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

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