nekedome / project-euler

solutions/problem21.py

"""
Project Euler Problem 21: Amicable Numbers
==========================================

.. module:: solutions.problem21
   :synopsis: My solution to problem #21.

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

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

Let :math:`d(n)` be defined as the sum of proper divisors of :math:`n` (numbers less than :math:`n` which divide evenly

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

into :math:`n`).

If :math:`d(a) = b` and :math:`d(b) = a`, where :math:`a \\neq b`, then :math:`a` and :math:`b` are an amicable pair and

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

each of :math:`a` and :math:`b` are called amicable numbers.

For example, the proper divisors of :math:`220` are :math:`1, 2, 4, 5, 10, 11, 20, 22, 44, 55` and :math:`110`;

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

therefore :math:`d(220) = 284`. The proper divisors of :math:`284` are :math:`1, 2, 4, 71` and :math:`142`; so

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

:math:`d(284) = 220`.

Evaluate the sum of all the amicable numbers under :math:`10000`.

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

Pre-compute :math:`d(n)` for all :math:`n` in our search space and then iterate over :math:`n` searching for

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

:math:`d(n) = m` and :math:`d(m) = n` where :math:`n \\neq m`. Compute the sum of all such :math:`(n, m)`.

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

.. note:: the pre-computation of :math:`d(n)` for an increasing :math:`n` can be drastically sped up by using sieving

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

          techniques. An alternative, but inferior, method would be to find the divisors of increasing values of

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

          :math:`n` via factorisation.

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

.. literalinclude:: ../../solutions/problem21.py
   :language: python
   :lines: 44-
"""

from lib.numbertheory.sieve import divisors_sieve


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

    # Pre-compute d(n) for all n in [2, 9999]
    target = 10000
    divisor_counts = divisors_sieve(target - 1, proper=True, aggregate="sum")
    d_vals = {n + 1: div_count for n, div_count in enumerate(divisor_counts)}
    del d_vals[1]  # divisors_sieve covers the closed interval [1, target - 1], remove d(1)

    # Identify amicable numbers
    amicable_numbers = set()
    for n, d_n in d_vals.items():

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

        if d_n in d_vals and d_vals[d_n] == n and n != d_n:
            amicable_numbers.add(n)
            amicable_numbers.add(d_n)

    # Sum all amicable numbers
    answer = sum(amicable_numbers)
    return answer


expected_answer = 31626

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