Euler : Problem 70

Posted by TAKAIY On 2011年12月8日木曜日 0 コメント

これもトーシェント関数の問題です。

普通に考えたら解けないのが分っているので、ちょっと考えます。





今回は、n/φ(n)を小さくするので、問題69で考えたことからすると、素因数の種類は少ないほうがいいということになります。
素因数を1つにするには、nは素数でなくてはならないのですが、nが素数のときのφ(n)は、n-1なので、これがpermutationになることはないでしょう。

ということで、素因数を2つとしてみます。少なくとも問題にある87109の素因数は2つなので、最悪、これが答になります。

さて、素因数が2つということは、

n=p1*p2

ということになります。 また、そのときのトーシェント関数の値は、

φ(n) = φ(p1)*φ(p2) = (p1-1)*(p2-1)

なので、掛けたときに10^7未満になる素数の組を作って、φ(n)とnがpermutationになるかどうか確認します。

20秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。






- permutation-num?
 名前の通り。

- pe-70
書いたとおりの動作の関数です。
permutationになるものをすべて求めて、n/φ(n) が最小のものを探します。

0 コメント:

コメントを投稿