CODEWITHSUNDEEP
pythonperformancepython-3.xmath
August Williams
August Williams

Reputation: 929

Can I more efficiently search for the first triangle number with >500 divisors? Why is my current implementation slow?

I'm working on Project Euler problem 12

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

I know for certain that it can produce correct answers for smaller numbers. For example if I replace > 500 with == 6, the output result I get is an expected 28.

For 500 divisors, about two minutes into the execution, the program begins to run very slowly. I believe every variable here is being overwritten at each iteration. Why is it slow? I have tried separating into functions to make use of local variables, but this doesn't improve the running time.

Code:

import sys

currentNumber, currentCalculationNumber, divisorCount, naturalNumber = 1, 1, 0, 1

while True:

    while currentCalculationNumber <= currentNumber:
        if currentNumber % currentCalculationNumber == 0:
            divisorCount += 1
        currentCalculationNumber += 1
    if divisorCount > 500:
        print ("ANSWER: " , currentNumber)
        sys.exit(0)

    naturalNumber += 1
    currentNumber += naturalNumber
    currentCalculationNumber, divisorCount = 1, 0

Upvotes: 0

Views: 180

Answers (2)

AGN Gazer
AGN Gazer

Reputation: 8378

I agree with @Prune's answer but here is a faster version of your brute-force algorithm:

VERSION 1 (slower, brute-forse using numpy)

import numpy as np
i = 1
f = lambda N: (N * (N + 1)) // 2
ndmax = 0

while True:
    t = f(i)
    p = np.arange(1, t + 1)
    r = np.mod(t, p)
    nd = p.size - np.count_nonzero(r) + 1
    if nd > ndmax: # track progress
        ndmax = nd
        print((i, t, nd))
    if nd > 500:
        print ("ANSWER: " , t)
        break
    i += 1

VERSION 2 (Fast, using sympy's divisor_count)

from sympy import divisor_count
import numpy as np
i = 1
f = lambda N: (N * (N + 1)) // 2
ndmax = 0

while True:
    t = f(i)
    nd = divisor_count(t)
    if nd > ndmax: # track progress
        ndmax = nd
        print((i, t, nd))
    if nd > 500:
        print ("ANSWER: " , t)
        break
    i += 1

For more details see divisor_count and reference therein.

Upvotes: 1

Prune
Prune

Reputation: 77860

The slowness is from your brute-force method of counting divisors. The solution is on the order of 10^8, so you're iterating through that inner while loop on the order of 10^16 times: the nested loops make an O(n) process. This is going to take a while. You need something more efficient, at least O(n log(n) ).

One of the purposes of Project Euler is to get us to investigate more efficient algorithms. For this one, you'll likely want to use the divisor function, which will require any of the numerous prime-generation functions.

You should develop a "bag of tricks" module that you import for most problems. In fact, you should already have one that generates prime numbers, from earlier problems (assuming that you're attacking them in some order). If not, try this one.

Upvotes: 3

Related Questions