#!/usr/bin/python2

"""
Statement:

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?

========================================================

Prelude:

Solving this problem with sheer brute force is very costly,
with a time complexity running of O[n^2] with very large n.

An optimal solution for this problem needs multiple alrorithmic
optimizations. First comes from the fact that a triangular
number can be calculated as:
    num_n = n*(n+1) / 2     ------------------------------ [1]

Second is the number of factors as represendted as exponents
of its prime factors. For example, any integer is represented as
    num = p^a x q^b ... r^c
where p, q ... r are prime factors, and a, b ... c are exponents.
This means p has a total of a+1 factors (1, p, p^2, ... p^a).

Since the total number of factors equals the combinations of
the multiples of prime factors, the total number of factors is
    (a+1) * (b+1) * ... * (c+1)     ---------------------- [2]

Combining [1] and [2], the factors of a triangular number are,
with the assumption that n is even (since either n or n+1 has
to be even, and we want the smallest number), with n and n+1 as
    n = p_1^a_1 * p_2^a_2 ... p_s^a_s
    n+1 = q_1^b_1 * q_2^b_2 ... q_t^b_t
    number of factors = (a_1-1) * prod(a_2 ... a_s) *
                        prod(b_1 ... b_t)  (< 500)
where a_1 is 2.

http://www.primepuzzles.net/problems/prob_019.htm
http://code.jasonbhill.com/sage/project-euler-problem-12/

"""


from unittest import TestCase, main
from utils import prime_factors


class Problem12(object):

    def __init__(self, bound):
        self.bound = bound

    def combinations(self, number):
        factors = prime_factors(number)
        if 2 in factors:
            factors[2] = factors[2] - 1
        return reduce(lambda x, y: x*y,
                      [i+1 for i in factors.values()])

    def fn(self):
        index = 2
        this = self.combinations(index)
        nxt = self.combinations(index+1)
        while this * nxt < self.bound:
            index += 1
            this, nxt = nxt, self.combinations(index+1)
        return index * (index + 1) / 2


class TestProblem12(TestCase):

    def setUp(self):
        self.bound = 500
        self.answer = 76576500

    def test_main(self):
        self.assertEqual(Problem12(self.bound).fn(), self.answer)


if __name__ == '__main__':
    main()

#!/usr/bin/python2

"""
Statement:

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?

========================================================

Prelude:

Solving this problem with sheer brute force is very costly,
with a time complexity running of O[n^2] with very large n.

An optimal solution for this problem needs multiple alrorithmic
optimizations. First comes from the fact that a triangular
number can be calculated as:
    num_n = n*(n+1) / 2     ------------------------------ [1]

Second is the number of factors as represendted as exponents
of its prime factors. For example, any integer is represented as
    num = p^a x q^b ... r^c
where p, q ... r are prime factors, and a, b ... c are exponents.
This means p has a total of a+1 factors (1, p, p^2, ... p^a).

Since the total number of factors equals the combinations of
the multiples of prime factors, the total number of factors is
    (a+1) * (b+1) * ... * (c+1)     ---------------------- [2]

Combining [1] and [2], the factors of a triangular number are,
with the assumption that n is even (since either n or n+1 has
to be even, and we want the smallest number), with n and n+1 as
    n = p_1^a_1 * p_2^a_2 ... p_s^a_s
    n+1 = q_1^b_1 * q_2^b_2 ... q_t^b_t
    number of factors = (a_1-1) * prod(a_2 ... a_s) *
                        prod(b_1 ... b_t)  (< 500)
where a_1 is 2.

http://www.primepuzzles.net/problems/prob_019.htm
http://code.jasonbhill.com/sage/project-euler-problem-12/

"""


from unittest import TestCase, main
from utils import prime_factors


class Problem12(object):

    def __init__(self, bound):
        self.bound = bound

    def combinations(self, number):
        factors = prime_factors(number)
        if 2 in factors:
            factors[2] = factors[2] - 1
        return reduce(lambda x, y: x*y,
                      [i+1 for i in factors.values()])

    def fn(self):
        index = 2
        this = self.combinations(index)
        nxt = self.combinations(index+1)
        while this * nxt < self.bound:
            index += 1
            this, nxt = nxt, self.combinations(index+1)
        return index * (index + 1) / 2


class TestProblem12(TestCase):

    def setUp(self):
        self.bound = 500
        self.answer = 76576500

    def test_main(self):
        self.assertEqual(Problem12(self.bound).fn(), self.answer)


if __name__ == '__main__':
    main()

#!/usr/bin/python2 Statement:  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?  ========================================================  Prelude:  Solving this problem with sheer brute force is very costly, with a time complexity running of O[n^2] with very large n.  An optimal solution for this problem needs multiple alrorithmic optimizations. First comes from the fact that a triangular number can be calculated as:     num_n = n*(n+1) / 2     ------------------------------ [1]  Second is the number of factors as represendted as exponents of its prime factors. For example, any integer is represented as     num = p^a x q^b ... r^c where p, q ... r are prime factors, and a, b ... c are exponents. This means p has a total of a+1 factors (1, p, p^2, ... p^a).  Since the total number of factors equals the combinations of the multiples of prime factors, the total number of factors is     (a+1) * (b+1) * ... * (c+1)     ---------------------- [2]  Combining [1] and [2], the factors of a triangular number are, with the assumption that n is even (since either n or n+1 has to be even, and we want the smallest number), with n and n+1 as     n = p_1^a_1 * p_2^a_2 ... p_s^a_s     n+1 = q_1^b_1 * q_2^b_2 ... q_t^b_t     number of factors = (a_1-1) * prod(a_2 ... a_s) *                         prod(b_1 ... b_t)  (< 500) where a_1 is 2.  http://www.primepuzzles.net/problems/prob_019.htm http://code.jasonbhill.com/sage/project-euler-problem-12/