problem 45 - mtsuyuguの日記

三角数: Tn=n(n+1)/2 かつ五角数 Pn=n(3n-1)/2 かつ六角数 Hn=n(2n-1) をみたす数のうち 40755 の次の数は何かという問題です。

三角数 Tn について n = 2k-1 を代入すると

Tn = n(n+1)/2
   = (2k-1)(2k-1+1)/2
   = 2k(2k-1)
   = Hk

が成り立つことから、六角数は奇数番目の三角数であることがわかります。よって答えを選るのに三角数は無視してもいいということです。

次に求める数を x とすると x は五角数なので

n(3n-1)/2 = x

を満たす正の整数 n があるということです。これを n について解くと

3n^2 - n - 2x = 0
n = (1+√(1+24x))/6

となるので、x に六角数を代入していき n が整数になる場合を見つけていけば、そのときの x が求める答えということになります。

以上を scheme で実装したのがこちら。

(define (hexagonal n)
  (* n (- (* 2 n) 1)))

(define (pentagonal? x)
  (integer? (/ (+ 1 (sqrt (+ 1 (* 24 x)))) 6)))

(define (p45)
  (let loop ((i 0)
             (result '()))
    (if (= (length result) 3)
      result
      (loop (+ i 1)
            (if (pentagonal? (hexagonal i))
              (cons (hexagonal i) result)
              result)))))

(print (p45))