#!/usr/bin/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?

from euler import get_total_divisors
from euler import get_divisors
from euler import is_triangular
import itertools
import FactNum

triangle_index = 1
ndivs = 1
less_than_500_divs = True

#slow method
def old():
	n=1
	triangle=n
	max_divisors = 1
	while True:
		divisors=get_total_divisors(triangle)
		if divisors>500:
			break
		if divisors > max_divisors:
			max_divisors = divisors
			print "Triangle number with most divisors is ", triangle, " with ", max_divisors
		elif n%100==0:
			print "Current at:", n, "and triangle at ", triangle

		triangle+=n
		n+=1

	print "Finished. First triangular with +500 divisors is ", triangle


def triangulars(num):

	vec_b = [ 1, 3, 6, 1, 6, 3, 1, 0, 0]

	n = 0
	b = 0
	triangle=0
	for i in range(num):
		
		while True:
			t = 9*n +vec_b[b]
			if t > triangle:
				triangle = t
				break
			else:
				n+=1

		print triangle, "= 9 *", n, "+", vec_b[b] 
		b= b+1 if b<len(vec_b)-1 else 0

def triangulars_v2(num):

	vec_b = [1, 3, 6, 1, 6, 3, 1, 0, 0]

	b= triangle = 0
	n = 1
	while True:
		triangle+=n
		n+=1
		
		N = (triangle - vec_b[b])/9

		#print triangle, "= 9 *", N, "+", vec_b[b] 
		if vec_b[b]==0:
			N_total_divs = get_total_divisors(N)

			if N_total_divs * 3 >= 500:
				print triangle
				break

		

		b= b+1 if b<len(vec_b)-1 else 0

		n+=1

def problema12_v3(limit,num_divs):
	
	div_count=[1 for i in range(0,limit+1)]
	
	print len(div_count)

	found = False
	max_divs = 1
	for num in xrange(2,len(div_count)):
		#print "-> ", num
		for i in xrange(num,len(div_count),num):
			#print i, " ", 
			div_count[i]+=1

			if div_count[i]>=num_divs and is_triangular(i):
					print "Found maximum:", i
					found = True
					break	

		if found:	
			break
		elif div_count[num]>max_divs and is_triangular(num):
			max_divs=div_count[num]
			print "Update: triangular with most divisors is ", num, " with ", div_count[num]
			
	#print [ (i,count) for (i,count) in zip(range(len(div_count)),div_count) ]
	
def problema12_v4(limit,num_divs):
	

							
problema12_v3(80000000,500)


