#!/usr/bin/env python

"""

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?

"""

#One of my slowest runnings solutions...


primes = [2,3,5,7,11,13,17,19,23,29]

def tri(n):
   return n*(n+1)/2


# returns a dictionary of prime factors of n, where the keys
#   are the prime factors, and the values are the number
#   of times that factor goes in to n
def prime_factors(n):
   factors = {}
   for i in (primes + range(29, n+1)):
      if i > n:
         break
      while n % i == 0:
         if not i in factors:
            factors[i] = 0
         factors[i] += 1
         n /= i
   return factors

# returns the number of divisors of n
def num_divs(n):
   facts = prime_factors(n)
   divs = 1
   for key in facts:
      divs *= facts[key]+1
   return divs

for i in range(2, 90001):
   #print i,tri(i), num_divs( tri(i) ), prime_factors(tri(i))
   t = tri(i)
   n = num_divs( t )
   if n > 150:
      print i, t, n
      if n > 500:
         break

#(Unused in this problem)
def is_prime(n):
   for i in range(2, n):
      if n % i == 0:
         return false
   return true

