Project Euler Problem 44: Pentagon Numbers¶
The source code for this problem can be found here.
Problem Statement¶
Pentagonal numbers are generated by the formula, \(P_n = \frac{n(3n1)}{2}\). The first ten pentagonal numbers are:
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  Pj\) is minimised; what is the value of \(D\)?
Solution Discussion¶
This solution is really a bruteforce search with some sensible ordering constraints to remove redundant work that would otherwise occur.
Iterate through a twodimensional collection of pentagonal numbers, \(\lbrace (p_j, p_k) \rbrace\), and simply test whether both the numbers \(p_j + p_k\) and \(p_j  p_k\) are pentagonal.
By iterating over \(p_k\) first, and in ascending order, and then \(p_j\) second in descending order from \(p_{k1}\) to \(p_1\) we will guarantee that \(p_k \gt p_j\). Therefore, we will only consider positive values for \(p_k + p_j\) and \(p_k  p_j\).
Further, by initialising \(p_j\) to a value as close to \(p_k\) as possible and then increasing the distance between \(p_j,p_k\) at each iteration, the first candidate \((p_j, p_k)\) satisfying the search conditions will have minimal distance \(p_j  p_k\) for the current value of \(p_k\).
Solution Implementation¶
from lib.sequence import Pentagonals
def solve():
""" Compute the answer to Project Euler's problem #44 """
pentagonals = Pentagonals()
visited_pentagonals = [] # will reverseiterate over this list {p_j}
pentagonals_set = set() # for testing whether sums or differences of pentagonal numbers are pentagonal numbers
for p_k in pentagonals:
for p_j in reversed(visited_pentagonals):
if (p_k  p_j) in pentagonals_set and (p_k + p_j) in pentagonals:
return p_k  p_j # p_k > p_j => p_k  p_j = p_k = p_j
visited_pentagonals.append(p_k)
pentagonals_set.add(p_k)
expected_answer = 5482660

solutions.problem44.
solve
()¶ Compute the answer to Project Euler’s problem #44