PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 381 / (素数-k)階乗

素数 p について,1 ≤ k ≤ 5 の k に対し S(p) = (Σ(p-k)!) mod(p) としよう。

たとえば p=7 の場合,

(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)!
= 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2
= 872

872 mod(7) = 4 となるので, S(7) = 4

5 ≤ p < 100 のとき,ΣS(p) = 480 となる。

5 ≤ p < 10^8 のときの ΣS(p) を求めよ。

Problem 381 - Project Euler


計算式がはじめから与えられている珍しい問題です。一応やってみましたが,そのまま計算するのは無理でした。

Wilson の定理(くわしくはwikipediaで→ ウィルソンの定理 - Wikipedia)を使って式を整理します。

(p-1)! ≡ -1 (mod p)

これに p-1 の逆元をかけると (p-2)! になります。

Mathematica には逆モジュロを求める関数があります。PowerMod[a, b, n] です。これは Mod[a^b, n] を求める関数なのですが,指数 b に負の数を指定できます。7を法としたときの5の逆元を求めてみましょう。 結果は3です。5*3=15≡1 (mod 7) ということですね。


この方法で S(p) を簡単な形にして和をとります。