     (37 votes, average: 4.84 out of 5) Loading...

## Project Euler 45 Solution ## 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: $\frac{1}{2} n(3n-1)=m(2m-1)$

As documented in the article by Wolfram on Hexagonal Pentagonal Numbers we can reduce this equation as: $(6n-1)^2-3(4m-1)^2=-2$

This is a diophantine equation that expands as such: $36n^2-48m^2-12n+24m$

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

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

Project Euler 45 Solution last updated