Project Euler Problem 38
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,
Solution
Answer: 932718654
We seek the largest 9-digit pandigital number formed by concatenating
$$x \times 1,; x \times 2,; \dots,; x \times n$$
for some integer $x$ and some $n>1$.
A number is 1-to-9 pandigital if it uses each digit $1,2,\dots,9$ exactly once.
Mathematical analysis
Let
$$P(x,n)=\text{concat}(x,2x,3x,\dots,nx).$$
We want the largest possible $P(x,n)$ that:
- has exactly 9 digits,
- contains digits $1$–$9$ exactly once,
- uses $n>1$.
Step 1: Restrict the size of $x$
Suppose $x$ has $d$ digits.
Since we concatenate at least two numbers ($n>1$), the total length must be 9.
If $d=5$
Then:
- $x\times1$ already has 5 digits,
- $x\times2$ has at least 5 digits,
so concatenation has at least 10 digits.
Impossible.
If $d=4$
Then concatenating $x$ and $2x$ gives either:
- $4+4=8$ digits, or
- $4+5=9$ digits.
To get exactly 9 digits, we need:
$$\text{len}(x)=4,\qquad \text{len}(2x)=5.$$
Thus $x\ge 5000$.
Also, since we want the largest pandigital number, a 4-digit prefix is advantageous because the concatenation begins with $x$ itself.
Hence the optimal solution is very likely among 4-digit values with $n=2$.
Step 2: Search strategy
We test integers $x$ and form:
$$s = \text{str}(x) + \text{str}(2x) + \cdots$$
until the concatenated string has length at least 9.
Then check:
- length is exactly 9,
- digits are exactly ${1,2,\dots,9}$.
A quick pandigital test is:
set(s) == set("123456789")
and len(s) == 9.
Step 3: Reason about the maximum
Because the concatenated number begins with $x$, maximizing the result means maximizing the leading digits.
Among 4-digit candidates, we search downward from 9876.
The known strong candidate:
$$9327 \times (1,2)$$
gives
$$9327;18654 = 932718654.$$
Digits used:
$$1,2,3,4,5,6,7,8,9$$
exactly once.
So this is pandigital.
We then verify no larger valid candidate exists.
Python implementation
def is_pandigital_1_to_9(s):
"""
Return True if s contains each digit 1-9 exactly once.
"""
return len(s) == 9 and set(s) == set("123456789")
largest = 0
# Try possible base integers
for x in range(1, 10000):
concatenated = ""
n = 1
# Keep appending x*n until length reaches 9
while len(concatenated) < 9:
concatenated += str(x * n)
n += 1
# Check if we formed a valid pandigital number
if is_pandigital_1_to_9(concatenated):
largest = max(largest, int(concatenated))
print(largest)
Code walkthrough
Function definition
def is_pandigital_1_to_9(s):
Defines a helper function to test pandigitality.
return len(s) == 9 and set(s) == set("123456789")
Checks two conditions:
- exactly 9 digits,
- digits are precisely $1$ through $9$.
Using a set automatically removes duplicates.
Main search
largest = 0
Stores the best answer found.
for x in range(1, 10000):
We only need $x<10000$, since 5-digit values cannot work.
concatenated = ""
n = 1
Start building the concatenated product.
while len(concatenated) < 9:
concatenated += str(x * n)
n += 1
Append:
$$x\times1,\ x\times2,\ x\times3,\dots$$
until the string reaches length at least 9.
if is_pandigital_1_to_9(concatenated):
Check whether the result is a valid 1–9 pandigital number.
largest = max(largest, int(concatenated))
Keep the largest valid value.
print(largest)
Outputs the final answer.
Verification with examples
Example 1
For $x=192$:
$$192\times1=192$$
$$192\times2=384$$
$$192\times3=576$$
Concatenation:
$$192384576$$
This is pandigital.
Example 2
For $x=9$:
$$9\times(1,2,3,4,5)$$
gives:
$$918273645$$
also pandigital.
Maximum candidate
The search finds:
$$932718654$$
generated by:
$$9327 \times (1,2)$$
since:
$$9327 \times 1 = 9327$$
$$9327 \times 2 = 18654$$
Concatenation:
$$932718654$$
which is 1–9 pandigital.
No larger valid concatenated product exists.
Final verification
- Exactly 9 digits ✔
- Uses digits $1$–$9$ once each ✔
- Formed from concatenated products with $n>1$ ✔
- Larger than the example $918273645$ ✔
Therefore the result is correct.
Answer: 932718654