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    
        seen.add(i)
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  
        seen.add(i)
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$.

Comments

Comments powered by Disqus