Project Euler Problem 44 Statement
Pentagonal numbers are generated by the formula, $P_n=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 - P_j|$ is minimised; what is the value of $D$?
Solution
Iterates through pentagonal numbers from position K+1 to N-1 and for each number, it checks if either:
- The sum of the current pentagonal number and the K-th previous pentagonal number is pentagonal
- The difference between the current pentagonal number and the K-th previous pentagonal number is pentagonal.
If either condition is true, it prints the current pentagonal number.
See the solution to problem 45 for an explanation for determining if a number is pentagonal.
HackerRank version
HackerRank Project Euler 44 wants the sum and difference of a K range of pentagonal numbers.
Python Source Code
import math
L = 10**6
is_pentagonal = lambda x: (math.sqrt(24*x+1)+1) % 6 == 0
ps = [(3*i*i - i) // 2 for i in range(1, L+1)]
N, K = map(int, input().split())
for n in range(K+1, N):
if is_pentagonal(ps[n]+ps[n-K]) or is_pentagonal(ps[n]-ps[n-K]):
print(ps[n]) Last Word
The original Project Euler asked for "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$?
This always caused confusion. Project Euler only accepts a string as a response to an answer attempt (usually a number). Since there are many pairs found they devised a way to just enter one number. That number was $D$. Just the closest pair which was simply the first pair found as we searched upward. The distance between pairs increases as we continue the search.