Project Euler/44

Problem Statement

Pentagonal numbers are generated by the formula:

$ P_n = \frac{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 both pentagonal and $ D = |P_k - P_j| $ is minimised; what is the value of $ D $?

Approach

Pentagonal Number Generation

Pentagonal numbers are generated directly from the closed-form formula $ P_n = \frac{n(3n-1)}{2} $. The solution generates these on the fly rather than pre-computing a fixed set, since the search bound is not known in advance.

Inverse Pentagonal Check

To test whether a number $ x $ is pentagonal, solve the quadratic equation:

$ \frac{n(3n-1)}{2} = x \implies 3n^2 - n - 2x = 0 $

Applying the quadratic formula yields:

$ n = \frac{1 + \sqrt{1 + 24x}}{6} $

If $ n $ is a positive integer, then $ x $ is pentagonal. The implementation truncates the result to a long and verifies that plugging it back into the pentagonal formula reproduces $ x $.

Search Strategy

The algorithm uses a doubly-nested loop over indices, generating pentagonal numbers incrementally:

• Outer loop: iterate $ n = 1, 2, 3, \dots $ to produce $ P_n $ (the larger pentagonal number, $ P_j $).
• Inner loop: for each $ n $, iterate $ k = n-1 $ down to $ 1 $, producing $ P_k $ (the smaller candidate).
• Compute the sum $ S = P_n + P_k $ and difference $ D = P_n - P_k $.
• If both $ S $ and $ D $ are pentagonal, return $ D $ as the answer.

Because the outer loop increases the larger pentagonal number $ P_n $ monotonically, the first valid pair encountered minimizes $ D $ — any later pair would involve a larger $ P_n $ and therefore a potentially larger difference.

Optimization Notes

• The inner loop counts downward from $ n-1 $ to $ 1 $, checking larger values of $ P_k $ first. This tends to find small differences sooner.
• The inverse pentagonal check uses floating-point Math.sqrt and is O(1), making the overall search efficient without precomputed hash tables.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem044.java