<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
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
Step1:  We already implemented a function that finds all prime factors of a number which may be useful if we are required to optimize. For now, let's use something simple like this. After all,
Premature optimization is the root of all evil
Donald Knuth
Step2:  Function composition is going to be useful for this problem. Of course, Python is not a functional programming language, but we can nonetheless hack together something that closely resembles it.
Step3:  Here is a "semi-quine" to test our function composition.
Step4:  Now we're ready to go
Step5:  First, a quick composition with the generator version of map and count/islice instead of the usual range, since we're going to apply the higher-order function first later, instead of islice.
Step6:  We can see that the first triangle number to have over 5 divisors has 6 divisors, but we don't know what the triangle number is. We need to do a bit more work to retain that information in our function composition pipeline.
Step7:  Excellent. Now we have a pair of the triangle number, and its number of factors.
Step8:  Instead of using islice, we just need to use our higher-order function first with a predicate. What does this function do? The name speaks for itself, return the first item in an iterable that satisfies the predicate.
Step9:  Hold on to your hats...
Step10:  Version 2
Step11:  First, let's implement prod, which is the multiplication analog to sum, with the help of the built-in reduce function.
Step12:  Now, we need a way to add 1 to each item of the Counter which represents an integer's prime factors. We could do this for example
Step13:  But that's not very Pythonic, nor 
does it utilize the power of Counter
very well. Let's do it right - by 
making use of the fact that Counter
objects supports addition.
Step14:  Now we're ready to implement count_factors.
Step15:  Version 3
<ASSISTANT_TASK:>
Python Code:
from six.moves import map, range, reduce
def triangle_num(n):
    "The nth triangle number"
    return n*(n+1)>>1
triangle_num(7)
list(map(triangle_num, range(1, 11)))
Explanation: 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?
<!-- TEASER_END -->
Version 1: Brute force
End of explanation
factors = lambda n: list(filter(lambda x: n % x == 0, range(1, n+1)))
{n:factors(n) for n in map(triangle_num, range(1, 8))}
Explanation: We already implemented a function that finds all prime factors of a number which may be useful if we are required to optimize. For now, let's use something simple like this. After all,
Premature optimization is the root of all evil
Donald Knuth
End of explanation
compose = lambda *fns: reduce(lambda f, g: lambda *args, **kwargs: f(g(*args, **kwargs)), fns)
Explanation: Function composition is going to be useful for this problem. Of course, Python is not a functional programming language, but we can nonetheless hack together something that closely resembles it.
End of explanation
compose(lambda x: x**2, len)('should be 169')
map(compose(factors, triangle_num), range(1, 11))
Explanation: Here is a "semi-quine" to test our function composition.
End of explanation
from itertools import count, islice
def first(pred, iterable):
    for x in iterable:
        if pred(x):
            return x
Explanation: Now we're ready to go
End of explanation
list(islice(map(compose(len, factors, triangle_num), count(1)), 10))
Explanation: First, a quick composition with the generator version of map and count/islice instead of the usual range, since we're going to apply the higher-order function first later, instead of islice.
End of explanation
first(lambda n: n >= 5, map(compose(len, factors, triangle_num), count(1)))
Explanation: We can see that the first triangle number to have over 5 divisors has 6 divisors, but we don't know what the triangle number is. We need to do a bit more work to retain that information in our function composition pipeline.
End of explanation
list(islice(map(compose(lambda n: (n, compose(len, factors)(n)), triangle_num), count(1)), 10))
Explanation: Excellent. Now we have a pair of the triangle number, and its number of factors.
End of explanation
first(lambda l: l[1] >= 5, map(compose(lambda n: (n, compose(len, factors)(n)), triangle_num), count(1)))
Explanation: Instead of using islice, we just need to use our higher-order function first with a predicate. What does this function do? The name speaks for itself, return the first item in an iterable that satisfies the predicate.
End of explanation
# (lambda l: l[1] >= 5*10**2, imap(compose(lambda n: (n, compose(len, factors)(n)), triangle_num), count(1)))
Explanation: Hold on to your hats...
End of explanation
%load_ext autoreload
%autoreload 2
from common.utils import prime_factors
prime_factors(28)
Explanation: Version 2: The Fundamental Theorem of Arithmetic
By the fundamental theorem of arithmetic, every integer $n$ has a unique prime factorization, say, $n = \prod_{i} p_i^{e_i}$ and it follows that $n$ has $\prod_{i} (e_i+1)$ factors. To see this, observe that each prime factor $p_i$ of $n$ can be used 0 to $e_i$ times to form a factor of $n$. This is where our prime_factors function comes in handy.
End of explanation
prod = lambda iterable: reduce(lambda x, y: x*y, iterable, 1)
prod([])
Explanation: First, let's implement prod, which is the multiplication analog to sum, with the help of the built-in reduce function.
End of explanation
from collections import Counter
c = Counter({2: 2, 7: 1})
for i in c:
    c[i] += 1
