Problem 28 - 対角線の和

この問題は面白かった。

Problem 28 - PukiWiki

1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:
21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13

対角線上の数字の合計はどちらも101であることが確かめられる.

1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はともにいくつだろうか?

何か法則が見える。


さて法則を見破る。f(n)で、nは偶数とする。

f(1)の時、1
f(3)の時、f(1) + 3 + 5 + 7 + 9
f(5)の時、f(3) + 13 + 17 + 21 + 25

となる。


もうちょい深める。対角線なので、4つづつ増える事を利用してまとめる。

f(1)の時、1
f(3)の時、f(1) + (3 + 9) + (5 + 7) = f(1) + (3 + 9) * 2
f(5)の時、f(3) + (13 + 25) + (17 + 21) = f(3) + (13 + 25) * 2

つまり、f(n) = f(n-2) + (始点+終点)*2である。


始点は、(n - 2)^2 + (n - 1)
終点は、n^2なので、

f(1) = 1
f(n) = f(n-2) + (n^2 + (n - 2)^2 + n - 1) * 2

という式を導き出した。


後はコーディングするだけ。

(define (problem28 n)
  (define (square n) (* n n))
  (define (iter n)
    (if (= n 1)
        1
        (+ (* 2 (+ (square n) (square (- n 2)) n -1))
           (problem28 (- n 2)))))
  (iter n))

(problem28 1001) ; 669171001

あってた。ちょっとビックリ。