Problem 69 - オイラーの関数

久しぶりにキマッた。

Problem 69 - Project Euler

翻訳無かったけど、オイラーの関数に関する問題。

オイラーの関数φ(n)は、nと互いに素な整数の個数を表す。

例えば、

φ(6) = {1,5} = 2
φ(10) = {1,3,7,9} = 4

n/φ(n)とすれば、nのなかに互いに素な整数の割合がわかる。

nを素因数分解した素数をp_kとすると、オイラーの関数は、

φ(n)= n (1 - 1/p_1)(1 - 1/p_2)(1 - 1/p_3)....(1 - 1/p_k)

として求められる。

6の中から2と3で割り切れるものを除いてやると、互いに素の整数1,5だけが残る。

で、今回は100万までのn/φ(n)が一番大きなものを探す。

つまり、互いに素ではない整数の割合が最も多いものを選べばいい。

2の倍数が一番多くの互いに素ではない整数を持つ。
3の倍数が２番目に多くの互いに素ではない整数を持つ。
5の倍数が・・・

素因数分解したら最も多くの素数が取れるもの・・・素数の積を出せばいい。

暗算でもいけちゃうぜ。

(* 2 3 5 7 11 13 17) ; 510510

ハイ。

もうちょっと真面目に。

(define (prime? n)
  (letrec ((trial-divisor
             (lambda (t)
               (or (< n (* t t))
                   (and (not (zero? (remainder n t)))
                        (trial-divisor (+ t 2)))))))
    (and (> n 1)
         (or (= n 2)
             (and (odd? n)
                  (trial-divisor 3))))))

(define (problem69 n)
  (letrec ((iter
             (lambda (m acc)
               (cond ((> (* acc m) n) acc)
                     ((prime? m) (iter (+ m 2) (* m acc)))
                     (else
                       (iter (+ m 2) acc))))))
    (iter 3 2)))

(problem69 1000000) ; 510510

普通にやったら100万*素因数分解かかる計算をたった数十回で終わらせることが出来た。

気持ちいい。