Project Euler 38: Find the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 2, 3, 4, or 5

Problem Description

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

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
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, … , n) where n > 1?

Analysis

We need to find a 1 to 9, 9-digit pandigital number greater than 918273645 mentioned above (otherwise 918273645 would be the answer, and we tried that, and it wasn’t). So we know that the first product in our concatenated sequence must start with a 9.

• Well, that rules out two digit integers 92 through 98 multiplied by (2, 3, 4) because they can’t make a 9-digit concatenated product.
• And, rule out three digit integers 921 through 987 multiplied by (2, 3, 4) for the same reason.
• Four digit integers 9213 through 9876 multiplied by (2, 3, 4) will yield a 9-digit number for only 2.
• No other combination works. They all create too many digits.

So, if one exists, we start from 9876 and count down multiplying our candidate by 1 and 2 and checking the concatenated products for pandigitality.

UPDATE:
Kristian points out that the second digit in our upper limit must be < 5 otherwise the multiplication by 2 will yeild a nine in the product, but a nine already exists in the first multiplication. We can’t have two.

Project Euler 38 Solution

Afterthoughts

• Function is_pandigital is listed in Common Functions and Routines for Project Euler