Project Euler 45: Find the next triangle-pentagonal-hexagonal number after 40755
Project Euler 45 Problem Description
Project Euler 45: Triangle, pentagonal, and hexagonal numbers are generated by the following formula:
| Triangle | Tn=n(n+1)/2 | 1, 3, 6, 10, 15, … | ||
| Pentagonal | Pn=n(3n−1)/2 | 1, 5, 12, 22, 35, … | ||
| Hexagonal | Hn=n(2n−1) | 1, 6, 15, 28, 45, … |
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.
Analysis
Note that Hexagonal numbers are a subset of Triangle numbers so we only determine the first occurrence of Pn = Hm to find our answer.
We can solve this mathematically by asserting that if Pn = Hm then:
As documented in the article by Wolfram on Hexagonal Pentagonal Numbers we can reduce this equation as:
This is a diophantine equation that expands as such:
which we will feed into our favorite Diophantine equation solver and produce the results:
P0 = 0
H0 = 0
Pn+1 = 97·Pn + 112·Hn - 44
Hn+1 = 84·Pn + 97·Hn - 38
Replace P0 and H0 with our starting index and this problem is solved instantly. Note that the starting values for p and h were defined in the problem.
A relevant sequence is documented as Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A046180: Hexagonal pentagonal numbers. A Python program is listed in the comments section to generate this sequence.
Project Euler 45 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 45 Solution Python 2.7 source.
Afterthoughts
- See also, Project Euler 44 Solution:
- The following program will print the first 8 numbers in the sequence:
p = 1
h = 1
for n in range(1, 9):
print n, h*(2*h - 1)
px = 97*p + 112*h - 44
h = 84*p + 97*h - 38
p = px
Discussion
No comments yet.