euler012.py

#!/usr/bin/env python
"""
Solution to Project Euler Problem 12
http://projecteuler.net/

by Apalala <apalala@gmail.com>
(cc) Attribution-ShareAlike
http://creativecommons.org/licenses/by-sa/3.0/

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?
"""
from functools import reduce
from itertools import combinations
from factorization import factors
from series import factorial
import operator


def triangles(n):
    i = 1
    t = 1
    while n > 0:
        yield t
        i += 1
        t += i
        n -= 1


def first_triangle_with_divisors(n):
    def prod(q):
        return reduce(operator.mul, q, 1)

    for t in triangles(factorial(n)):
        f = factors(t)
        reps = [k[1] for k in f]
        count = 1
        for s in range(len(reps)):
            for c in combinations(reps, s + 1):
                count += prod(c)
        if count >= n:
            return t


def test():
    assert (1, 3, 6, 10, 15, 21, 28, 36, 45, 55) == tuple(triangles(10))
    assert 28 == first_triangle_with_divisors(5)


def run():
    print(first_triangle_with_divisors(500))


if __name__ == "__main__":
    test()
    run()