ホーム - Project Euler

Problem 44¶

Pentagon Numbers¶

Pentagonal numbers are generated by the formula, $P_n=n(3n-1)/2$. The first ten pentagonal numbers are:

$$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \dots$$

It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, $70 - 22 = 48$, is not pentagonal.

Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and $D = |P_k - P_j|$ is minimised; what is the value of $D$?

五角数¶

五角数は $P_n=n(3n-1)/2$ で生成される. 最初の10項は

$$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \dots$$

である.

$P_4 + P_7 = 22 + 70 = 92 = P_8$ である. しかし差 $70 - 22 = 48$ は五角数ではない.

五角数のペア $P_j$ と $P_k$ について, 差と和が五角数になるものを考える. 差を $D = |P_k - P_j|$ と書く. 差 $D$ の最小値を求めよ.

(import (scheme base)
        (gauche base)
        (scheme vector))

(define pentagonal-num
  (list->vector
    (cdr
      (map (^n
             (/ (* n
                   (- (* n 3) 1))
                2))
           (iota 10002)))))

(define (pentagonal-num? n)
  (vector-binary-search
    pentagonal-num
    n
    (^[a b] (- a b))))

(define find-pentagonal-pair
  (let loop1 ([k 1])
    ; 10000 まで生成した時、7070 + 7071 までは値が範囲を超えなかった
    (if (< 7071 k)
      (errorf "解が見つかりませんでした~%")
      (let ([p_k (vector-ref pentagonal-num k)])
        (let loop2 ([j (- k 1)])
          (if (negative? j)
            (loop1 (+ k 1))
            (let ([p_j (vector-ref pentagonal-num j)])
              (if (and (pentagonal-num? (- p_k p_j))
                       (pentagonal-num? (+ p_k p_j)))
                `(,p_j . ,p_k)
                (loop2 (- j 1))))))))))

(define answer-44
  (- (cdr find-pentagonal-pair)
     (car find-pentagonal-pair)))

(format #t "44: ~d~%" answer-44)