Solving Project Euler #45

Nov 14 2025

Introduction

Project Euler is a repository of fantastic computational problems that require a modest to heavy degree of mathematical think…

Solving Project Euler #45

Nov 14 2025

Introduction

Project Euler is a repository of fantastic computational problems that require a modest to heavy degree of mathematical thinking. As someone who enjoys programming and math, I love Project Euler. In this post we’ll discuss a solution to a fun problem of theirs that I solved the other day, problem 45.

But first, a disclaimer:

From the Project Euler FAQ: “[...] the rule about sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems. Problems 1 to 100 provide a wealth of helpful introductory teaching material and if you are able to respect our requirements, then we give permission for those problems and their solutions to be discussed elsewhere.”

Emphasis mine. With that noted, let’s discuss the problem.

Problem statement

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

where is a positive integer. So, for example, .

It can be verified that .

Find the next triangle number that is also pentagonal and hexagonal.

Feel free to try and solve this yourself in another tab. Maybe you’ll end up with a different solution than mine, in which case I’d love to hear about it 🙂

Sketching out a solution

We have two equations in three variables, and some very useful domain constraints. Let’s say the triangular number equals the pentagonal number equals the hexagonal number. And so:

We also have some useful domain constraints. are positive integers, which gives us these inequalities

Expand out the equations:

Expressing `t` in terms of `h`

Let’s focus on the first one:

where . The only way for two integers to satisfy that last equation while both being positive is for them to be equal to each other, and so we get .

We’ve turned one of our variables into a function of the other, ! Let’s do the same for .

Expressing `p` in terms of `h`

The final step above was me expanding out all the brackets and pushing everything over to the left. I also kept the parens around the last two terms on the left because I wanted to make the equation look like — you guessed it — a quadratic equation in .

Let’s apply the quadratic formula:

Note that I flipped the order of the terms inside the parens around so I could get rid of the negative sign outside the parens.

There are two solutions here, but we can discard the one that looks like

because it’s negative! To see why, note that the denominator is positive and both terms in the numerator are negative.

And so we get a one-to-one mapping from to :

This is way messier than the earlier mapping . But now we have enough to write our solver program.

Coding it up

Here’s some Python code that implements our search for the next solution:

1from math import sqrt
2
3def sqrt_discriminant(m):
4    return sqrt(12*(4*m*m - 2*m) + 1)
5
6def nth_triangle_num(n):
7    return n*(n+1)//2
8
9h = 144
10while True:
11    s = sqrt_discriminant(h)
12    if int(s) == s:
13        numerator = int(s) + 1
14        if numerator % 6 == 0:
15            t = 2*h - 1
16            p = numerator // 6
17            print(nth_triangle_num(t))
18            break
19    h += 1

We’re doing a simple linear search starting from , because, as the problem requires, we’re searching for the next solution after . Within our search, we ignore all values of for which the expression

is not an integer. For it to be an integer:

the numerator must be an integer
...and it must be divisible by .

For the numerator to be an integer, the quantity must be a perfect square. That’s what the int(s) == s check is for. The rest is pretty straightforward — once we find a value for that yields an integer value for , we find the corresponding value of , print the values and then break out of our otherwise-infinite while loop.

The above code spits out an answer almost immediately on my laptop.

An aside: it feels like overkill to use the Python standard library’s math.sqrt function just to check if a number is a perfect square. As it turns out, we don’t need to use it! You can always write an integer sqrt implementation that uses binary search to find the square root of a positive integer, rounded down to the nearest integer, and then check that squaring that integer equals our original number. I leave this as an exercise to the reader.

Conclusion

I hope you enjoyed this dissection of a not-terribly-difficult but nevertheless very enjoyable problem. Thank you for reading!

P.S. Hover to reveal the answer, if you’re curious: the next triangle number that is also pentagonal and hexagonal is 1533776805.