8
\$\begingroup\$

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

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Good answer, but for a beginner, a generator function might be a bit much. \$\endgroup\$ – omgimanerd Jul 24 '17 at 18:19

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.