プロジェクトオイラー 問１２０

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１２０「自乗で割った余り」
(a-1)ⁿ + (a+1)ⁿ を a² で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 6³ + 8³ = 728 ≡ 42 mod 49.
n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≦ a ≦ 1000 において, Σ rmax を求めよ.


注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def f(s, e): return sum([a*(a - (2- a%2)) for a in xrange(s, e+1)])
start, end = 3, 1000
print f(start, end)

まず、(a+1)ⁿ + (a-1)ⁿ　を展開してみます。
(a+1)ⁿ + (a-1)ⁿ ÷ a² の余りについて、手計算して様子を見てみます。

n=2のとき
  (a+1)² + (a-1)²
= (a² + 2*a + 1) + (a² - 2*a + 1)
= 2(a² + 1)
なので、a²で割った余りは、2です。

n=3のとき
  (a+1)³ + (a-1)³
= (a³ + 3*a² + 3*a + 1) + (a³ - 3*a² + 3*a - 1)
= 2(a³ + 3*a)
= 2(aⁿ * n*a)
なので、a²で割った余りは、2*n*aのa²での余り、2*n*a÷a²の余りです。

n=4のとき
  (a+1)⁴ + (a-1)⁴
= (a⁴ + 4*a³ + 6*a² + 4*a + 1) + (a⁴ - 4*a³ + 6*a² - 4*a + 1)
= 2(a⁴ + 6*a²) + 2
なので、a²での余りは、2です。

上記より、展開式をaの乗数の多い項から順に並べたとき、
・aの係数は二項係数でパスカルの三角形のそれぞれの値です。
・(a+1)と(a-1)のn乗同士をたすことで、偶数番目の項は互いに打ち消し合います。
・題意からn≧3なので、aの2乗以上の項は全部割り切れ、余りはでません。
なので、
nが奇数の場合、余りはa¹の項だけみればよく、2*n*a÷(a²)の余りです。
nが偶数の場合、余りはa⁰の項だけみればよく、2です。
なので、nが奇数の場合だけ考えれば十分です。
割り算の余りは「割られる数」＝「割る数の倍数」のときに0になり、
割られる数がこの値よりも小さいができるだけ大きな値というのが求める値です。
また、「割られる数」が「割る数」を超えると、
それまでに出現した余りが再度循環して出現するので、
「割られる数」が「割る数」以下の場合だけ考えれば十分です。
特に、「割られる数」＝「割る数」の場合、商が1で余り0。
「割られる数」がこの値よりも小さいができるだけ大きな値の場合、
商が0で残りが余りになり、「割られる数」＝「余り」になります。
そこでまず、「割られる数」＝「余り」の場合のnを計算します。
2an = a²
n = a/2
nがこの値よりも小さくできるだけ大きな値のとき、余りが最大になります。
ところで、題意からnもaも整数なので、aが奇数か偶数かで場合分けが必要です。
(1)aが奇数の場合
n = a/2よりも小さくできるだけ大きな値は、n = (a-1)/2 です。
このときの求める値は、2an = 2a(a-1)/2 = a(a-1) です。
(2)aが偶数の場合
n = a/2よりも小さくできるだけ大きな値は、n = (a-2)/2 です。
このときの求める値は、2an = 2a(a-2)/2 = a(a-2) です。
aを奇数か偶数かで場合分けして上記の値を累計すればいいことになります。

１．関数f(s, e)
s以上e以下の値について、問題文にある最大値を返します。
・sum([a*(a - (2- a%2)) for a in xrange(s, e+1)])
　%演算子は余りなので、
　「a%2」は、aが奇数なら1、偶数なら0です。
　「2 - a%2」は、aが奇数なら1、偶数なら2です。
　「a*(a - (2- a%2))」は、aが奇数ならa(a-1)、aが偶数ならa(a-2)　です。
　sからeまで順にaのforループで上記の計算結果を配列に入れて、sum関数で合計します。
　ループは内包表記をしています。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
333082500