HOME SUMMARY

Problem 44

1. Problem

Pentagon Numbers

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

1,5,12,22,35,51,70,92,117,145,…

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 - 22 = 48, is not pentagonal.

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

五边形数

五边形数由公式 Pn = n(3n-1)/2 给出。前十个五边形数是:

1,5,12,22,35,51,70,92,117,145,…

可以看出 P4 + P7 = 22 + 70 = 92 = P8。然而,它们的差 70 - 22 = 48 并不是五边形数。

在所有和差均为五边形数的五边形数对 Pj 和 Pk 中,找出使 D = |Pk - Pj| 最小的一对;此时 D 的值是多少?

2. Solution

本题的目标是找出最小的且为两个五边形数之差的五边形数,而且同时要满足两个五边形数之和也为五边形数。显然有较小的五边形数必大于等于较大五边形数的后继减去较大数。

容易发现有以下公式:

\[P_{n+1} - P_{n} = 3n + 1 \ \ n \ge 1\]

\[P_{n+k} - P_{n} = \sum_{i=0}^{k-1}(3(n+i) + 1) = 3nk + \frac{3k^2 - k}{2} = 3nk + P_{k} \ \ n,k \ge 1\]

\[P_{n+k} + P_{n} = \frac{n(3n-1)}{2} + \frac{(n+k)(3n+3k-1)}{2} = 2P_{n} + P_{k} + 3nk\ \ n,k \ge 1\]

由于不知道这个问题的上界在哪,这里我也只能假设答案位于数列的前 10000 项中,使用上面的公式来进行计算:

(defun eu44-penta (n)
  (/ (* n (1- (* n 3))) 2))

(let ((tbl (make-hash-table :size 20000))
      (res nil))
  (cl-loop for i from 1 to 20000
           do (puthash (eu44-penta i) t tbl))
  (cl-loop
   for i from 2 to 10000
   do (cl-loop
       for k from 1 to (- 10000 i) do
       (when (and (gethash (+ (eu44-penta k) (* 3 i k)) tbl)
                  (gethash (+ (eu44-penta k)
                              (* 2 (eu44-penta i))
                              (* 3 i k))
                           tbl))
         (push `(,i ,(+ i k) ,(+ (eu44-penta k) (* 3 i k)))
               res))))
  res)
=> ((1020 2167 5482660))