Speedup for Project Euler 44 - pentagon numbers
You're right that the problem condition that \$\left|P_k - P_j\right|\$ be minimized means that to properly solve it, it's not sufficient to find a pair of pentagonal numbers whose sum and difference are both pentagonal: you have to also establish that there is no pair of pentagonal numbers with the required property and a smaller difference.

Once you've found one pair of pentagonal numbers with the required property, this gives you a bound on \$j\$ and \$k\$; unfortunately the bound is in the millions, so that any \$\Omega(n^2)\$ algorithm (in particular, any algorithm that compares pairs of pentagonal numbers below the bound) will take far too long. It's no good just speeding up what you've got: you have to take a completely new approach.

So here's a rough sketch of an alternative algorithm.

The \$n\$th pentagonal number is $$P_n = {n(3n-1)\over 2}.$$ By completing the square, $$P_n = {(6n - 1)^2 - 1 \over 24}.$$ If \$P_k - P_j = P_x\$ and \$P_k + P_j = P_y\$ are both pentagonal numbers, then $$ \eqalign{ (6k - 1)^2 - (6j - 1)^2 &amp;= (6x - 1)^2 - 1 \\ (6k - 1)^2 + (6j - 1)^2 &amp;= (6y - 1)^2 + 1 } $$ Write \$K = 6k - 1\$, \$X = 6x - 1\$, and \$Y = 6y - 1\$. Add the two equations above, getting $$ 2K^2 = X^2 + Y^2. $$

So the plan is:


Iterate over all values for \$k\$ below the bound that you already established.
For each \$k\$, let \$K = 6k - 1\$, and enumerate all the ways to write \$2K^2\$ as the sum of two squares \$X^2 + Y^2\$.
For each such decomposition, if \$X ≡ -1 \pmod 6\$ and \$Y ≡ -1 \pmod 6\$ and \$J = \sqrt{K^2 - X^2 + 1} ≡ -1 \pmod 6\$, then this is a solution.


In step 2, the enumeration of \$2K^2\$ as sums of two squares can be computed efficiently by factorizing \$K\$ and then using the Brahmagupta–Fibonacci identity. Since you are going to be needing a lot of these factorizations, it will be most efficient to sieve for them.

This ought to be doable within your 10 second goal.

(Credit: I adapted this strategy from Daniel Fischer's post in the Project Euler forum.)