# Project Euler Problem 38: Pandigital Multiples¶

The source code for this problem can be found here.

## Problem Statement¶

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

$\begin{split}192 \times 1 &= 192 \\ 192 \times 2 &= 384 \\ 192 \times 3 &= 576\end{split}$

By concatenating each product we get the $$1$$ to $$9$$ pandigital, $$192384576$$. We will call $$192384576$$ the concatenated product of $$192$$ and $$(1,2,3)$$.

The same can be achieved by starting with $$9$$ and multiplying by $$1,2,3,4,$$ and $$5$$, giving the pandigital, $$918273645$$, which is the concatenated product of $$9$$ and $$(1,2,3,4,5)$$.

What is the largest $$1$$ to $$9$$ pandigital $$9$$-digit number that can be formed as the concatenated product of an integer with $$(1,2,\dots,n)$$ where $$n \gt 1$$?

## Solution Discussion¶

We’re given that $$n \gt 1$$, but can we establish an upper-bound? Yes.

Observe that if $$n = 10$$, then the concatenated product must have at least $$10$$ digits. This cannot be $$1$$ though $$9$$ pandigital as it contains too many digits. Therefore, $$n \le 9$$.

Let $$x$$ be a $$y$$-digit number

Observe that $$1 \times x$$ is obviously a $$y$$-digit number but other, higher, multiples of $$x$$ are either $$y$$ or $$y+1$$ -digit numbers.

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

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

Recall that we already have a $$9$$-digital pandigitial number $$918273645$$, and that we are searching for a higher one as a result of the concatenated product operation. So, we can assume that if a larger pandigital number exists, it too is $$9$$ digits long. We must constrain $$y$$ s.t. there are $$9$$-digit numbers in the search space.

$$\therefore n = 2 \Rightarrow y \in \lbrace 4 \rbrace$$

By similar analysis we can establish the following results for other values of $$n$$.

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

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

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

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

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

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

$$n = 9 \Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x || 9x$$ which will have digits in the range of $$[9y, 9y+8] \Rightarrow y \in \lbrace 1 \rbrace$$

For any case where $$y \gt 1$$, we can further refine the search. Since $$x \times 1$$ will be included in the concatenated product, $$x$$ itself cannot contain any repeated digits. So, we can search through increasing integers starting from $$1, 12, 123, 1234, \dots$$ which are the smallest integers of lengths $$1, 2, 3, 4, \dots$$ without repeated digits.

Now, we have an algorithm. Search through $$n \in [2, 9]$$, and for each $$n$$, consider $$a$$ in the range specified above corresponding to $$n$$. For each $$(a, n)$$, build the concatenated product. The answer is simply the maximal concatenated product.

## Solution Implementation¶

from lib.digital import num_digits, is_pandigital

def concatenated_product(a: int, n: int) -> int:
""" 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
for val in vals:
z = z * (10 ** num_digits(val)) + val

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

# 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),
7: (1, 10 ** 1), 8: (1, 10 ** 1), 9: (1, 10 ** 1)}

# Perform the search
for n in range(2, 10):
for a in range(*bounds[n]):
concat_prod = concatenated_product(a, n)
if is_pandigital(concat_prod, 9):

Build the concatenated product $$a$$ and $$(1, 2, \dots, n)$$
The concatenated product of $$a$$ and $$(1, 2, \dots, n)$$ is defined as $$(1 \times a) || (2 \times a) || \dots || (n \times a)$$
Parameters: a (int) – the base integer n (int) – the number of products in the concatenated product int the concatenated product of $$a$$ and $$(1, 2, \dots, n)$$