Beginner's attempt for Project Euler problem 12 (highly divisible triangle number)

Question

I'm a couple weeks into learning Python and I'm working through the Project Euler problems. Problem 12 asks:

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

My problem is that my code takes far too long.

I had a list in there to store the factors but I replaced it with a counter variable to count the number of factors. It resets after looping through the divisors.

I'm not entirely sure but I feel like there is a much better way to cycle through the divisors?

How could I optimise this piece of code?

target = 100000000
counter = 0
for value in xrange(1, target + 1):
 x = (value * (value + 1))/2
 for divisor in xrange(1, x+1):
 product = x % divisor
 if product == 0:
 counter += 1
 if counter >= 500:
 print x
 sys.exit()
 else:
 counter = 0

I appreciate that similar questions have already been asked but I am hoping to gain useful 'personalised' advice from this community

Please excuse the vague variable names and the code in general...

• vnp: See here
• Martin R: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .

Answer 1

Iteration, flow control, naming, and clarity

Your iteration is a bit clumsy.

It seems that target is an arbitrarily chosen number that you picked just to act as a sufficiently large second parameter to xrange(). If you want an unbounded counting loop, itertools.count(1) would be better.

Instead of else: counter = 0, you should just set counter = 0 in the right place — just before the inner loop.

Avoid using sys.exit() — it's like killing your program with a sledgehammer. You should structure your code so that it terminates naturally.

from itertools import count
for value in count(1):
 x = (value * (value + 1))/2
 for divisor in xrange(1, x+1):
 product = x % divisor
 if product == 0:
 counter += 1
 if counter >= 500:
 break
print x

There is an idiom for counting items that meet some criterion: sum() with a generator expression.

from itertools import count
for value in count(1):
 x = (value * (value + 1)) / 2
 if 500 <= sum(1 for divisor in xrange(1, x + 1) if x % divisor == 0):
 print x
 break

As you noted yourself, your variables are poorly named. product, in particular, should be called remainder. counter is vague; divisor_count would be more helpful.

What you want to express is a loop over the triangle numbers. For even greater clarity, I'd break that out into a triangle number generator function.

from itertools import count
def triangle_numbers():
 """Generator of triangle numbers, starting with 1, 1+2, 1+2+3, ..."""
 n = 0
 for i in count(1):
 n += i
 yield n
def divisor_count(n):
 """Count of the divisors of n"""
 return sum(1 for divisor in xrange(1, n + 1) if n % divisor == 0)
print next(t for t in triangle_numbers() if divisor_count(t) >= 500)

Mathematics

Note that \$\dfrac{n(n+1)}{2}\$ is a product of two coprimes. As explained here, the divisors of such a product can be computed based on the divisors of each of its two known factors.

from itertools import count
def divisor_count(n):
 """Count of the divisors of n"""
 return sum(1 for divisor in xrange(1, n + 1) if n % divisor == 0)
for n in count(1):
 tn = n * (n + 1) // 2
 # n and (n + 1) are relatively prime. Therefore, if n is even,
 # the factors of tn can be derived from the factors of n/2 and
 # the factors of n+1. If n is odd, then the factors of tn can be
 # derived from the factors of n and the factors of ((n+1)/2).
 tn_divisor_count = (
 divisor_count(n // 2) * divisor_count(n + 1) if n % 2 == 0 else
 divisor_count(n) * divisor_count((n + 1) // 2)
 )
 if tn_divisor_count >= 500:
 print tn
 break

• omgimanerd: Good answer, but for a beginner, a generator function might be a bit much.