'''
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

def triangles():
  t = 1
  i = 2
  yield t
  while True:
    t += i
    i += 1
    yield t

def prime_factors(n):
  pfs = [1]
  f = 2
  og = n
  if n < 4:
    pfs.append(n)
    return pfs
  else:
    while f**2 <= n:
      while n % f == 0:
        pfs.append(f)
        n //= f
      f += 1
    pfs.append(n)
    return pfs

def divisors(n):
  pfs = prime_factors(n)
  divs = set([1])
  for i in range(2, len(pfs)):
    combs = combinations(pfs, i)
    for comb in combs:
      divs.add(reduce(lambda a, b: a*b, comb))
  return divs

def divisible_triangle(d):
  for t in triangles():
    if len(divisors(t)) >= d:
      return t

%timeit divisible_triangle(500)

