Detailed mathematical approach

Problem Summary

The \(n\)-th pentagonal number is

$P_n=\frac{n(3n-1)}{2}.$

We seek indices \(j<k\) such that both \(P_j+P_k\) and \(P_k-P_j\) are pentagonal, and we want the positive difference

$D=P_k-P_j$

to be as small as possible. A naive search over all pairs is infinite, so the real task is to exploit the arithmetic structure of pentagonal numbers and organize the search so that most candidates are rejected quickly.

Mathematical Approach

The implementations are built around three ingredients: the explicit formula for pentagonal numbers, a constant-time test for deciding whether a number is pentagonal, and a monotone scan order that allows safe pruning inside the nested loops.

The pentagonal sequence is strictly increasing

The first few pentagonal numbers are

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

and their growth is quadratic. More importantly for the code, the sequence is strictly increasing because

$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$

This monotonicity is the key invariant used by the search. For a fixed larger index \(k\), if we inspect smaller indices in the order \(j=k-1,k-2,\dots,1\), then \(P_j\) decreases and therefore the difference \(P_k-P_j\) increases step by step.

Testing whether an integer is pentagonal

Suppose \(x=P_n\). Starting from \(x=n(3n-1)/2\), multiply by 24 and complete the square:

$24x+1=12n(3n-1)+1=(6n-1)^2.$

So an integer \(x>0\) is pentagonal exactly when \(24x+1\) is a perfect square and

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

is an integer. Equivalently, if \(s=\sqrt{24x+1}\), then \(s\) must be integral and \(s\equiv 5 \pmod 6\). The implementations use this inverse test instead of scanning a list for membership. That makes every sum and difference check an \(O(1)\) arithmetic operation.

Rewriting the difference condition

For \(j<k\), the difference between two pentagonal numbers can be written as

$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$

This formula shows immediately that the gap depends on both the index difference \(k-j\) and the index sum \(k+j\). It is useful conceptually, but the code relies on an even simpler fact: for fixed \(k\), once \(j\) moves downward, the quantity \(P_k-P_j\) can only get larger. Therefore, if a valid pair has already produced a best difference \(D_{\min}\) and the current candidate satisfies

$P_k-P_j\ge D_{\min},$

then every later candidate in that same inner loop is automatically worse. The loop can stop immediately without missing a better answer.

The sum condition has no comparable monotone shortcut, so each remaining candidate still needs a direct pentagonal test on

$P_k+P_j.$

Worked example

Take \(P_4=22\) and \(P_7=70\). Their sum is

$22+70=92,$

and

$24\cdot 92+1=2209=47^2,$

so \(92\) is pentagonal, in fact \(92=P_8\). But their difference is

$70-22=48,$

and

$24\cdot 48+1=1153,$

which is not a perfect square. So this pair satisfies the sum condition but fails the difference condition. The example shows why both tests are essential: a rare pentagonal sum does not imply a pentagonal difference.

How the Code Works

The C++, Python, and Java implementations first precompute the pentagonal numbers \(P_1,P_2,\dots,P_M\) for a configurable upper index bound \(M\); in the provided programs the default is 5000. Keeping these values in an array avoids recomputing the quadratic formula during the pair scan.

To decide whether a sum or difference is pentagonal, the implementation applies the inverse criterion \(24x+1=(6n-1)^2\). One version uses an integer square root to check the discriminant exactly; the other two compute a square root, round to the nearest candidate index, and then substitute that index back into \(n(3n-1)/2\). In all three cases, the final acceptance step is exact because the recovered index must reproduce the original value. Before the full search begins, the programs also verify this predicate on small known cases such as 12 and 35, reject 36, and confirm the larger pentagonal number 40755.

The main search enumerates the larger index increasingly. For each larger index, it walks the smaller index downward, computes the current difference and sum, and uses the monotonicity of the difference to stop the inner loop as soon as the current gap is no longer better than the best valid one already found. Only the candidates that survive this pruning are tested for the two pentagonal conditions. Whenever both tests succeed, the best difference is updated. After all indices up to the chosen bound have been processed, that smallest recorded difference is returned.

Complexity Analysis

If \(M\) is the search bound on the larger index, precomputing the pentagonal table costs \(O(M)\) time and \(O(M)\) space. The nested scan over pairs costs \(O(M^2)\) time in the worst case, because it may inspect on the order of \(M(M-1)/2\) pairs. Each inspection performs only constant-time arithmetic together with two constant-time pentagonality checks.

The pruning rule often saves a noticeable fraction of the inner loop once a good candidate has been found, but it does not change the worst-case asymptotic bound. So the method is still a quadratic search in theory, yet it is practical here because the bound is modest and the direct pentagonal test is very cheap.

Footnotes and References

1. Problem page: Project Euler 44
2. Pentagonal numbers: Wikipedia - Pentagonal number
3. Further formulas: MathWorld - Pentagonal Number
4. Sequence data: OEIS A000326