// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (35 votes, average: 4.83 out of 5)
Loading...

Project Euler Solutions

Project Euler 45 Solution

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.
download arrowUse this link to get the Project Euler 45 Solution Python 2.7 source.

Project Euler 45

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

Discussion

No comments yet.

Post a comment