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:
For \((a,b,c)\) to be \(d\)pandigital, the total number of digits in all integers must equal \(d\):
Combining these two facts sets up useful constraints on \(b\), given \(a\) and \(d\):
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\).
This leads to an upperbound on the number of digits in \(a\):
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 targetpandigital numbers
a_max = base ** ((target  1) // 2) # upperbound on a
# Perform search over a and b looking for targetpandigital 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 (halfopen interval)
b_upper = base ** (b_upper_digits  a_len) # maximum value of b (halfopen 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 targetpandigital numbers 'product'
# Sum all unique targetpandigital integers
answer = sum(pandigitals)
return answer
expected_answer = 45228

solutions.problem32.
solve
()¶ Compute the answer to Project Euler’s problem #32