# -*- coding: utf-8 -*-
from __future__ import print_function, unicode_literals, absolute_import, division
"""
problem description:

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?


weblink:

"""

from projecteulerhelper import *
#timeit is import from helper, instead of timeit module
from math import sqrt
#

# test the correction by a small dimension first. 
# test  brute force first, method1
#then, try some smart method! 

def divisors(x):
    #if x<4: return [1,x]

    if int(sqrt(x))**2 == x:
        l=[int(sqrt(x))]
        stop=int(sqrt(x))
    else:
        stop=int(sqrt(x))+1
        l=[]  # 
    for i in range(1, stop):
        if x%i==0:
            l.append(i) # there will be no repeat!
            l.append(x/i)
    return sorted(l)

def test():
    for i in range(1,10):
        print('divisors(',i ,')=', divisors(i))
    print('divisors(28):',divisors(28))

    print('divisors(64):', len(divisors(64)))
    print('divisors(128):', len(divisors(128)))



def bruteforce():  # impossible
    dmax=2
    start=1000
    for i in range(start,10**6):
        l=len(divisors(i))
        if l>dmax:
            dmax=l
        if dmax>500:
            print(i,dmax)
            break

def product(list):
    p = 1
    for i in list:
        p *= i
    return p

def smarter():
    # x=p1**i1 * p2**i2 ...         p is the prime list
    # all prime has only 2 divisors
    # increasing the power  is not effective as increase the prime, only by +1
    print('divisors(30):', len(divisors(30)))  # 2**3
    print('divisors(210):', len(divisors(210))) # 
    print('divisors(2310):', len(divisors(2310))) # 32
    print('divisors(4620):', len(divisors(4620))) #X2
    print('divisors(9240):', len(divisors(9240))) #X4
    print('divisors(18480):', len(divisors(18480))) #X8
    print('divisors(30030):', len(divisors(30030))) #2**6

    p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    pp=[]  #[2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230L]
    for i in range(len(p)):
        pp.append( product(p[:i+1]))
    pn=[len(divisors(x)) for x in pp]
    print(pp,pn)
    # mul by 2, can increase half of the len, 
    print('divisors() of', 9699690*4, len(divisors(9699690*4))) #512
    print("test passed")
    

def problem():
    #test()
    #bruteforce()
    smarter()
    
if __name__ == "__main__":
    timeit(problem)
    #timeit(func, param)
# -*- coding: utf-8 -*-
from __future__ import print_function, unicode_literals, absolute_import, division
"""
problem description:

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?


weblink:

"""

from projecteulerhelper import *
#timeit is import from helper, instead of timeit module
from math import sqrt
#

# test the correction by a small dimension first. 
# test  brute force first, method1
#then, try some smart method! 

def divisors(x):
    #if x<4: return [1,x]

    if int(sqrt(x))**2 == x:
        l=[int(sqrt(x))]
        stop=int(sqrt(x))
    else:
        stop=int(sqrt(x))+1
        l=[]  # 
    for i in range(1, stop):
        if x%i==0:
            l.append(i) # there will be no repeat!
            l.append(x/i)
    return sorted(l)

def test():
    for i in range(1,10):
        print('divisors(',i ,')=', divisors(i))
    print('divisors(28):',divisors(28))

    print('divisors(64):', len(divisors(64)))
    print('divisors(128):', len(divisors(128)))



def bruteforce():  # impossible
    dmax=2
    start=1000
    for i in range(start,10**6):
        l=len(divisors(i))
        if l>dmax:
            dmax=l
        if dmax>500:
            print(i,dmax)
            break

def product(list):
    p = 1
    for i in list:
        p *= i
    return p

def smarter():
    # x=p1**i1 * p2**i2 ...         p is the prime list
    # all prime has only 2 divisors
    # increasing the power  is not effective as increase the prime, only by +1
    print('divisors(30):', len(divisors(30)))  # 2**3
    print('divisors(210):', len(divisors(210))) # 
    print('divisors(2310):', len(divisors(2310))) # 32
    print('divisors(4620):', len(divisors(4620))) #X2
    print('divisors(9240):', len(divisors(9240))) #X4
    print('divisors(18480):', len(divisors(18480))) #X8
    print('divisors(30030):', len(divisors(30030))) #2**6

    p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    pp=[]  #[2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230L]
    for i in range(len(p)):
        pp.append( product(p[:i+1]))
    pn=[len(divisors(x)) for x in pp]
    print(pp,pn)
    # mul by 2, can increase half of the len, 
    print('divisors() of', 9699690*4, len(divisors(9699690*4))) #512
    print("test passed")
    

def problem():
    #test()
    #bruteforce()
    smarter()
    
if __name__ == "__main__":
    timeit(problem)
    #timeit(func, param)
# -*- coding: utf-8 -*- problem description:
 
 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?
 
 
 weblink: #timeit is import from helper, instead of timeit module # # test the correction by a small dimension first. # test  brute force first, method1 #then, try some smart method! #if x<4: return [1,x] # # there will be no repeat! # impossible # x=p1**i1 * p2**i2 ...         p is the prime list # all prime has only 2 divisors # increasing the power  is not effective as increase the prime, only by +1 # 2**3 # # 32 #X2 #X4 #X8 #2**6 #[2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230L] # mul by 2, can increase half of the len, #512 #test() #bruteforce() #timeit(func, param)