Project Euler Problem #12

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?

I know this question has been asked here many times regarding long run times (my problem) but I don't understand the explanations so here is my take;

def euler_12(num):
    i = 0
    for n in range(1,num):
        list= []
        for j in range(1, n**2):
            if (n+i) % j == 0:
                if len(list) == 500:
        i = i + n

I understand this is probably a very poor way to do it, and it also takes forever to run, so any comments are highly appreciated.

  • 1
    \$\begingroup\$ The code as posted fails to run due to NameError: name 'num' is not defined on the last line. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 7:30
  • 3
    \$\begingroup\$ @PeterTaylor That's clearly an example of how to use the code. Just change num to the num you want. \$\endgroup\$ – Peilonrayz Apr 25 '18 at 8:35
  • 1
    \$\begingroup\$ @Peilonrayz, which is what? The problem which this is attempting to solve is quite small and specific, so the code which solves it should run standalone without requiring the user to guess a value for an undocumented parameter. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 8:38
  • 4
    \$\begingroup\$ -1 from me because the Code does not solve the problem. I was not able to find the result. for small values of num the program finishes without printing a result and for larger numthe program hangs up without printing a result. \$\endgroup\$ – miracle173 Apr 26 '18 at 16:18
  • 2
    \$\begingroup\$ This question is being discussed on meta \$\endgroup\$ – Simon Forsberg May 11 '18 at 9:37

Split up your code. You're:

  1. Generating all triangle numbers.
  2. Factorizing all triangle numbers.
  3. Displaying when you get the first triangle number with 500 or more factors. And ending the program.

These sound like some good functions to me.

And so you could use:

def triangle_numbers():
    return ...

def factors(number):
    return ...

def euler_12():
    for number in triangle_numbers():
        if len(factors(number)) >= 500:
            return number


To generate all triangle numbers you can use itertools.count and itertools.accumulate. If you're not running Python 3 you can implement accumulate, or manually perform the calculations yourself.

import itertools

# Python 3
def triangle_numbers():
    return itertools.accumulate(itertools.count())

# Python 2
def triangle_numbers():
    sum = 0
    for i in itertools.count():
        sum += i
        yield sum

Currently your factors code would be:

def factors(num):
    list= []
    for j in range(1, num**2):
        if (num) % j == 0:

This has a couple of problems.

  1. You don't need to use num ** 2. The largest maximum you need is num + 1.
  2. You can use int(num ** 0.5) + 1.

    This is as \$\sqrt{n}^2 = n\$. With the equation \$n = a * b\$, allowing you to find \$a\$ when you've found \$b\$.

And so you can use:

def factors(num):
    for div in range(1, int(num**0.5) + 1):
        if num % div == 0:
            yield div
            other = num // div
            if other != div:
                yield other

This has change this piece of code from \$O(n^2)\$ to \$O(\sqrt{n})\$. So if \$n = 10000\$, you'd only need to check \$100\$ numbers, rather than \$100000000\$.

You will also have to change the return value of factors to a list to use len.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.