PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 120 / 自乗で割った余り

(a-1)^n+(a+1)^n を a^2 で割った余りを r とする。たとえば a=7, n=3 のとき r=42 である。

6^3 + 8^3 = 728 ≡ 42 (mod 49)

n が変われば r も変わるが,a=7 のとき r の最大値 r_max は 42 であることがわかる。

3 ≤ a ≤ 1000 において Σ r_max を求めよ。

Problem 120 - Project Euler


うーん,これはほぼ数学の問題と言ってよいかと。a^2 を法として考えます。

f:id:variee:20170320222804p:plain

最大値を求めるには n が奇数の場合を考えれば十分です。

 r= mod[2na, a^2 ]

2na を a^2 で割ったときの商を q とします。

 2na=a^2 q+r

r は a の倍数だということがわかります。r=aR (1≦R≦ a-1)とおいて上の式に代入し,両辺を a で割ります。

 2n=aq+R

これは1次の不定方程式。2と a が互いに素なとき,つまり a が奇数のときは R=a-1 を与える n が存在します。r=aR の最大値は a(a-1)。

2と a が互いに素でないとき,つまり a が偶数のときは両辺を2で割って上と同じ議論をすると R の最大値は a-2 だとわかります。 r=aR の最大値は a(a-2)。

シグマ計算しやすい形にまとめましょう。2≦b≦500とします。a = 2b-1 のとき

 r_{max}=(2b-1)(2b-2)=4b^2-6b+2

a = 2b のとき

 r_{max}=2b(2b-2)=4b^2-4b

これらの和 8b^2-10b+2 を足しあわせたものが答えです。手計算でも楽勝ですね。