PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 429 / 単約数の自乗和

ある数 n の単約数(unitary divisor)d とは gcd(d, n/d)=1 となる n の約数のことである。4!=24 の単約数は 1, 3, 8, 24 であり,これらの自乗和は

1^2 + 3^2 + 8^2 + 24^2 = 650

n の単約数の自乗和を S(n) で表す。S(4!)=650 である。

S(100,000,000!) を求め,1,000,000,009 を法として答えよ。

Problem 429 - Project Euler


単約数は各素因数を目一杯使った約数のことです。4! と S(4!)=650 を素因数分解すれば解けます。

 4!=2^3 \times 3,\, 650=\left\{(2^3)^2+1\right\} \left\{(3^1)^2+1\right\}

これを一般化すればOK。計算時間は70秒。

  1. 10^8! を素因数分解
  2. 各指数 k を2倍
  3. Mod[p^(2k)+1,1000000009] の積を求める
  4. 最後にもう一度 1000000009 で割る