PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 231 / 二項係数の素因数分解

二項係数 C[10, 3] = 120 は

  • 120 = 2^3 ×3×5 = 2×2×2×3×5
  • 2+2+2+3+5 = 14

をみたす。C[10, 3] を素因数分解した項の和は 14 となる。

C[20000000, 15000000] を素因数分解した項の和を求めよ。

Problem 231 - Project Euler


ダメ元で素因数分解させてみたらやはりダメでした。n を素因数分解した項の和を f(n) として考えます。

二項係数は C[m, n] = m! / n! (m-n)! と変形できます。求める和は f(分子) - f(分母) で求められますし,

f(m!)=f(1)+f(2)+...+f(m)

も言えます。

まず f(n) を求めましょう。FactorInteger[ ] すると {素数, 指数} のリストが得られ,その積の和が f(n) です。f(120) で実験してみました。


あとはこれを(大量に)足し引きするだけです。C[m, n] を約分した上で計算してもらいました。