Project Euler # Triangular, pentagonal and hexagonal in Python

Question

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

• Triangle: \$T_n=\frac{n(n+1)}{2}\$ 1, 3, 6, 10, 15, …
• Pentagonal: \$P_n=\frac{n(3n−1)}{2}\$ 1, 5, 12, 22, 35, …
• Hexagonal: \$H_n=n(2n−1)\$ 1, 6, 15, 28, 45, …

It can be verified that \$T_{285} = P_{165} = H_{143} = 40755\$.

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

from time import time


def tri_pent_hex(n):
    """yields triangles that are also pentagons and hexagons in range n."""
    triangles = set((num * (num + 1)) // 2 for num in range(1, n))
    pentagons = set((num * (3 * num - 1)) // 2 for num in range(1, n))
    hexagons = set(num * (2 * num - 1) for num in range(1, n))
    for triangle in triangles:
        if triangle in pentagons and triangle in hexagons:
            yield triangle


if __name__ == '__main__':
    start_time = time()
    print(max(tri_pent_hex(1000000)))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

Instead of generating 3 million numbers and store them in memory, you only need to generate 3 of them at a time (one triangular, one pentagonal and one hexagonal) and compare them. The lowest should be advanced to the next of its kind and the processus repeated. That way you only generate the amount of numbers you need to achieve your goal and you don't put that much pressure on your memory.

You can use 3 simples functions to generate each kind of number:

def triangular_numbers():
    n = 0
    while True:
        n += 1
        yield (n * (n + 1)) // 2


def pentagonal_numbers():
    n = 0
    while True:
        n += 1
        yield (n * (3 * n - 1)) // 2


def hexagonal_numbers():
    n = 0
    while True:
        n += 1
        yield (n * (2 * n - 1))

And combine them to generate each number that are the 3 at the same time:

def triangular_pentagonal_and_hexagonal_numbers():
    """yields triangles that are also pentagons and hexagons."""
    triangles = triangular_numbers()
    pentagons = pentagonal_numbers()
    hexagons = hexagonal_numbers()

    t = next(triangles)
    p = next(pentagons)
    h = next(hexagons)

    while True:
        if t == p == h:
            yield t
        m = min(t, p, h)
        if m == t:
            t = next(triangles)
        elif m == p:
            p = next(pentagons)
        else:
            h = next(hexagons)

You now only need to ask this function for the number you’re after:

def main():
    numbers = triangular_pentagonal_and_hexagonal_numbers()
    one = next(numbers)
    assert one == 1
    given = next(numbers)
    assert given == 40755
    return next(numbers)


if __name__ == '__main__':
    print(main())

---

Now that it works, you can simplify the first 3 functions using itertools.count:

def triangular_numbers():
    yield from ((n * (n + 1)) // 2 for n in count(start=1))


def pentagonal_numbers():
    yield from ((n * (3 * n - 1)) // 2 for n in count(start=1))


def hexagonal_numbers():
    yield from (n * (2 * n - 1) for n in count(start=1))

---

Comparing to your approach:

$ python emadboctor.py 
1533776805
Time: 1.0859220027923584 seconds.

Mine is around 20 times faster:

$ python -m timeit 'import tri_pen_hexa; tri_pen_hexa.main()'
5 loops, best of 5: 50.4 msec per loop

Answer 2

The way this was written, it was meant to steer you in the direction you did.

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

You loop the triangles to find matches in the others:

for triangle in triangles:
    if triangle in pentagons and triangle in hexagons:
        yield triangle

But if you think about it, there are more triangles than pentagons and more pentagons than hexagons. And since you need to find occurences where all 3 types match, wouldn't it be better to loop the hexagons, and find a match on the others from there?

My point is:

Don't let the way a question is asked influence the way you implement an algorithm.

Answer 3

Disclaimer: This is not a proper review. I just want to give a taste of how the Project Euler problems shall be addressed.

Given a number \$x\$, it is triangular if there exist \$n\$ such that

\$\dfrac{n(3n-1)}{2} = x\$

Solving for \$n\$, gives \$n = \dfrac{1 + \sqrt{1 + 24x}}{6}\$

Similarly, for it to be pentagonal, there must be \$k\$ such that

\$\dfrac{k(k+1)}{2} = k\$

Solving for \$k\$ gives \$k = \dfrac{-1 + \sqrt{1 + 8k}}{2}\$

It means that \$1 + 8x\$ and \$1 + 24x\$ must simultaneously be perfect squares. We may stop here. Generate hexagonal numbers and test them against a condition above. It is already better than the solution above (we only need to generate one sequence vs three), but just by a linear factor; besides, testing for something being a perfect square does not feel comfy. Let's continue.

We are after integer \$u\$ and \$v\$ such that \$1 + 8x = u^2\$ and \$1 + 24x = v^2\$. Excluding \$x\$ results in \$v^2 - 3u^2 = -2\$. This is a variation of a famous Pell's equation, and it is where a real efficiency comes from: the solutions of Pell's equation grow exponentially fast.

Now, solve the Pell equation (it is trivial) for \$u_i, v_i\$. Recreate \$x_i\$. Test it to be a hexagonal number (yet another quadratic).