(37 votes, average: 4.86 out of 5)
Loading...
Project Euler 44: Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.
Project Euler 44 Problem Description
Project Euler 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 is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?
Analysis
When the problem asks for D = |Pk − Pj| to be minimized it simply means the numerically closest pair which, by our method, is the first occurrence found.
We search by sum and difference instead of by Pj and Pk and this caused some confusion. This was the best we we could think of to minimize D without having to force comparisons.
The variable names have been changed to make this more clear:
s is the sum Pk + Pj
Pj is, well, Pj
s-Pj is Pk
D is s-2*Pj which is simplified from (s-Pj)-Pj
The Trinket provided takes about 12 seconds to run.
Project Euler 44 Solution
Runs < 0.210 seconds in Python 2.7.
Use this link to get the Project Euler 44 Solution Python 2.7 source.
Afterthoughts
- See also, Project Euler 45 Solution:
My code to solve the problem:
import math
def is_pentagonal_number(num):
n = (0.5 + math.sqrt(0.25 – 6.0 * (-num))) / 3.0
return n == int(n)
def project_euler_44():
last_number_1 = 1
n1 = 2
best_distance = 1000 * 1000 * 1000
while True:
current_number_1 = n1 * (3 * n1 – 1) // 2 #first pentagonal number
if current_number_1 – last_number_1 > best_distance:
break
continue_to_outer_loop = False
n2 = n1 – 1
while n2 > 0:
current_number_2 = n2 * (3 * n2 – 1) // 2
if current_number_1 – current_number_2 > best_distance:
continue_to_outer_loop = True
break
if is_pentagonal_number(current_number_1 + current_number_2) and is_pentagonal_number(current_number_1 – current_number_2):
tmp_distance = current_number_1 – current_number_2
if best_distance > tmp_distance:
best_distance = tmp_distance
n2 -= 1
n1 += 1
if continue_to_outer_loop:
continue
last_number_1 = current_number_1
return best_distance
print(project_euler_44())
Posted by Yuto | October 30, 2023, 5:17 PMMY SOLUTION HARDLY TAKES 1.5sec
def is_pentagonal(n):
if (1+(24*n+1)**0.5) % 6 == 0: #function to check if the number is pentagonal number or not
return True
return False
flag = True
i = 1
while flag:
for j in range(1, i):
a = i*(3*i-1)/2
b = j*(3*j-1)/2
if is_pentagonal(a+b) and is_pentagonal(a-b):
print (a-b)
flag = False
break
i += 1
Posted by Sinchan | November 2, 2019, 10:26 PMIn the comparison you tested if p-n and p-2*n belonged to the set of pentagonals. why not p+n?
Posted by Marcio | December 17, 2015, 3:42 AMBecause we are searching for the sum and D, not Pk and Pj. I revised the description to make this more clear.
Posted by Mike Molony | October 18, 2016, 1:38 AM