Problem 45 - 三角数、五角数、六角数

同じような問題があった気がする。

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.

三角数、五角数、六角数で共通する値を探す。

六角数なら三角数と言えるので、三角数を見る必要が無い。

五角数の式から、解の方程式を使って、五角数チェックを作れば完了。

五角数の結果をxと置いといて、

x = n(3n − 1) / 2

変形して、

3n^2 - n - 2x = 0

解の方程式から、

n = (1 ± √(1 + 24x)) / 6

プラス側を採用し、nが整数であれば、五角数と言える。

(define (problem45 n)
  (let ((pentagonal? (lambda (n)
                       (integer? (/ (+ (sqrt (+ 1 (* 24 n))) 1) 6))))
        (hexagonal (lambda (n)
                     (* n (- (* 2 n) 1)))))
       (if (pentagonal? (hexagonal n))
           (hexagonal n)
           (problem45 (+ 1 n)))))

(problem45 2) ; 40755
(problem45 144) ; 1533776805

案外早くてビビッタ。