// 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.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|1533776805|

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