# Project Euler Problem 32: Pandigital Products¶

The source code for this problem can be found here.

## Problem Statement¶

We shall say that an $$n$$-digit number is pandigital if it makes use of all the digits $$1$$ to $$n$$ exactly once; for example, the $$5$$-digit number, $$15234$$, is $$1$$ through $$5$$ pandigital.

The product $$7254$$ is unusual, as the identity, $$39 \times 186 = 7254$$, containing multiplicand, multiplier, and product is $$1$$ through $$9$$ pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a $$1$$ through $$9$$ pandigital.

Note

some products can be obtained in more than one way so be sure to only include it once in your sum.

## Solution Discussion¶

The single example given demonstrates that we need not consider prime factorisations but rather the product of two positive integers; $$a \times b = c$$.

The tuple $$(a,b,c)$$ is defined as $$d$$-pandigital if the digits $$1$$ through $$d$$ appear precisely once in the digits comprising the three integers $$a,b,c$$ when represented in decimal. A pruned search will suffice to find all such $$d$$-pandigital integers.

First, observe that $$c$$ is completely determined by $$a$$ and $$b$$, we need only consider $$a$$ and $$b$$. A naive search over all $$d$$-digit integers $$a$$ and $$b$$ involves a search space of size $$10^{2 \times d}$$. However, this can be reduced by utilising some additional constraints imposed by the problem.

Since we are searching for $$1$$ through $$9$$ pandigital numbers, we know there are no $$0$$ digits. Thus, $$a$$ and $$b$$ are positive integers without leading zeroes and the number of digits in their product is restricted according to:

$\begin{split}&\mbox{Let } c = a \times b \\ &\mbox{Let } |x| \mbox{ be the number of decimal digits in } x \\ &|a| + |b| - 1 \le |c| \le |a| + |b|\end{split}$

For $$(a,b,c)$$ to be $$d$$-pandigital, the total number of digits in all integers must equal $$d$$:

$|a| + |b| + |c| = d$

Combining these two facts sets up useful constraints on $$b$$, given $$a$$ and $$d$$:

$\begin{split}&|a| + |b| - 1 \le |c| \le |a| + |b| \\ \Rightarrow &|a| + |b| + |a| + |b| - 1 \le |a| + |b| + |c| \le |a| + |b| + |a| + |b| \\ \Rightarrow &2|a| + 2|b| - 1 \le d \le 2|a| + 2|b| \\ \Rightarrow &2|b| - 1 \le d - 2|a| \le 2|b| \\ \Rightarrow &d - 2|a| \le 2|b| \mbox{ and } 2|b| - 1 \le d - 2|a| \\ \Rightarrow &\frac{d}{2} - |a| \le |b| \mbox{ and } |b| \le \frac{d + 1}{2} - |a| \\ \Rightarrow &\frac{d}{2} - |a| \le |b| \le \frac{d + 1}{2} - |a|\end{split}$

Finally, the search over possible integers $$a$$ is bound by two overall constraints. Firstly, that $$(a,b,c)$$ must consist of exactly $$d$$ digits and that each integer must be at least one digit. Secondly, that the number of digits in $$c$$ will be at least equal to the number of digits in $$a$$.

$c = a \times b \Rightarrow |c| \ge |a| \mbox{ (for positive integers } a,b,c)$

This leads to an upper-bound on the number of digits in $$a$$:

$\begin{split}&d = |a| + |b| + |c| \ge |a| + |b| + |a| = 2|a| + |b| \\ \Rightarrow &d \ge 2|a| + |b| \\ &\mbox{Since } |b| \ge 1, 2|a| + |b| \ge 2|a| + 1 \\ \Rightarrow &d \ge 2|a| + 1 \\ \Rightarrow &\frac{d - 1}{2} \ge |a| \\ \Rightarrow &1 \le |a| \le \frac{d - 1}{2} \mbox{ (since all } a,b,c \mbox{ must be at least one digit)}\end{split}$

## Solution Implementation¶

from lib.digital import is_pandigital, num_digits

def solve():
""" Compute the answer to Project Euler's problem #32 """

# Problem specific parameters
base = 10  # use decimal representation
target = 9  # searching for target-pandigital numbers
a_max = base ** ((target - 1) // 2)  # upper-bound on a

# Perform search over a and b looking for target-pandigital numbers
pandigitals = set()
for multiplicand in range(1, a_max):  # search over values of a
a_len = num_digits(multiplicand)
b_lower_digits = (target + 1) // 2 - 1  # minimum number of digits in b
b_upper_digits = target // 2 + 1  # maximum number of digits in b
b_lower = base ** (b_lower_digits - a_len)  # minimum value of b (half-open interval)
b_upper = base ** (b_upper_digits - a_len)  # maximum value of b (half-open interval)

for multiplier in range(b_lower, b_upper):  # search over values of b
product = multiplicand * multiplier  # compute c = a * b

if is_pandigital([multiplicand, multiplier, product], target, 1, base):
pandigitals.add(product)  # save any unique target-pandigital numbers 'product'

# Sum all unique target-pandigital integers

solutions.problem32.solve()