notebook.community

Edit and run

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?



In [1]:

    
from __future__ import print_function

from euler import gen_triangular
from euler import gen_lt
from euler import get_factors
from euler import product
from euler import gen_n
from collections import defaultdict
from collections import Counter
from itertools import count



In [2]:

    
# modest hardware for 2015
!lscpu









    



Architecture:          i686
CPU op-mode(s):        32-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 14
Stepping:              8
CPU MHz:               2000.000
BogoMIPS:              3994.38
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              2048K



In [3]:

    
list(gen_lt(gen_triangular(), 100))









    Out[3]:





[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91]



In [4]:

    
list(get_factors(1)), list(get_factors(72))









    Out[4]:





([], [2, 2, 2, 3, 3])



In [5]:

    
def tabulate(x):
    '''Returns dictionary for given collection x where
        keys are for collection elements
        values are count of how many times 
            the key occurs in the given collection.'''
    f = {}
    for i in x:
        if i not in f:
            f[i] = 0
        f[i] += 1
    return f



In [6]:

    
tabulate(get_factors(24)), len(tabulate(get_factors(24)))









    Out[6]:





({2: 3, 3: 1}, 2)



In [7]:

    
def foo(n):
    for t in gen_triangular():
        if product(map((lambda x: x+1), tabulate(get_factors(t)).values())) > n:
            return t



In [8]:

    
n = 500
%timeit foo(n)
foo(n)









    



1 loops, best of 3: 87.9 ms per loop






    Out[8]:





76576500



In [9]:

    
def tabulate(x):
    '''Returns dictionary for given collection x where
        keys are for collection elements
        values are count of how many times 
            the key occurs in the given collection.'''
    counts = defaultdict(int)
    for i in x:
        counts[i] += 1
    return counts



In [10]:

    
n = 500
%timeit foo(n)
foo(n)









    



10 loops, best of 3: 97.2 ms per loop






    Out[10]:





76576500



In [11]:

    
def foo(n):
    for t in gen_triangular():
        if product(map((lambda x: x+1), Counter(get_factors(t)).values())) > n:
            return t



In [12]:

    
n = 500
%timeit foo(n)
foo(n)









    



10 loops, best of 3: 186 ms per loop






    Out[12]:





76576500



In [13]:

    
def gen_triangular_main_factors():
    for i in count(1, 2):
        yield i, (i+1) / 2
        yield (i+1) / 2, i+2



In [14]:

    
for i in gen_n(gen_triangular_main_factors(), 10):
    print(i, product(i))









    



(1, 1) 1
(1, 3) 3
(3, 2) 6
(2, 5) 10
(5, 3) 15
(3, 7) 21
(7, 4) 28
(4, 9) 36
(9, 5) 45
(5, 11) 55



In [15]:

    
def tabulate(x):
    '''Returns dictionary for given collection of collection x where
        keys are for collection elements
        values are count of how many times 
            the key occurs in the given collection.'''
    f = {}
    for y in x:
        for i in y:
            if i not in f:
                f[i] = 0
            f[i] += 1
    return f



In [16]:

    
def foo(n):
    for t in gen_triangular_main_factors():
        factors = tabulate(map(get_factors, t))
        if product(map((lambda x: x+1), factors.values())) > n:
            return product(t)



In [17]:

    
n = 500
%timeit foo(n)
foo(n)









    



10 loops, best of 3: 114 ms per loop






    Out[17]:





76576500