# Project Euler Problem 44: Pentagon numbers

Pentagonal numbers are generated by the formula, $P_n=\frac{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_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$?

In [1]:
def polygonal(s):
c = s - 2
a = b = 1
while True:
yield a
b += c
a += b

In [2]:
def sum_diff_polygonal(s):
seen = set()
for i in polygonal(s):
for j in seen:
p = i - j
q = j
# we already know p+q=i is s-gonal
# since i must be; just need to check
# that p and p-q are as well
if p in seen and p-q in seen:
yield p, q

In [3]:
it = sum_diff_polygonal(5)

In [4]:
next(it)

Out[4]:
(7042750, 1560090)
In [5]:
def sum_diff_polygonal(s):
seen = set()
for i in polygonal(s):
for j in seen:
if i-j in seen and i-2*j in seen:
yield i-j, j

In [6]:
it = sum_diff_polygonal(5)

In [7]:
next(it)

Out[7]:
(7042750, 1560090)
In [8]:
it = sum_diff_polygonal(3)

In [9]:
next(it)

Out[9]:
(21, 15)
In [10]:
next(it)

Out[10]:
(171, 105)
In [11]:
from itertools import islice

In [12]:
list(islice(polygonal(3), 25))

Out[12]:
[1,
3,
6,
10,
15,
21,
28,
36,
45,
55,
66,
78,
91,
105,
120,
136,
153,
171,
190,
210,
231,
253,
276,
300,
325]

#### TODO: Prove minimality of $| P_k - P_j |$¶

If we have $k$ such that $P_k$ is triangular and there is only one $j < k$ such that $P_j$, $P_k + P_j$ and $P_k - P_j$ is triangular then we need only minimize $k$ to minimize $| P_k - P_j |$. Otherwise, we'd need to consider $j=k-1, k-2, \cdots, 2, 1$.