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\):
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):
answer = max(answer, concat_prod)
return answer
expected_answer = 932718654
-
solutions.problem38.concatenated_product(a, n)¶ 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
Return type: intReturns: the concatenated product of \(a\) and \((1, 2, \dots, n)\)
- a (
-
solutions.problem38.solve()¶ Compute the answer to Project Euler’s problem #38