Problem 248

248 Numbers for which Euler’s totient function equals 13!

Problem 248 – Project Euler

phi(n) = 13 ! となる n を探す問題.

一見,探索範囲が広そうに見えるが…

n を 素因数ベースで考えれば,そもそも n に含まれる素因数が少ないことに気づく.

m , n を互いに素として, phi(m * n) = q ならば, phi(n) = q / phi(m).で,q が小くなる.

ということで, n の素因数を固定して,問題を小くして再帰的に解いた.

Haskellのコード(パスは答えの下10桁,the 100,000th such number)

http://firestorage.jp/download/78b8ef8964240964e88d2fd78e535c8799aa6782

More Reading
Older// Problem 249