プロジェクトオイラー Problem28

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 28
1から初めて右方向に進み時計回りに数字を増やしていき,
5×5の螺旋が以下のように生成される:
21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

両対角線上の数字の合計は101であることが確かめられる.
1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はいくつだろうか?


私の解答例は以下です。

def g(n):
 if n<1 or (not n%2): return 0
 elif n==1: return 1
 s, t = n-1, n-2
 u = t*t+s
 return u+(u+s)+(u+s*2)+(u+s*3)
 
def f(n): return sum([g(i) for i in xrange(1, n+1, 2)])
 
print f(1001)

１．g(n)
・関数g(n)は、一辺がn個の四角形の四隅値の合計値を返します。

・s, t = n-1, n-2
　sは一辺がn個の四角形の隣接する四隅の値の差、
　tは１つ内側の正方形の一辺の個数です。

・u = t*t+s
　uは一辺がn個の四角形の最小の四隅値です。結果として右下隅の数字です。
　まず１つ内側の正方形内の個数は、t*tです。
　そこから１つ右に進み、一辺n個の四角形に出るとその位置は、
　この四角形の右上隅の１つ下なので、右下隅までの長さはn-1です。
　これらの和uが右下隅値になります。
　
・return u+(u+s)+(u+s*2)+(u+s*3)
　あとは、右下隅値を基準に、四隅値の差分sを増しながら、四隅のすべての値を足します。
　
２．f(n)
・関数f(n)は、一辺がn個の四角形の対角線上の値の和を返します。
・sum([g(i) for i in xrange(1, n+1, 2)])
　一辺n個の四角形の一辺は1,3,5,・・・nの奇数です。
　まずxrange関数で1からn以下の奇数を発生させ、ループ変数iに設定します。
　そしてfor文の前に送り、g(i)を順番に計算して配列に貯めていきます。
　その後、その配列をsum関数で合計し、返却します。


（別解）

print sum([4*i*i-6*i+6 for i in xrange(3, n+1, 2)])+1

先ほどの関数g(n)はnの二次式にまとめることができます。
つまり、n>2の条件下で、
s = n-1
t = n-2
u = t*t+s
のときの以下の値を計算しておきます。
  u+(u+s)+(u+s*2)+(u+s*3)
= u*4 + s*6
= (t*t+s)*4 + s*6
= 4*t*t + 10*s
= 4*(n-2)*(n-2) + 10*(n-1)
= 4*(n*n - 4*n + 4) + (10*n - 10)
= 4*n*n - 6*n + 6

以上から、n≧3のとき上記の式で、n=1の対角線値として1を足すことにします。
まず、xrange関数で3からn以下の奇数を発生させ、ループ変数iに設定します。
そしてfor文の前に送り、「4*i*i-6*i+6」を順番に計算して配列に貯めていきます。
その後、その配列をsum関数で合計し、n=1のときの1を足して、返します。

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