nekedome / project-euler

solutions/problem38.py

"""
Project Euler Problem 38: Pandigital Multiples
==============================================

.. module:: solutions.problem38
   :synopsis: My solution to problem #38.

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

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

Take the number :math:`192` and multiply it by each of :math:`1,2,` and :math:`3`:

.. math::

    192 \\times 1 &= 192 \\\\
    192 \\times 2 &= 384 \\\\
    192 \\times 3 &= 576

By concatenating each product we get the :math:`1` to :math:`9` pandigital, :math:`192384576`. We will call

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

:math:`192384576` the concatenated product of :math:`192` and :math:`(1,2,3)`.

The same can be achieved by starting with :math:`9` and multiplying by :math:`1,2,3,4,` and :math:`5`, giving the

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

pandigital, :math:`918273645`, which is the concatenated product of :math:`9` and :math:`(1,2,3,4,5)`.

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

What is the largest :math:`1` to :math:`9` pandigital :math:`9`-digit number that can be formed as the concatenated

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

product of an integer with :math:`(1,2,\\dots,n)` where :math:`n \\gt 1`?

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

We're given that :math:`n \\gt 1`, but can we establish an upper-bound? Yes.

Observe that if :math:`n = 10`, then the concatenated product must have at least :math:`10` digits. This cannot be

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

:math:`1` though :math:`9` pandigital as it contains too many digits. Therefore, :math:`n \\le 9`.

Let :math:`x` be a :math:`y`-digit number

Observe that :math:`1 \\times x` is obviously a :math:`y`-digit number but other, higher, multiples of :math:`x` are

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

either :math:`y` or :math:`y+1` -digit numbers.

Now, consider the properties of the concatenated products for various values of :math:`n \\in [2, 9]`.

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

:math:`n = 2 \\Rightarrow 1x || 2x` which will have digits in the range of :math:`[2y, 2y+1]`

Recall that we already have a :math:`9`-digital pandigitial number :math:`918273645`, and that we are searching for a

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

higher one as a result of the concatenated product operation. So, we can assume that if a larger pandigital number

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

exists, it too is :math:`9` digits long. We must constrain :math:`y` s.t. there are :math:`9`-digit numbers in the

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

search space.

:math:`\\therefore n = 2 \\Rightarrow y \\in \\lbrace 4 \\rbrace`

By similar analysis we can establish the following results for other values of :math:`n`.

:math:`n = 3 \\Rightarrow 1x || 2x || 3x` which will have digits in the range of
:math:`[3y, 3y+2] \\Rightarrow y \\in \\lbrace 3 \\rbrace`

:math:`n = 4 \\Rightarrow 1x || 2x || 3x || 4x` which will have digits in the range of
:math:`[4y, 4y+3] \\Rightarrow y \\in \\lbrace 2 \\rbrace`

:math:`n = 5 \\Rightarrow 1x || 2x || 3x || 4x || 5x` which will have digits in the range of
:math:`[5y, 5y+4] \\Rightarrow y \\in \\lbrace 1 \\rbrace`

:math:`n = 6 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x` which will have digits in the range of
:math:`[6y, 6y+5] \\Rightarrow y \\in \\lbrace 1 \\rbrace`

:math:`n = 7 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x` which will have digits in the range of

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

:math:`[7y, 7y+6] \\Rightarrow y \\in \\lbrace 1 \\rbrace`

:math:`n = 8 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x` which will have digits in the range of

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

:math:`[8y, 8y+7] \\Rightarrow y \\in \\lbrace 1 \\rbrace`

:math:`n = 9 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x || 9x` which will have digits in the range of

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

:math:`[9y, 9y+8] \\Rightarrow y \\in \\lbrace 1 \\rbrace`

For any case where :math:`y \\gt 1`, we can further refine the search. Since :math:`x \\times 1` will be included in the

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

concatenated product, :math:`x` itself cannot contain any repeated digits. So, we can search through increasing integers

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

starting from :math:`1, 12, 123, 1234, \\dots` which are the smallest integers of lengths :math:`1, 2, 3, 4, \\dots`

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

without repeated digits.

Now, we have an algorithm. Search through :math:`n \\in [2, 9]`, and for each :math:`n`, consider :math:`a` in the range

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

specified above corresponding to :math:`n`. For each :math:`(a, n)`, build the concatenated product. The answer is

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

simply the maximal concatenated product.

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

.. literalinclude:: ../../solutions/problem38.py
   :language: python
   :lines: 95-
"""

from lib.digital import num_digits, is_pandigital


def concatenated_product(a: int, n: int) -> int:

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

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

    """ Build the concatenated product :math:`a` and :math:`(1, 2, \\dots, n)`

    The concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)` is defined as
    :math:`(1 \\times a) || (2 \\times a) || \\dots || (n \\times a)`

    :param a: the base integer
    :param n: the number of products in the concatenated product
    :return: the concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)`
    """

    vals = [i * a for i in range(1, n + 1)]
    z = 0

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

    for val in vals:
        z = z * (10 ** num_digits(val)) + val

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

    return z


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

    answer = 918273645  # we are searching for a greater answer, this will do as a starting value to maximise

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

    # The range of the search space on a for each possible value of n
    bounds = {2: (1234, 10 ** 4), 3: (123, 10 ** 3), 4: (12, 10 ** 2), 5: (1, 10 ** 1), 6: (1, 10 ** 1),

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

              7: (1, 10 ** 1), 8: (1, 10 ** 1), 9: (1, 10 ** 1)}

    # Perform the search
    for n in range(2, 10):

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

        for a in range(*bounds[n]):

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

            concat_prod = concatenated_product(a, n)
            if is_pandigital(concat_prod, 9):
                answer = max(answer, concat_prod)

    return answer


expected_answer = 932718654

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