Calculating the first triangle number to have over 500 divisors in python

Question

I'm trying to solve the 12th problem on Project Euler. I can calculate the number that has over 500 divisors in almost 4 minutes. How can i make it faster? Here's the attempt;

import time

def main():
    memo={0:0,1:1}
    i=2
    n=200
    while(1):
        if len(getD(getT(i)))>n:
            break
        i+=1
    print(getT(i))

#returns the nth triangle number
def getT(n):
    if not n in memo:
        memo[n]=n+getT(n-1)
    return memo[n]

#returns the list of the divisors
def getD(n):
    divisors=[n]
    for i in xrange(1,int((n/2)+1)):
        if (n/float(i))%1==0:
            divisors.append(i)
    return divisors

startTime=time.time()
main()
print(time.time()-startTime)

Answer 1

You don't need an array to store the triangle numbers. You can use a single int because you are checking only one value. Also, it might help to use the triangle number formula:n*(n+1)/2 where you find the nth triangle number.

getD also only needs to return a single number, as you are just looking for 500 divisors, not the values of the divisors.

However, your real problem lies in the n/2 in the for loop. By checking factor pairs, you can use sqrt(n). So only check values up to sqrt(n). If you check up to n/2, you get a very large number of wasted tests (in the millions).

So you want to do the following (n is the integer to find number of divisors of, d is possible divisor):

• make sure n/d has no remainder.
• determine whether to add 1 or 2 to your number of divisors.

Answer 2

Using a decorator (courtesy of activestate recipes) to save previously calculated values, and using a list comprehension to generate the devisors:

def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret 
    return memodict().__getitem__

@memodict
def trinumdiv(n):
    '''Return the number of divisors of the n-th triangle number'''
    numbers = range(1,n+1)
    total = sum(numbers)
    return len([j for j in range(1,total+1) if total % j == 0])

def main():
    nums = range(100000)
    for n in nums:
        if trinumdiv(n) > 200:
           print n
           break

Results:

In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:def main():
:       nums = range(10000)
:       for n in nums:
:               if trinumdiv(n) > 100:
:                  print 'Found:', n
:                  break
:
:startTime=time.time()
:main()
:print(time.time()-startTime)
:--
Found: 384
1.34229898453

and

In [2]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:def main():
:       nums = range(10000)
:       for n in nums:
:               if trinumdiv(n) > 200:
:                  print 'Found:', n
:                  break
:
:startTime=time.time()
:main()
:print(time.time()-startTime)
:--
Found: 2015
220.681169033

Answer 3

A few comments.

As Quincunx writes, you only need to check the integer range from 1..sqrt(n) which would translate into something like this for i in xrange(1, sqrt(n) + 1): .... This optimization alone vastly speeds up things.

You can use the triangle number formula (which I didn't know until just now, thank you Quincunx), or you can use another approach for finding the triangle numbers than recursion and dictionary lookups. You only need the next number in the sequence, so there is no point in saving it. Function calls involves significant overhead in Python, so recursion is usually not recommended for number crunching. Also, why the cast to float, I didn't quite get that ?

I see that you are already using xrange instead of range to build the int stream. I assume you know that xrange is faster because it is implemented as a generator function. You can do that too. This makes things a lot smoother as well.

I've tried to do just that, use generators, and the code below finds the 500th triangle number in ~16sec on my machine (YMMV). But I've also used a neat trick to find the divisors, which is the quadratic sieve.

Here is my code:

def triangle_num_generator():
    """ return the next triangle number on each call
        Nth triangle number is defined as SUM([1...N]) """
    n = 1
    s = 0
    while 1:
        s += n
        n += 1
        yield s


def triangle_num_naive(n):
    """ return the nth triangle number using the triangle generator """
    tgen = triangle_num_generator()
    ret = 0
    for i in range(n):
        ret = tgen.next()
    return ret

def divisor_gen(n):
    """ finds divisors by using a quadrativ sieve """
    divisors = []
    # search from 1..sqrt(n)
    for i in xrange(1, int(n**0.5) + 1):
        if n % i is 0:
            yield i
            if i is not n / i:
                divisors.insert(0, n / i)
    for div in divisors:
        yield div


def divisors(n):
    return [d for d in divisor_gen(n)]


num_divs = 0
i = 1
while num_divs < 500:
    i += 1
    tnum = triangle_num_naive(i)
    divs = divisors(tnum)
    num_divs = len(divs)

print tnum # 76576500

Running it produces the following output on my humble machine:

morten@laptop:~/documents/project_euler$ time python pr012.py 
76576500

real    0m16.584s
user    0m16.521s
sys     0m0.016s

Using the triangle formula instead of the naive approach:

real    0m3.437s
user    0m3.424s
sys     0m0.000s

Answer 4

I made a code for the same task. It is fairly fast. I used a very fast factor-finding algorithm to find the factors of the number. I also used (n^2 + n)/2 to find the triangle numbers. Here is the code:

from functools import reduce
import time
start = time.time()
n = 1
list_divs = []
while len(list_divs) < 500:
    tri_n = (n*n+n)/2 # Generates the triangle number T(n)
    list_divs = list(set(reduce(list.__add__,([i, int(tri_n//i)] for i in range(1, int(pow(tri_n, 0.5) + 1)) if tri_n % i == 0)))) # this is the factor generator for any number n
    n+=1
print(tri_n, time.time() - start)

It completes the job in 15 seconds on an OK computer.

Answer 5

Here is my answer which solves in about 3 seconds. I think it could be made faster by keeping track of the divisors or generating a prime list to use as divisors... but 3 seconds was quick enough for me.

import time

def numdivisors(triangle):
  factors = 0
  for i in range(1, int((triangle ** 0.5)) + 1):
    if triangle % i == 0:
      factors += 1
  return factors * 2

def maxtriangledivisors(max):
  i = 1
  triangle = 0
  while i > 0:
    triangle += i
    if numdivisors(triangle) >= max:
      print 'it was found number', triangle,'triangle', i, 'with total of ', numdivisors(triangle), 'factors'
      return triangle
    i += 1

startTime=time.time()
maxtriangledivisors(500)
print(time.time()-startTime)

Answer 6

Here is another solution to the problem.In this i use Sieve of Eratosthenes to find the primes then doing prime factorisation. Applying the below formula to calculate number of factors of a number: total number of factors=(n+1)*(m+1).....

where number=2^n*3^n.......

My best time is 1.9 seconds.

from time import time
t=time()

a=[0]*100
c=0
for i in range(2,100):
    if a[i]==0:
        for j in range(i*i,100,i):
            continue
        a[c]=i
        c=c+1
print(a)

n=1
ctr=0
while(ctr<=1000):
    ctr=1
    triang=n*(n+1)/2
    x=triang
    i=0
    n=n+1
    while(a[i]<=x):
        b=1
        while(x%a[i]==0):
            b=b+1
            x=x//a[i];
        i=i+1
        ctr=ctr*b
print(triang)
print("took time",time()-t)