Problem 44: Pentagon Numbers

Pentagonal numbers are generated by the formula, $P_{n} = n (3 n - 1) / 2$ . 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 = | P_{k} - P_{j} |$ is minimised; what is the value of $D$ ?

Solution

The goal is to find $j, k, d, s$ such that $P_{k} - P_{j} = P_{d}$ and $P_{k} + P_{j} = P_{s}$ , and $P_{d}$ is minimized. To guarantee this last condition, my program iterates over increasing values of $d$ .

The expression $P_{d} = P_{k} - P_{j}$ evaluates to $\frac{1}{2} d (3 d - 1) = \frac{1}{2} (3 k^{2} - k) - \frac{1}{2} (3 j^{2} - j)$ . This simplifies to $d (3 d - 1) = (k - j) (3 k + 3 j - 1)$ . As such, I iterate over all factors $a$ of $2 P_{d}$ using a SymPy function, set $b = \frac{2 P_{d}}{a}$ , and solve the system of equations $a = k - j, b = 3 k + 3 j - 1$ for $k$ and $j$ . This inner loop breaks when $b < 3 a$ .

The system of equations has the solution $k = \frac{3 a + b + 1}{6}$ and $j = \frac{- 3 a + b + 1}{6}$ , which is a pair of integers if $b \equiv 2 \mod 3$ and $a$ and $\frac{b + 1}{3}$ have the same parity. From there, it's a matter of checking whether $P_{k} + P_{j}$ is a pentagonal number. If $P_{k} + P_{j} = \frac{s (3 s - 1)}{2}$ for $s > 0$ , then by the quadratic formula, $s = \frac{1 + \sqrt{1 + 24 (P_{k} + P_{j})}}{6}$ . If this is an integer, we're done.

Python Code

from itertools import count
from sympy import divisors
from math import isqrt
def p44():
	for d in count(1):
		Pd2 = d * (3*d - 1)
		for a in divisors(Pd2):
			b = Pd2 // a
			if b < 3 * a:
				break
			if b % 3 == 2:
				c = (b + 1) // 3
				if a % 2 == c % 2:
					k = (a + c) // 2
					j = (c - a) // 2
					Pk2 = k * (3*k - 1)
					Pj2 = j * (3*j - 1)
					Ps2 = Pk2 + Pj2
					if isqrt(1+12*Ps2)**2 == 1+12*Ps2 and (1 + isqrt(1 + 12*Ps2)) % 6 == 0:
						return Pd2 // 2

Previous Problem Next Problem

Back to Project Euler