Problem #44 concerns a somewhat obscure class of numbers known as the pentagonal numbers. It is also (in my opinion) the most difficult question in the first 50 problems of Project Euler, and the only one that I have yet to find a solution for that runs in under a minute. (I’m a very sloppy programmer right now) Here’s the problem:
Project Euler Problem 44: Pentagon numbers
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?
As stated above, my solution to this problem is extremely inefficient, and I definitely need to come back to this problem at some point. Here’s my solution:
Solution #1: Very Inefficient Brute Force Approach
We list all of the pentagonal numbers up to an arbitrary upper bound and check all quadruples of pentagonal numbers for the given property. To optimize this search a bit, I did casework on the pentagonal number which is the sum of two smaller pentagonal numbers first, and then I did casework on the pentagonal number which is the smaller of the two summand pentagonal numbers second. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #44
'''
import time
def projectEulerProblemFortyFour(n):
myPentagons = [1,5]
c = 3
minDifference = 10**30
while(c<=n):
myPentagons.append(c*(3*c-1)/2)
c+=1
for a in myPentagons:
for b in myPentagons:
if(2*b<=a):
if (a-b) in myPentagons:
if (a-2*b) in myPentagons:
if (a-2*b) < minDifference:
minDifference = (a-2*b)
else:
break
return minDifference
start = time.time()
print projectEulerProblemFortyFour(4000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
5482660
--- 227.999250889 seconds ---
for input of n = 4000
'''
Yikes! That took nearly 4 minutes to run, nearly 4 times the maximum time that all solutions on Project Euler should run within. I definitely need to come back to this problem at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 