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)
        pentagonals_set.add(p_k)


expected_answer = 5482660
solutions.problem44.solve()

Compute the answer to Project Euler’s problem #44