#44 - Pentagonal numbers

20 May 2016 in Project Euler on 5%

Pentagonal numbers are generated by the formula, $P_n=\frac{1}{2}n(3n-1)$. 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 pentagonal and $D=\lvert P_j - P_k\rvert$.

---

Just like #42 - Coded triangle numbers, we need to test if a given number is a pentagonal number. Solving the equation by the quadratic formula, we get, $$n=\frac{1+\sqrt{24P_n+1}}{6}$$

If $n$ is an integer for a given input value, then $P_n$ is a valid pentagonal number. This will be the condition that we test. To minimize the difference, $P_j$ and $P_k$ need to be as close as possible to each other.

Therefore, this problem can be solved using two for loops; One to increase $P_k$ and the other to check all pentagonal numbers below $P_k$.

# file: "problem044.py"
def isPentagonal(x):
    n = ((24 * x + 1) ** 0.5 + 1) / 6
    return int(n) == n

notFound = True
k = 2
while notFound:
    Pk = k * (3 * k - 1) // 2
    for j in range(k - 1, 0, -1):
        Pj = j * (3 * j - 1) // 2
        if isPentagonal(Pk + Pj) and isPentagonal(Pk - Pj):
            print(Pk - Pj)
            notFound = False
            break
    k += 1

The output is,

5482660
2.5649144140300306 seconds.

Thus, $D=\mathbf{5482660}$.