Xavier Ho

# This one only took 8 seconds on my machine. Wow?

"""The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) 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?"""

from operator import mul

def factorise(num):
    """Returns a list of prime factors. For example:
        factorise(6) will return
        [0, 0, 1, 1, 0, 0]
        as in, 2^1 * 3^1 = 6."""
    powers = [0, 0]
    factor = 2
    while num > 1:
        if num % factor == 0:
            powers[factor-1] += 1
            num /= factor
        else:
            powers.append(0)
            factor += 1
    return powers

def countDivisors(powers):
    """Takes a factorised form and returns the number of possible divisors.
        For example: 24 = 2^3 * 3^1
        There are (3 + 1)*(1 + 1) possible divisors, or 8.
        24 has divisors of 1, 2, 3, 4, 6, 8, 12, 24 - 8 of them."""
    return reduce(mul, [(x+1) for x in powers if x != 0])

# MAIN
n = 2
tri = 1
while True:
    tri += n
    count = countDivisors(factorise(tri))
    if count > 500:
        print tri, count
        break
    n += 1