Project Euler Problem #12 - Highly divisible triangular number

Question

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:
 list.append(j)
 if len(list) == 500:
 print(n+i)
 break
 i = i + n

euler_12(num)

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.

• Peter Taylor: The code as posted fails to run due to NameError: name 'num' is not defined on the last line.
• Peilonrayz: @PeterTaylor That's clearly an example of how to use the code. Just change num to the num you want.
• Peter Taylor: @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.
• miracle173: -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.
• Simon Forsberg: This question is being discussed on meta

Answer 1

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
print(euler_12())

---

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:
 list.append(j)

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.