nekedome / project-euler

solutions/problem5.py

"""
Project Euler Problem 5: Smallest Multiple
==========================================

.. module:: solutions.problem5
   :synopsis: My solution to problem #5.

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

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

:math:`2520` is the smallest number that can be divided by each of the numbers from :math:`1` to :math:`10` without any
remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from :math:`1` to :math:`20`?

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

:math:`2520` is the smallest multiple of all numbers :math:`1` through :math:`10`, which means that any multiple of
:math:`2520` is also divisible by :math:`1` through :math:`10`. Any non-multiple will not be divisible by ALL numbers
:math:`1` through :math:`10`, so can be ignored.

Divisibility by the numbers :math:`11` through :math:`20` should be tested from highest (:math:`20`) to lowest
(:math:`11`) since higher divisors will rule more candidates out by in-divisibility. More explicitly, :math:`19` out of
every :math:`20` integers are not divisible by :math:`20` whereas only :math:`18` out of every :math:`19` integers are
not divisible by :math:`19`. This is akin to lazy boolean logic evaluation and avoids redundant computation.

Using these insights, a simple search strategy will find the answer very quickly. More specifically, search through
increasing multiples of :math:`2520` testing for divisibility by :math:`20,19,\\dots,11` - in that order. Identify the
first, and thus smallest such number.

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

.. literalinclude:: ../../solutions/problem5.py
   :language: python
   :lines: 43-
"""

from typing import List


def is_multiple(n: int, divisors: List[int]) -> bool:

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

    """ Check whether :math:`n` is divisible by all of the given :math:`divisors`

    :param n: the integer to check for divisibility
    :param divisors: the divisors to test :math:`n` with
    :return: whether :math:`n` is divisible by all :math:`divisors` or not
    """

    for m in divisors:

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

        if n % m != 0:
            return False
    return True


def solve():
    """ Compute the answer to Project Euler's problem #5 """
    divisors = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11]  # reverse order
    n = 2520  # start our search at 2520

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

    while not is_multiple(n, divisors):
        n += 2520  # increment our search by 2520 at a time

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

    return n


expected_answer = 232792560

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