nekedome / project-euler

solutions/problem12.py

"""
Project Euler Problem 12: Highly Divisible Triangular Number
============================================================

.. module:: solutions.problem12
   :synopsis: My solution to problem #12.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem12.py>`_.

Problem Statement
#################

The sequence of triangle numbers is generated by adding the natural numbers. So the :math:`7^{th}` triangle number would

This line is too long as per the coding-style (120/100).

be
    :math:`1+2+3+4+5+6+7 = 28`.

The first ten terms would be:
    :math:`1,3,6,10,15,21,28,36,45,55,\\dots`

Let us list the factors of the first seven triangle numbers:

.. math::

     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 :math:`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?

Solution Discussion
###################

This solution uses a sieve to incrementally build up the count of divisors :math:`d(x)` for all :math:`x` up to some

This line is too long as per the coding-style (116/100).

pre-determined upper-bound. With this sieve, the problem is easily solvable.

All triangle numbers are of the form:
    :math:`T_n = 1 + 2 + \\dots + n`
which can be re-expressed in the closed form:
    :math:`T_n = \\frac{n \\times (n + 1)}{2}`

Importantly, this expression can be de-composed into pair-wise co-prime components.

Case (:math:`n` is even):
    :math:`T_n = \\frac{n}{2} \\times (n + 1)`

Case (:math:`n` is odd):
    :math:`T_n = n \\times (\\frac{n + 1}{2})`

It should be easy to see that only one term in each case is divisible by :math:`2`, so prior to dividing out by

This line is too long as per the coding-style (111/100).

:math:`2` we have:

* (:math:`n` is even) n and (n + 1)
* (:math:`n` is odd)  n and (n + 1)

Clearly, :math:`n` and :math:`(n + 1)` are co-prime, therefore, the two terms in each case are pair-wise co-prime.

This line is too long as per the coding-style (114/100).

Since these terms are co-prime, the number of divisors in :math:`T_n` can be determined by the number of divisors in

This line is too long as per the coding-style (116/100).

each term.

.. math::

    d(T_n) &= d \\bigg(n \\times \\frac{n + 1}{2} \\bigg) & \\\\
           &= d(n) \\times d \\bigg(\\frac{n + 1}{2} \\bigg)     & \\; \\; \\; \\mbox{(if n is odd)} \\\\

This line is too long as per the coding-style (105/100).

           &= d \\bigg(\\frac{n}{2} \\bigg) \\times d(n + 1)       & \\; \\; \\; \\mbox{(if n is even)}

This line is too long as per the coding-style (103/100).

So, the overall solution is to build a sieve on the number of divisors in the range :math:`n=1,\\dots,answer`

This line is too long as per the coding-style (109/100).

Finally, we may set a reasonable upper-bound on :math:`answer` by applying the following:

.. math::

    & d(answer) \\lt 2 \\times \\sqrt{answer} \\mbox{ and } d(answer) \\gt 500 \\\\
    & \\Rightarrow 500 \\lt d(answer) \\lt 2 \\times \\sqrt{answer} \\\\
    & \\Rightarrow \\frac{500}{2} \\lt \\sqrt{answer} \\\\
    & \\Rightarrow 250 \\lt \\sqrt{answer} \\\\
    & \\Rightarrow \\sqrt{answer} \\gt 250 \\\\
    & \\Rightarrow answer \\gt 250^2

While this range will be sufficient, it may be excessive. This algorithm computes the solution quickly enough so I won't

This line is too long as per the coding-style (120/100).

investigate a tighter bound on :math:`n`.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem12.py
   :language: python
   :lines: 97-
"""

from lib.numbertheory import divisors_sieve, is_even


def solve():
    """ Compute the answer to Project Euler's problem #12 """

    target = 500  # target number of divisors
    limit = (target // 2) ** 2  # search limit for the sieve

    # Build the number of divisors sieve
    divisors = divisors_sieve(limit, proper=False, aggregate="count")
    sieve = {n + 1: divisors_count for n, divisors_count in enumerate(divisors)}

    # Search through the sieve for the first T_n exceeding the targeted number of divisors
    answer = None
    for n in range(1, limit - 1):

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        if is_even(n):
            n_divisors = sieve[n // 2] * sieve[n + 1]
        else:
            n_divisors = sieve[n] * sieve[(n + 1) // 2]
        if n_divisors > target:
            answer = n * (n + 1) // 2
            break

    return answer


expected_answer = 76576500

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).