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.
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)