Y箱

オイラーのトーシェント関数φ(n)の問題です。


まずは、普通に解いてみましがやっぱり15分もかかります。大きな数の素因数分解そのものに時間がかかるのが問題です。
答が出たので、まあこれでもいいかな...と思っていたのですが、帰りの電車で考えていたら、ひらめきまして、やり直しました。


nの素因数分解が







のようにあらわせるとき、φ(n)は、








で得られます。問題の答は、n/φ(n)を求めます。
最初のやりかたは、ここで、nを素因数分解して、この式をそのまま計算するものでした。

このあと、この式を眺めていて別の方法を思いつきました。

n/φ(n)の値はこういう値です。









nが消えるところがポイントです。
この式の値を大きくするということは、分母を小さくするということです。それには、掛け合わされているかっこの中を小さくすればすればよくて、かっこの中を小さくするには、pを小さくすればいいということがわかります。さらにその数が沢山あればなおいいですね。
ということで、求めるnは、小さな素因数を沢山持つものであることになります。
とはいっても、同じ素因数をいくら持っていても、pは増えませんので、これは、小さい素数から順に素因数として持つものということになります。

ようするに、2、3、5...と、小さいほうから順に1000000を超えないように素数を掛けていくと答が出るということです。
ただ、このやりかただと、重複している素因数がみつからないので、実際にもとめる数はこの数の倍数ということになります。



前半はだめな実装。

- get-n-slash-phi-n
  n/φ(n) を計算する関数
  素因数分解をして、式のとおりに計算しています。

- pe-69
  2からnまでの数について、上の関数を使って、n/φ(n)が最大のものを求める。

下の二つができたやつ。
- product-list
  与えられたコレクションを順に掛けてできる数のリストを返す。
  2 2 2 2 2... なら 2 4 8 16 32... が返ります。

- pe-69
  説明の通りの動作をする関数。
  上の関数で素数を順に掛けた数のリストを作って、引数以下の最大数を求めます。さらに、
  それの倍数で引数以下のものをすべて求めます。