操作
Problem 45 » 履歴 » リビジョン 1
リビジョン 1/2
| 次 »
Noppi, 2024/01/16 09:32
Problem 45¶
Triangular, Pentagonal, and Hexagonal¶
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
| Triangle | $T_n=n(n+1)/2$ | $1, 3, 6, 10, 15, \dots$ |
| Pentagonal | $P_n=n(3n - 1)/2$ | $1, 5, 12, 22, 35, \dots$ |
| Hexagonal | $H_n=n(2n - 1)$ | $1, 6, 15, 28, 45, \dots$ |
It can be verified that $T_{285} = P_{165} = H_{143} = 40755$.
Find the next triangle number that is also pentagonal and hexagonal.
三角数, 五角数, 六角数¶
三角数, 五角数, 六角数は以下のように生成される.
| 三角数 | $T_n=n(n+1)/2$ | $1, 3, 6, 10, 15, \dots$ |
| 五角数 | $P_n=n(3n - 1)/2$ | $1, 5, 12, 22, 35, \dots$ |
| 六角数 | $H_n=n(2n - 1)$ | $1, 6, 15, 28, 45, \dots$ |
$T_{285} = P_{165} = H_{143} = 40755$ であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
(import (scheme base)
(gauche base)
(scheme vector))
; 40755 から次の五角数を 10_0000 個求めてみる
; 10_0000 個目の値は 15050091750 だった
(define pentagonal-num
(let ([table (make-vector 10_0001)])
(let loop ([i 0] [current 41750] [inc 502])
(cond
[(< 10_0000 i) table]
[else
(vector-set! table i current)
(loop (+ i 1) (+ current inc) (+ inc 3))]))))
; 40755 から次の六角数を 15050091750 を超えないところまで求める
(define hexagonal-num
(list->vector
(let loop ([current 40755] [inc 573] [lis '()])
(if (< 15050091750 current)
(reverse lis)
(loop (+ current inc) (+ inc 4) (cons current lis))))))
(define (pentagonal-num? num)
(vector-binary-search
pentagonal-num
num
(^[a b] (- a b))))
(define find-tph
(let ([count (vector-length hexagonal-num)])
(let loop ([i 0])
(if (<= count i)
(errorf "解が見つかりませんでした~%")
(let ([current (vector-ref hexagonal-num i)])
(if (pentagonal-num? current)
current
(loop (+ i 1))))))))
(define answer-45 find-tph)
(format #t "45: ~d~%" answer-45)
Noppi が2024/01/16に更新 · 1件の履歴