Project Euler Problem 45 As a self-teaching Python beginner for almost 4 months, I have mostly been doing online challenges including Project Euler problems.

Problem 45 asks:


  Triangle, pentagonal, and hexagonal numbers are generated by the
  following formulae:
  
  $$
\begin{array}{lll}
\textrm{Triangle}   &amp; T_n=n(n+1)/2  &amp; 1, 3,  6, 10, 15, \ldots  \\
\textrm{Pentagonal} &amp; P_n=n(3n−1)/2 &amp; 1, 5, 12, 22, 35, \ldots  \\
\textrm{Hexagonal}  &amp; H_n=n(2n−1)   &amp; 1, 6, 15, 28, 45, \ldots \\
\end{array}
$$
  
  It can be verified that \$T_{285} = P_{165} = H_{143} = 40755\$.
  
  Find the next triangle number that is also pentagonal and hexagonal.


I encountered this problem and was able to write the code without much problem although most of the solutions I write are mostly brute force. However I am not satisfied with the time the coding took to find the answer as it took 530.7 seconds to find the solution with this code:

import time

startTime = time.time()

limit = 1000000
triangle = []
pentagonal = []
hexagonal = []
triangle_number = []

class Shape:
    def __init__(self, term):
        self.term = term

    def triangle(self):
        return int(self.term * (self.term + 1) / 2)

    def pentagonal(self):
        return int(self.term * (3 * self.term -1) / 2)

    def hexagonal(self):
        return int(self.term * (2 * self.term - 1))

def generate():
    for terms in range(1, limit + 1):
        product = Shape(terms)

        triangle.append(product.triangle())
        pentagonal.append(product.pentagonal())
        hexagonal.append(product.hexagonal())

def main():
    generate()

    for _, terms in enumerate(hexagonal):
        if len(triangle_number) == 3:
            break
        elif terms in triangle and terms in pentagonal:
            triangle_number.append(terms)
            print(terms)

    print(triangle_number)
    print(time.time() - startTime, "seconds")

main()


I am aware that using the class is unecessary for this problem, but I want to include it as a practice of getting used to writing solutions that require classes.

Alternatively I have re-written another solution of this problem without any classes included but keeping the same style, however it still took 328.2 seconds.

So what suggestions are there to improve the code to run faster? I have tried to review other solutions from the solution page however I do not understand how it was simplified so much to make it run more efficient.
Arithmetic

Project Euler questions are meant to educate you about both mathematics and programming.  It would be a good idea to understand what these triangular, pentagonal, and hexagonal numbers actually are, rather than blindly applying the given formulas.

One performance improvement would be to find a way to generate successive elements of each sequence without plugging \$n\$ into the formulas, which involve division.  (Division tends to be slow.  Floating-point division, using the / instead of the // operator, is even slower, and it also causes you to have to cast the result back to an int.)

If you take the formula for pentagonal numbers \$P_n\$, you can figure out another formula for the difference between successive elements in the sequence.

$$
\begin{align}
P_n &amp;= \frac{n(3n-1)}{2} = \frac{3n^2-n}{2} \\
P_{n+1} &amp;= \frac{(n+1)(3(n+1)-1)}{2} = \frac{(n+1)(3n+2)}{2} = \frac{3n^2+5n+2}{2} \\
P_{n+1} - P_n &amp;= \frac{(3n^2+5n+2)-(3n^2-n)}{2} = \frac{6n+2}{2} = 3n + 1
\end{align}
$$

If you do the same for triangular, square, and hexagonal numbers, you'll find:

$$
\begin{align}
T_{n+1} - T_n &amp;= n+1 \\
P_{n+1} - P_n &amp;= 3n+1 \\
H_{n+1} - H_n &amp;= 4n+1
\end{align}
$$

Considering that square numbers would be \$S_{n+1} - S_n = 2n+1\$, you can see a pattern to produce polygonal numbers in general.

Algorithm

Your strategy is to generate a million elements of each sequence and find the elements that exist in common.

First of all, one million is an arbitrary limit.  You might need fewer than a million to find the next element in common (in which case you've wasted execution time), or you might need more than a million (in which case you would have to raise the limit and run your code again).  It would be nice if your algorithm did not have to rely on a guess.

Secondly, the millionth hexagonal number is certainly going to be much larger than the millionth triangular number.  There is no way that the millionth hexagonal number is going to coincide with anything, so that's wasted work.

Thirdly, you store the sequences as lists.  Searching a list (e.g. terms in triangle) involves inspecting every element in that list (a so-called O(n) operation).  Searching a set takes only O(1) time.  Therefore, simply changing


triangle = []
pentagonal = []
hexagonal = []



and


        triangle.append(product.triangle())
        pentagonal.append(product.pentagonal())
        hexagonal.append(product.hexagonal())



to

triangle = set()
pentagonal = set()
hexagonal = set()


and

        triangle.add(product.triangle())
        pentagonal.add(product.pentagonal())
        hexagonal.add(product.hexagonal())


brings the execution time down from hundreds of seconds down to about 2 seconds.  Better yet, your main() function could be simplified using the set intersection operator &amp;:

def main():
    generate()
    triangle_number = triangle &amp; pentagonal &amp; hexagonal
    print(sorted(triangle_number))
    print(time.time() - startTime, "seconds")


Pythonicity

Be consistent with your naming.  If you write "pentagonal" and "hexagonal", then use "triangular" rather than "triangle".

The Shape class shouldn't exist at all.  It's just a very weird and cryptic way to call three functions that take a numerical parameter.

for _, terms in enumerate(hexagonal) is a nonsensical use of enumerate.  If you're going to throw away the index anyway, why not just write for terms in hexagonal?  And why is your iteration variable pluralized (terms rather than term)?

Your code would be much more expressive if you could say "give me the next pentagonal number".  A good way to do that in Python is to define a generator, so that you can write next(pentagonal_numbers).

Suggested solution

from itertools import count

def polygonal_numbers(sides):
    result = 0
    for n in count():
        yield result
        result += (sides - 2) * n + 1

tt, pp, hh = polygonal_numbers(3), polygonal_numbers(5), polygonal_numbers(6)
t = p = 0 
for h in hh:
    while p &lt; h: p = next(pp)
    while t &lt; h: t = next(tt)
    if t == p == h &gt; 40755:
        print(h)
        break


If you take into account that every hexagonal number is also a triangular number, you can ignore the triangular numbers altogether:

from itertools import count

def polygonal_numbers(sides):
    result = 0
    for n in count():
        yield result
        result += (sides - 2) * n + 1

pentagonal_numbers = polygonal_numbers(5)
p = 0
for h in polygonal_numbers(6):
    while p &lt; h: p = next(pentagonal_numbers)
    if p == h &gt; 40755:
        print(h)
        break


My last solution takes about 50 milliseconds to run on my machine.