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?
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
from itertools import islice
# from itertools import accumulate
from itertools import dropwhile
from functools import partial
# from operator import mul
In [2]:
# modest hardware for 2015
!lscpu
In [3]:
list(gen_lt(gen_triangular(), 100))
Out[3]:
In [4]:
list(get_factors(1)), list(get_factors(72))
Out[4]:
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))
Out[6]:
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)
Out[8]:
In [9]:
known_good_output = foo(n)
map() is often slow, so I explore avoiding the need use map to add one after tabulate(), by using a generator expression. The generator expression is faster than map.
In [10]:
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 [11]:
def foo(n):
for t in gen_triangular():
if product(x+1 for x in tabulate(get_factors(t)).values()) > n:
return t
In [12]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Next I explore by initializing the count to 1 in tabulate() to avoid the need to add one afterwards. This yields the fastest code. The downsides of this are that tabulate is not so general and the trickery of hiding the initialization to 1.
In [13]:
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
plus one.'''
f = {}
for i in x:
if i not in f:
f[i] = 1
f[i] += 1
return f
In [14]:
tabulate(get_factors(24))
Out[14]:
In [15]:
def foo(n):
for t in gen_triangular():
if product(tabulate(get_factors(t)).values()) > n:
return t
In [16]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below, try a defaultdict. It is cleaner and slower.
In [17]:
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 [18]:
def foo(n):
for t in gen_triangular():
if product(map(lambda x: x+1, tabulate(get_factors(t)).values())) > n:
return t
In [19]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below is a minor variation of the above. The code below uses a generator expression to add one, instead of map used above.
In [20]:
def foo(n):
for t in gen_triangular():
if product(x+1 for x in tabulate(get_factors(t)).values()) > n:
return t
In [21]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below, product(x+1 for x in Counter(get_factors(t)).values()) is moved to a separate function for readability. Even if it is a little slower, the improved readability is worth it.
In [22]:
def number_of_factors(n):
return product(x+1 for x in Counter(get_factors(n)).values())
In [23]:
def foo(n):
for t in gen_triangular():
if number_of_factors(t) > n:
return t
In [24]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below is a minor variation of cells 17 - 19 above. Below defaultdict is used with a default value of 1 to avoid needing to add one later.
In [25]:
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
plus one.'''
counts = defaultdict(partial(int, 1))
for i in x:
counts[i] += 1
return counts
In [26]:
def foo(n):
for t in gen_triangular():
if product(tabulate(get_factors(t)).values()) > n:
return t
In [27]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below, product(tabulate(get_factors(t)).values()) is moved to a separate function for readability. Even if it is a little slower, the improved readability is worth it.
In [28]:
def number_of_factors(n):
return product(tabulate(get_factors(n)).values())
In [29]:
def foo(n):
for t in gen_triangular():
if number_of_factors(t) > n:
return t
In [30]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Convert to a more functional approach below. It hurts my head to figure it out; it is hard to read, so I do not like this approach.
In [31]:
def foo(n):
return list(islice(
(t for t in gen_triangular()
if product(tabulate(get_factors(t)).values()) > n),
1))[0]
In [32]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Convert the above to a completely functional approach below. This is hard to read, so it is not good, even though it produces the correct result.
In [33]:
def foo(n):
return list(islice(
filter(
lambda t: product(tabulate(get_factors(t)).values()) > n,
gen_triangular(),
),
1
))[0]
In [34]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Next try itertools.dropwhile() instead of filter. This is ugly also.
In [35]:
def foo(n):
return list(islice(
dropwhile(
lambda t: product(tabulate(get_factors(t)).values()) <= n,
gen_triangular(),
),
1
))[0]
In [36]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Use straightforward Counter instead of a defaultdict. Using Counter is much easier to read, so I like it even though it is much slower.
In [37]:
def foo(n):
for t in gen_triangular():
if product(x+1 for x in Counter(get_factors(t)).values()) > n:
return t
In [38]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
Below, product(x+1 for x in Counter(get_factors(t)).values()) is moved to a separate function for readability. Even if it is a little slower, the improved readability is worth it.
In [39]:
def number_of_factors(n):
return product(x+1 for x in Counter(get_factors(n)).values())
In [40]:
def foo(n):
for t in gen_triangular():
if number_of_factors(t) > n:
return t
In [41]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
My gen_n reinvented much of islice(). My gen_n also is slower than islice(), so my gen_n has little value. So I deprecate gen_n.
In [42]:
%timeit list(gen_n(range(n+n), n))
%timeit list(islice(range(n+n), n))
Below, try going for speed at the expense of readability.
Since we care only about the factors of triangular numbers, not the triangular numbers themselves, explore generating the two main factors of triangular numbers and separately factor those two main factors, to figure out the factors of the triangular number. Hopefully factoring two smaller numbers will be faster than factoring one big number.
In [43]:
def gen_triangular_main_factors():
for i in count(1, 2):
yield i, (i+1) // 2
yield (i+1) // 2, i+2
In [44]:
for i in islice(gen_triangular_main_factors(), 10):
print(i, product(i))
In [45]:
def iter_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
plus one.'''
f = {}
for y in x:
for i in y:
if i not in f:
f[i] = 1
f[i] += 1
return f
In [46]:
def foo(n):
for t in gen_triangular_main_factors():
factors = iter_tabulate(map(get_factors, t))
if product(factors.values()) > n:
return product(t)
In [47]:
n = 500
%timeit foo(n)
assert foo(n) == known_good_output
The point of the code above was speed, but it is slower than the fastest code. Maybe the slowness is due to overhead. Maybe that overhead would be less important for huge numbers.
So let's try it for a large value of n compared against the fastest version above renamed below as goo().
In [48]:
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
plus one.'''
f = {}
for i in x:
if i not in f:
f[i] = 1
f[i] += 1
return f
In [49]:
def goo(n):
for t in gen_triangular():
if product(tabulate(get_factors(t)).values()) > n:
return t
In [50]:
n = 2000
%timeit goo(n)
goo(n)
Out[50]:
In [51]:
n = 2000
%timeit foo(n)
foo(n)
Out[51]:
In [52]:
Counter(get_factors(_))
Out[52]:
Factoring the main factors separately is still slower than the fastest code. The more I think about the way that get_factors() works, that makes sense. Factoring the main factors separately means that get_factors() has to try some of the same prime numbers twice. Calling get_factors() only once (with the triangular number) only needs to try each prime number once (when it is not a divisor).
Summary
Cells 13, 15 have the fastest code, which has a for loop and does not use any special data types.
Cells 39 - 40 have the prettiest code, by using collections.Counter.
Cells 17, 22 - 23 seem to be the best compromise between readability and speed.
Use itertools.islice instead of my euler.gen_n.