CODEWITHSUNDEEP
pythonmath
Rikpython
Rikpython

Reputation: 1

How to improve running time for Project Euler exercises

I am experiencing some running time issues with Project Euler. The exercise can be found here: Project Euler exercise 12. My solution is: 

def triangularnr(n):
    T_n = n*(n+1)/2     #Function to calculate triangular numbers 
    return T_n

for n in range(1,1*10**8):  #Nr with over 500 divisors is large, large range required
    count = 2   #Every nr is divisible by itself and by 1, thus initially count = 2 
    for i in range(2,int(triangularnr(n))): #Defining i to find divisors 
        if triangularnr(n)%i == 0:
            count+=1 #Incrementing count to count the nr of divisors 
    if count > 500: #If a triangularnr has over 500 divisors we want to print the nr
        print(triangularnr(n))
        break

I've tried to optimize the code by reducing the nr of steps required and by using a mathematical formula for triangular numbers. My code works for 5 divisors, but it takes ages to find 500 divisors. I've let the code run for 3 hours yesterday and still no output. Should I let the code run for more than 3 hours, or will the output never be printed as there is something wrong with my code?

Upvotes: 0

Views: 68

Answers (2)

Heike
Heike

Reputation: 24420

This is more a mathematical answer than a programming one, but one way to improve your algorithm is to think about how to determine the number of divisors of a number.

The brute force way would be to iterate over all numbers smaller than your test number and check every one of them but this is not very efficient for large numbers as you found out.

A more efficient way would be to consider the prime decomposition of your test number. Any integer can be written as the product of prime numbers. Suppose that N has prime factors p1, p2,... , pn with exponents k1, k2,... ,kn, i.e. N == p1**k1 * p2**k2 * ... * pn**kn, then the number of divisors of N is equal to (k1+1)*(k2+1)*...*(kn+1). So finding the number of divisors is equivalent to finding the prime factors of a number which restricts the number of integers you need to check considerably.

Another thing to realize is that if integers N1 and N2 have no prime factors in common (which is the case for N and N+1), the number of divisors of N1*N2 is equal to the number of divisors of N1 times the number of divisors of N2. This means that since you are considering numbers of the form N*(N+1)//2 and since N and N+1 have no prime factors in common, the number of divisors of your triangular numbers is equal to the product of the number of divisors of N//2 and the number of divisors of N+1 for even N, and to the product of the number of divisors of N and the number of divisors of (N+1)//2 for odd N.

Upvotes: 2

Krish
Krish

Reputation: 1081

Firstly, as a rule of thumb, for most project Euler exercises your code should take less than a minute to run. Remember, questions on project Euler challenge your ability to come up with interesting solutions, not to brute force answers.

Your algorithm is inefficient because:

  • Triangular numbers increase by the square (expand n*(n+1)/2)
  • Your algorithm loops through every triangular number

These two things mean that your algorithm probably has a complexity of n^3. Eg. doubling the required number of factors increases the search space by a factor of 8.

One tip that might prove useful is that if you have two numbers, a and b, the number of factors of a*b is equal to the number of factors of a multiplied by the number of factors of b. For example 5 has two factors (5, 1) and 14 has 4 factors (1, 2 ,7 and 14). From this we know that 5*14 has 2*4 factors, without having to search the numbers from 1 to 70.

Lucky for you the triangular number formula T_n = n * (n + 1) / 2 already comes broken down into two factors, so you need to code something to:

  • Determine if n or n + 1 is even
  • Divide the even factor by 2
  • Calculate the number of factors of these factors
  • Multiply these numbers to find the number of factors of the triangular number

Hope that helped :)

Upvotes: 1

Related Questions