Problem 44

Pentagon Numbers

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

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. 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 给出。前十个五边形数是：

可以看出 P₄ + P₇ = 22 + 70 = 92 = P₈。然而，它们的差 70 - 22 = 48 并不是五边形数。

在所有和差均为五边形数的五边形数对 P_j 和 P_k 中，找出使 D = |P_k - P_j| 最小的一对；此时 D 的值是多少？

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

容易发现有以下公式：

\[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))