Back to index

The problem: https://projecteuler.net/problem=38.

Let's denote by $x @ n$ the concatenated product of $x$ and $(1, 2, 3, ..., n)$ and denote by $d(q)$ the number of digits of the number $q$. It is clear that $d(x) \leq 9$. Another thing is that for $x @ n$ be a 1 through 9 pandigital, need $d(x)n \leq 9$ since $d(x @ n) \geq n d(x)$ and we want $d(x @ n) = 9$. Another thing is that if $d(x) \geq 5$, then $x @ n$ can't be a 1 through 9 pandigital. This is because $n \geq 2$ (as it's specified in the problem statement), and then $d(x @ n) \geq n d(x) \geq 10 > 9$. So we need only to test numbers with $k$ digits, where $k \in \{1, 2, 3, 4\}.$

We can actually program our test loop so that these constraints emerge from the code.

In [1]:
def digits_of(num):
    assert num >= 0
    if num == 0:
        return [0]
    digits = []
    while num > 0:
        d = num % 10
        num //= 10
        digits.append(d)
    digits.reverse()
    return digits
    
def concatenated_product(x, n):
    digits_pieces = [digits_of(x*(i+1)) for i in range(n)]
    all_digits = []
    for piece in digits_pieces:
        all_digits.extend(piece)
    return all_digits

def is_pandigital(digits_of):
    found = [0]*10
    for d in digits_of:
        assert 0 <= d and d <= 9
        found[d] += 1
    for d in range(9):
        if found[d+1] != 1:
            return False
    return found[0] == False

def digits_to_integer(digits):
    val = 0
    for d in digits:
        val *= 10
        val += d
    return val

max_pandigital_so_far = -1
num_digits = 1
while num_digits <= 9:
    lower = 10**(num_digits-1)
    upper = lower*10
    n = 2
    while n*num_digits <= 9:
        x = lower
        while x < upper:
            c = concatenated_product(x, n)
            if is_pandigital(c):
                val = digits_to_integer(c)
                if val > max_pandigital_so_far:
                    max_pandigital_so_far = val
            x += 1
        n += 1
    num_digits += 1

print("Answer is", max_pandigital_so_far)
Answer is 932718654