#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 itertools
import math
from operator import mul
from functools import reduce
def isFactor(n,fact):
        if n % fact ==0:
                return True
                        
#Generate all primes up to n
def generateSieve(num):
        n = int(num)
        sieve = []
        numbers = [0] *n
        i=2
        while i < n :
                #print i, sieve
                if numbers[i] == 1:
                        i += 1
                        continue
                if numbers[i] ==0: # This is a prime number
                        sieve.append(i)
                if 2*i >= n:
                        i +=1
                        continue
                j=i
                while True:
                        j += i
                        if j >= n:
                                break
                        numbers[j] = 1
                i += 1
        return sieve

def factorize(n,sieveTable):
        dividers = []
        if sieveTable != None:
                primes = sieveTable
        else:
                primes = generateSieve(math.sqrt(n))
        factored = n
        i=0
        while (i < len(primes) )& (i < n):
                if factored % primes[i] ==0:
                        factored /= primes[i]
                        dividers.append(primes[i])
                        continue
                i +=1
        if factored != 1:
                dividers.append(int(factored))
        return dividers
    
def generateTriangleNum(n):
    sumN = 0
    i=1
    while i <= n:
        sumN += i
        i+=1
    return sumN

def findTriangleNumWithNDivisors(nDiv,startWith):
    maxsieveSize = 1000
    initSieve = generateSieve(maxsieveSize)
    i=startWith#i=1
    currTriangleNum=generateTriangleNum(i-1)#currTriangleNum =0
    maxLenFactors = 0
    while True:
        currTriangleNum +=i
        if i % 2 ==0:
            divToKill = i+1
        else:
            divToKill = i 
        shortTriangle = int(currTriangleNum/divToKill)
        if shortTriangle > maxsieveSize:
            #print ('Old sieve size:',maxsieveSize,'Need more sieve!')
            maxsieveSize  = 2 * shortTriangle
            initSieve = generateSieve(maxsieveSize)
        primeFactors = factorize(divToKill,initSieve)
        primeFactors += factorize(shortTriangle,initSieve)
        if 2 **len(primeFactors) -1 < nDiv:
            #print ('Immposible, only ', len(primeFactors), ' prime factors. MAX possible factors:',2**len(primeFactors))
            i+=1
            continue
        factors =primeFactors
        currFactorsLen = 1
        uniqueFactors = set(factors)
        for fact in uniqueFactors:
            currFactorsLen *= (factors.count(fact) +1)
        
        #k=2 # po ile w kombinacjach
        #print ('factors:',factors,'currTriangleNum:',currTriangleNum)
        #while k <= len(primeFactors):
            #combs = list(itertools.combinations(primeFactors,k))
            #for tup in combs:
            #    #print ('tup:',tup)
            #    factors.add(reduce(mul,tup))
            #k+=1
        #print ('factors:',factors,'currTriangleNum:',currTriangleNum)
        if i % 10 == 0:
            print ('Over number:',i, 'Current Triangle Number:', currTriangleNum,'Sieve size:', maxsieveSize)
        if currFactorsLen > maxLenFactors:
            maxLenFactors = currFactorsLen 
            print (currTriangleNum, maxLenFactors)
        if maxLenFactors > nDiv:
            return currTriangleNum,factors
        i+=1
        
    
        


