Project Euler Solution 38: Pandigital multiples

Now we do Problem 38: Pandigital multiples as part of the Project Euler series. This problem is about subsequent multiples of numbers which have unique digits.

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?

To form the potentially pandigital product of a number, I've written a function. It takes the number and then creates subsequent multiples of the number. As soon as a digit occurs twice, the whole thing is discarded. Once there are exactly nine unique digits, the resulting number is returned. We also must not have any zeros in there, because the numbers are supposed to only contain the numbers from 1 to 9.

def pandigital_product(number: int) -> Optional[int]:
    digits = set()
    results = []
    for n in itertools.count(1):
        product = number * n
        product_digits = set(str(product))
        if len(product_digits) != len(str(product)):
            return None
        if "0" in product_digits:
            return None
        if digits & product_digits:
            return None
        else:
            digits |= product_digits
            results.append(product)
            if len(digits) == 9:
                return int("".join(map(str, results)))

A test ensures that the example works correctly.

def test_is_pandigital_product() -> None:
    assert pandigital_product(192) == 192_384_576

With that function available, writing the solution becomes quite straightforward.

def solution() -> int:
    pandigital_products = []
    for start in range(1, 100_000):
        if product := pandigital_product(start):
            pandigital_products.append(product)
    return max(pandigital_products)

This runs in 84 ms, so that is acceptable.

Using sets to track the unique digits makes this manageable. One has to be a bit careful when the product already contains digits multiple times. This is explicitly checked.