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,

Project Euler Problem 38

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:

  1. has exactly 9 digits,
  2. contains digits $1$–$9$ exactly once,
  3. 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:

  1. exactly 9 digits,
  2. digits are precisely $1$ through $9$.

Using a set automatically removes duplicates.


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