# 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(3n-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 - Pj|$$ is minimised; what is the value of $$D$$?

## Solution Discussion¶

This solution is really a brute-force search with some sensible ordering constraints to remove redundant work that would otherwise occur.

Iterate through a two-dimensional 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_{k-1}$$ 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 reverse-iterate 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)

solutions.problem44.solve()