Admin: Create Project Euler/44 page with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)

2026-06-16T14:24:48Z

Create Project Euler/44 page with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)

New page

==Problem Statement==

Pentagonal numbers are generated by the formula:

<math>
P_n = \frac{n(3n-1)}{2}
</math>

The first ten pentagonal numbers are:

<math>
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \dots
</math>

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

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

==Approach==

===Pentagonal Number Generation===

Pentagonal numbers are generated directly from the closed-form formula <math>P_n = \frac{n(3n-1)}{2}</math>. 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 <math>x</math> is pentagonal, solve the quadratic equation:

<math>
\frac{n(3n-1)}{2} = x \implies 3n^2 - n - 2x = 0
</math>

Applying the quadratic formula yields:

<math>
n = \frac{1 + \sqrt{1 + 24x}}{6}
</math>

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

===Search Strategy===

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

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

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

===Optimization Notes===

* The inner loop counts '''downward''' from <math>n-1</math> to <math>1</math>, checking larger values of <math>P_k</math> first. This tends to find small differences sooner.
* The inverse pentagonal check uses floating-point <code>Math.sqrt</code> 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

==Flags==

{{ProjectEulerFlag}}

Project Euler/44 - Revision history

Admin: Create Project Euler/44 page with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)