# 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?
#

import math
import datetime
from prime_util.prime_util import *


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


def divisors_count(val):
    is_divisors = [True for i in range(0, val/2 + 1)]
    is_divisors[0] = False
    for i in range(2, len(is_divisors)):
        if not is_divisors[i]:
            continue
        if val % i != 0:
            is_divisors[i] = False
            for j in range(i*i, len(is_divisors), 2*i):
                is_divisors[i] = False
    return sum(is_divisors) + 1


def p(n):
    triangle_index = 27 if n > 5 else 1
    n_divisors = 0
    t = 0
    while n_divisors <= n:
        triangle_index *=2
        t = triangle(triangle_index)
        t_divisors = divisors_count(t)
        n_divisors = max(n_divisors, t_divisors)
        print t, n_divisors

    return t, t_divisors


def problem_12(n, primes):
    start_time = datetime.datetime.now()
    n_div = 0
    t = 0
    triangle_val = 0
    while n_div <= n:
        t += 1
        val = triangle(t)
        prime_dec = prime_decomposition_dict_using(val, primes)
        mult = 1
        for prime in prime_dec:
            mult *= (prime_dec[prime] + 1)
        if mult > n_div:
            n_div = mult
            triangle_val = val
        print n_div, triangle_val
    print "Program took {}".format(datetime.datetime.now() - start_time)
    return n_div, triangle_val


table_of_primes = primes_under(66000)

print problem_12(500, table_of_primes)

