Euler 12: counting divisors of a triangle number

Question

This is the question:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

import math
def triangulated(num):
    x = 0
    for num in range(1, num + 1):
        x = x + num
    return x


l = []


def factors(g):
    for n in range(1, triangulated(g) + 1):
        if triangulated(g) % n == 0:
            l.append(n)
    if len(l) > 500:
        print(triangulated(g))
        print(l)
    l.clear()


for k in range(1, 10000000000):
    factors(k)
    print(k)

Help optimise this problem.

Answer 1

This is not a review, but an extended comment.

Project Euler problems are about math, not programming. To optimize, you need to do the math homework first:

1. The \$n\$'th triangular number is \$\dfrac{n (n+1)}{2}\$.
2. A number of divisors, aka \$\sigma_0\$, is a multiplicative function. The link to divisor function may also be interesting.
3. \$n\$ and \$n+1\$ are coprime.

That should be enough to get you started with optimization.

Answer 2

The first step of optimization is to remove the duplicate call to triangulated.

The second step of optimization is to pick only the factors that are the divisors and ignore the numbers that aren't.

Start from the reverse in the second function loop, if there is a divisor from reverse, all the factors of that divisor will definitely be a divisor, so find and all of them, so you can skip them in the loop. Eg, if you start the loop from 200, then all the factors of 200, (100, 50, 25, 4...) can be ignored by adding them to a set. In further loops do it only for the numbers that aren't present in this set. This technique is what is followed in "Seive of Erastosthenes".