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

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...

• See here – vnp Jul 24 '17 at 17:43
• 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. – Martin R Jul 24 '17 at 19:23

## 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

• Good answer, but for a beginner, a generator function might be a bit much. – omgimanerd Jul 24 '17 at 18:19