Pentagon numbers¶

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. 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 = |P_k − P_j| is minimised; what is the value of D?

Idea¶

Naive solution.

Assume $ j \lt k $, so $ P_j \lt P_k $, so $ D = |P_k - P_j| = P_k - P_j = \frac{k(3k-1)}{2} - \frac{j(3j-1)}{2} = \frac{(k-j)(3(k+j)-1)}{2}$.

Let $t=k-j$, then $ D=\frac{t(3(t+2j)-1)}{2}$, it always increases w.r.t $t$, since $j \gt 0$.

So for a certain $k$, we will search through $j=k-1, ...., 1 $

from math import ceil, sqrt

def get_pentagon(n):
    return n * (3*n-1) // 2

def is_sum_pentagon(pj, pk):
    n = ceil(sqrt(pj+pk) / sqrt(3/2))
    while get_pentagon(n) < pj + pk:
        n += 1
    return get_pentagon(n) == pj + pk

is_sum_pentagon(22, 70)

True

is_sum_pentagon(12, 22)

False

def solve():
    pentagon_numbers = set([0, 1])
    k = 2
    while True:
        pk = get_pentagon(k)
        pentagon_numbers.add(pk)
        for j in range(k-1, 0, -1):
            pj = get_pentagon(j)
            if (pk-pj) in pentagon_numbers and is_sum_pentagon(pj, pk):
                return pk - pj
        k += 1

solve()

5482660