Problem28

30分プログラム、その301。Problem28 via Project Euler。

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の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はともにいくつだろうか?

直接解かなくても、じっくり考えたら素敵な方法がありそうだったので考えてみた。

n	一辺の長さ	対角線	公差	初項
1	1	1	?	1
2	3	3,5,7,9	2	3
3	5	13,17,21,25	4	13
..
n	2n-1		size(n)-1	{size(n-1)}^2+size(n)-1

size(n)はn番目の四角形の一辺の長さ。
表から、n番目の四角形の対角線の初項と公差がわかった。項数は4であるのが自明なので、n番目の対角線の和が簡単にもとまる。あとは、500番目(1001x1001)までの和を求めてやればいい。

使い方

$ ghc --make problem28
[1 of 1] Compiling Main             ( problem28.hs, problem28.o )
Linking problem28 ...

$ time ./problem28
669171001
./problem28  0.01s user 0.02s system 24% cpu 0.115 total

ソースコード

diag size = if size == 1 then
                take 1 xs
            else
                take 4 xs
    where
      xs = [a,a+k..]
      k = size - 1
      prev = size - 2
      a = prev * prev + k

solve = let xs = [1,3..1001]
        in
          sum $ concat $ map diag xs

main = print solve

参考

• 過去の30分プログラム
• Problem 28 - PukiWiki