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
    answer = sum(pandigitals)
    return answer


expected_answer = 45228

solutions.problem32.solve()

Compute the answer to Project Euler’s problem #32