c
Explanation: Now, we need a way to add 1 to each item of the Counter which represents an integer's prime factors. We could do this for example
End of explanation
c = Counter({2: 2, 7: 1})
d = Counter(c.keys())
d
c + d
Explanation: But that's not very Pythonic, nor 
does it utilize the power of Counter
very well. Let's do it right - by 
making use of the fact that Counter
objects supports addition.
End of explanation
def count_factors(n):
    c = prime_factors(n)
    d = Counter(c.keys())
    return prod((c+d).values()) 
count_factors(10000)
first(lambda l: l[1] >= 5, map(compose(lambda n: (n, count_factors(n)), triangle_num), count(2)))
first(lambda l: l[1] >= 50, map(compose(lambda n: (n, count_factors(n)), triangle_num), count(2)))
first(lambda l: l[1] >= 500, map(compose(lambda n: (n, count_factors(n)), triangle_num), count(2)))
Explanation: Now we're ready to implement count_factors.
End of explanation
for n in count(2):
    k = n // 2
    T_n = triangle_num(n)
    if n % 2:
        a, b = 2*k+1, k+1
    else:
        a, b = k, 2*k+1
    T_n_factors = count_factors(a)*count_factors(b)
    if T_n_factors >= 500:
        print(T_n, T_n_factors)
        break
for k in count(1):
    a = count_factors(k)
    b = count_factors(2*k+1)
    c = count_factors(k+1)
    n_even = triangle_num(2*k)
    n_odd = triangle_num(2*k+1)
    if a*b >= 500:
        print(n_even)
        break
    elif b*c >= 500:
        print(n_odd)
        break
Explanation: Version 3: Pretty basic number theory
Denote the $n$th triangle by $T_n$ and recall that $T_n = \frac{n(n+1)}{2}$.
Observe that $n$ and $n+1$ are coprime. That is, $\gcd{(n, n+1)} = 1$. Note that one of $n, n+1$ must be even and that in general $\gcd{(a, 2b)} = 1 \Rightarrow \gcd{(a, b)} = 1$ for integers $a, b$.
Say $n = 2k$. Then $T_n = \frac{n(n+1)}{2} = k(2k+1)$. Then, $\gcd{(n, n+1)} = 1 \Rightarrow \gcd{(\frac{n}{2}, n+1)} = \gcd{(k, 2k+1)} = 1$ - the only common positive factor of $k$ and $2k+1$ is $1$, so we need only find their respective factors and combine them together. 
The same goes for the case where $n = 2k+1$. We have $T_n = \frac{n(n+1)}{2} =(k+1)(2k+1)$ and $\gcd{(n, n+1)} = 1\Rightarrow \gcd{(n, \frac{n+1}{2})} = \gcd{(2k+1, k+1)}=1$, so we factorize $2k+1$ and $k+1$.
Now that we have decomposed the problem to factorizing 2 integers, we essentially have the overlapping subproblem of factorizing $2k+1$. So we can even use dynamic programming to further optimize this solution.
End of explanation
<END_TASK>