problem12.py

#!/usr/bin/python
from tools.timeit import timeit
from pprint import pprint as pp
from tools.primes import factorize
from tools.general import product

from itertools import combinations

problem = """The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

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

def genTriangleNums(limit=99999999):
    idx1 = 0
    sidx = 0
    while sidx < limit:
        idx1 += 1
        sidx += idx1
        yield sidx

@timeit
def process():
    index = 0
    for NUM in genTriangleNums():
        index += 1
        factors = factorize(NUM)
        
        factors1 = [[pow(num, c) for c in range(1, count+1)]for num, count in factors]
        
        divs = []
        for facs in factors1:
            divs += facs

        divisors = set()

        for r in range(1, len(divs) + 1):
            for nums in combinations(divs, r):
                prod = product(nums)
                if NUM % prod == 0:
                    divisors.add(prod)
                    
        numdivs = len(divisors)
        numdivs += 1

        if numdivs > 500:
            break
    value = "%s has %s divisors. This is the %s'th triangle number" % (NUM, numdivs, index)
    return value
    
etime, solution = process()

print "Problem :\n%s\n\n\nSolution : %s" % (problem, solution)
print "\nRunning time : %10.6f seconds" % (etime)