Problem 044


Project Euler

Pentagon numbers

Problem 44

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?


This problem works with pentagonal numbers which we can solve for n using quadratic equations

P_n = \frac {n (3n-1)} {2} 
n = \frac {1 + \sqrt(1 + 24 Pn)} {6} 
Once we found the first min_D, we verify that it is the minimum by continue searching for the next D. If any D is greater than min_D, we can ignore. If any D is less than min_D, we record the new D as min_D. Once we reach a point where
P_{n+1} - P_n > min\_D 
We can stop because all D thereafter will be larger than min_D. The program can run really slow if we don’t exclude D that is already greater than min_D when we run the verification.
Advertisements