Revisiting Project Euler #45

Dec 20 2025

In this blog post I revisit a fun Project Euler problem. The solution I detailed in this previous blog post worked but was a little clunky, involving checking if a quantity was a perfect square. I submitted that blog post to Hacker News for discussion, and one of the comment threads on that submission opened up an interesting line of discussion — what if we just modeled this problem as a combination of iterators?

I translated the approach discussed in the above comments to Python, and got:

 1# generators for pentagonal and hexagonal numbers
 2def pentagonal():
 3    i = 1
 4    while True:
 5        yield i*(3*i-1)//2
 6        i += 1
 7def hexagonal():
 8    i = 1
 9    while True:
10        yield i*(2*i-1)
11        i += 1
12
13# given two generators, advances both until a common element is found, then
14# yields that element
15def combine(g1, g2):
16    while True:
17        l, r = next(g1), next(g2)
18        while l != r:
19            if l < r:
20                l = next(g1)
21            else:
22                r = next(g2)
23        yield l
24
25if __name__ == '__main__':
26    seen = 0
27    for num in combine(pentagonal(), hexagonal()):
28        print(num)
29        seen += 1
30        if seen == 4:  # change this to the number of desired outputs
31            break

What's going on here? To start with, we're defining a function combine that takes as input two existing generators and only yields elements that are members of both generators. This is ensured by the while l != r loop that precedes the yield l.

Fair enough, but how come the above code makes no mention of triangle numbers at all? Seems like we should define a generator for triangle numbers, and then do something like this?

for num in combine(triangle(), combine(pentagonal(), hexagonal())):
    pass  # seen = 0 ...

It turns out that we don't need to! A nice insight from the previous blog post that eluded me until I re-read the Hacker News thread (in particular, this comment) was that every hexagonal number is a triangle number. Recall that if the $t^{th}$ triangle number equals the $h^{th}$ hexagonal number, then $t = 2h - 1$ must be true.

We can read this property in reverse: given the $h^{th}$ hexagonal number, there always exists a corresponding $t = 2h-1$ such that the $t^{th}$ triangular number equals it. In other words, every hexagonal number is a triangle number. Which means that it's enough to check for numbers that are both hexagonal and pentagonal. The "triangle" requirement will automatically be satisfied 🙂.

This approach is much more readable than the one in the previous blog post, but is it more performant? As it turns out, this approach runs faster on my machine than the previous approach! It's not instantly obvious to me why, without inspecting the generated CPython bytecode, but I speculate that it has to do with the expensiveness of computing the floating-point square root of a number.