28問目

Project Euler math

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

2つの対角線上にある数字の合計は101と分かります.
同様にして1001×1001サイズの渦の両対角線上の数字の合計はいくつか?

http://projecteuler.net/index.php?section=problems&id=28

たぶんプログラム組んで解こうとすると, 「対角線上にある」判定が面倒なんだろう. しかし, 数学使って解いてしまえばなんてことはないので, 数学のみで解いた.

☆ . . .☆
 . * * * .
 . * * * .
 . * * * .
☆ . . .☆

中央のアスタリスクでできた正方形のサイズを (2n+1) × (2n+1) とすると, 4つの☆のところにある数字の合計は,
\begin{eqnarray}&&\{(2n+1)^2+(2n+1)+1\}\\ &+& \{(2n+1)^2+(2n+1)+(2n+2)+1\}\\&+&\{(2n+1)^2+(2n+1)+2(2n+2)+1\}\\&+&\{(2n+1)^2+(2n+1)+3(2n+2)+1\}\\&=&4(4n^2+9n+6).\end{eqnarray}
一般的に (2L+1)×(2L+1) サイズの渦に対しては, これを n=0 から L-1 まで足して, 最後に中心の1を加えて終了.
\begin{eqnarray}1 + \sum_{n=0}^{L-1} 4(4n^2+9n+6) &=& 1+4\{4\cdot\frac{(L-1)L(2L-1)}{6} + 9\cdot\frac{(L-1)L}{2} + 6L\}\\ &=& \frac{8(L-1)L(2L-1)}{3} + 18(L-1)L + 24L + 1.\end{eqnarray}