Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[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$ であることが分かる.

次の三角数かつ五角数かつ六角数な数を求めよ.

```scheme

(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)

```