python - time to execute a loop increases suddenly

Question

I have some small piece of software that calculates the number of factors of each triangle number to see what is the first one of them has more than X number of factors (yes, it's a projecteuler problem, number 12,, although i didn't solve it yet)... as am trying making X some random values to see what the code does and in how much time, I noticed something strange (to me at least): until X=47 the execution time increases in obviously normal way, but when X = 48 it increases more than normal, and function calls are much greater than the rate, it (explodes) if I would say that.. why does it do that??

the code:

def fac(n):
    c=0
    for i in range (1,n+1):
        if n%i==0:
            c=c+1
    return c

n=1

while True:
    summ=0
    for i in range (1,n+1):
        summ=summ+i
    if fac(summ)>X:
        break
    n=n+1

print summ

and when profiling:

when X=45 :  314 function calls in 0.027 CPU seconds
when X=46 :  314 function calls in 0.026 CPU seconds
when X=47 :  314 function calls in 0.026 CPU seconds
when X=48 :  674 function calls in 0.233 CPU seconds
when X=49 :  674 function calls in 0.237 CPU seconds

I assume that if I continued I would meet other points that system calls increases and time increases suddenly, and previously there were points like that but time was so small so it did't matter so much.. Why function calls suddenly increases?? Isn't it supposed just to call the function one more time for the new value??

P.S. am using cProfile as a profiler, and X in the code here is just for demonstration, I write the value directly in the code... thank you in advance...

Answer 1

Have you looked at the actual values involved?

The first triangular number with more than 47 factors is T(104) = 5460, which has 48 factors.

But the first triangular number with more than 48 factors is T(224) = 25200, which has 90 factors. So no wonder it takes a lot more work.

If your code runs up to T(n), then it calls range 2n times and fac n times, for a total of 3n function calls. Thus for T(104) it requires 312 function calls, and for T(224) it requires 672 function calls. Presumably there are 2 function calls of overhead somewhere that you're not showing us, which explains the profiling results you get.

---

Your current strategy is not going to get you to the answer for the Project Euler problem. But I can give some hints.

• Do you have to start over again with summ=0 each time you compute a triangular number?
• Do you have to loop over all the numbers up to n in order to work out how many divisors it has? Could there be a quicker way? (How many divisors does 2¹⁶ = 65536 have? Do you have to loop over all the numbers from 1 to 65536?)
• How many divisors do triangular numbers have? (Look at some small triangular numbers where you can compute the answer.) Can you see any patterns that would help you compute the answer for much bigger triangular numbers?