Project Euler Problem 44 Solution

1. Precomputing Pentagonal Numbers

The code starts by computing the first \(10^6\) pentagonal numbers using the formula: $$P(i) = \frac{3i^2 - i}{2}$$ This is done with a list comprehension:

L = 10**6
ps = [(3*i*i - i) // 2 for i in range(1, L+1)]

Here, ps is a list containing the first \(L\) pentagonal numbers, where the \(i\)-th pentagonal number is calculated using the formula.

2. Creating a Set for Fast Lookup

The program converts the list of pentagonal numbers into a set:

px = set(ps)

Storing the pentagonal numbers in a set allows for fast \(O(1)\) membership tests, which is essential for checking if a given number is pentagonal.

3. Reading Input Parameters

The program reads two integers \(N\) and \(K\) from input:

N, K = map(int, input().split())

Here, \(N\) sets an upper bound for the indices of the pentagonal numbers to consider, and \(K\) is the fixed difference in indices between the two numbers in each pair.

4. Iterating Over Candidate Pairs

The code then iterates over candidate pairs of pentagonal numbers:

for n in range(K+1, N):
    if (ps[n] + ps[n-K]) in px or (ps[n] - ps[n-K]) in px:
        print(ps[n])

In this loop:

• Loop Range: The loop variable \(n\) runs from \(K+1\) to \(N-1\). For each \(n\), the code considers the pair: $$\big(P(n-K),\ P(n)\big)$$
• Condition Check: The code checks whether the sum or the diffeence of the two pentagonal numbers, $$P(n) + P(n-K)$$ $$P(n) - P(n-K)$$ is in the set \(px\) (i.e., is pentagonal).
• If either condition is met (using the logical or), the program prints the larger pentagonal number, \(P(n)\).

The use of precomputation and set lookups ensures that these membership tests are fast, which is critical given the potentially large number of checks.