Project Euler Problem 32

Solution

Answer: 45228

We seek all identities

$$a \times b = c$$

such that when the decimal digits of $a$, $b$, and $c$ are concatenated, we obtain a $1$-through-$9$ pandigital number: every digit $1,2,\dots,9$ appears exactly once.

We must sum all distinct products $c$.

---

Mathematical analysis

Let:

• multiplicand $= a$
• multiplier $= b$
• product $= c$

The concatenation of $a,b,c$ uses exactly 9 digits total.

Step 1 — Determine possible digit lengths

Suppose:

• $a$ has $m$ digits
• $b$ has $n$ digits
• $c$ has $p$ digits

Then:

$$m+n+p=9$$

Also, multiplication roughly satisfies:

$$p \approx m+n \quad \text{or} \quad m+n-1$$

because multiplying an $m$-digit number by an $n$-digit number produces either an $(m+n)$-digit or $(m+n-1)$-digit number.

Substitute into the digit condition:

$$m+n+p=9$$

If $p=m+n$, then:

$$2(m+n)=9$$

impossible.

Hence necessarily:

$$p=m+n-1$$

So:

$$m+n+(m+n-1)=9$$

$$2(m+n)=10$$

$$m+n=5$$

and therefore:

$$p=4$$

So the product must be a 4-digit number, and the multiplicands together use 5 digits.

Possible splits:

• $1$-digit × $4$-digit $=4$-digit
• $2$-digit × $3$-digit $=4$-digit

No other cases work.

---

Step 2 — Brute-force search strategy

We can directly test all possibilities.

For every candidate pair $(a,b)$:

1. Compute:

$$c=a\times b$$ 2. Form the string:

$$s = \text{str}(a)+\text{str}(b)+\text{str}(c)$$ 3. Check:

• length is 9
• digits are exactly $1,\dots,9$
• no zero appears
• no repeated digits

To avoid counting duplicate products multiple times, store valid products in a set.

Finally compute:

$$\sum \text{(distinct products)}$$

---

Python implementation

def is_pandigital(a, b, c):
    """
    Return True if concatenating a, b, c produces
    a 1-through-9 pandigital number.
    """
    s = str(a) + str(b) + str(c)

    # Must use exactly 9 digits
    if len(s) != 9:
        return False

    # Digits must be exactly 1..9
    return set(s) == set("123456789")

products = set()

# Case 1:
# 1-digit × 4-digit = 4-digit
for a in range(1, 10):
    for b in range(1000, 10000):
        c = a * b

        if is_pandigital(a, b, c):
            products.add(c)

# Case 2:
# 2-digit × 3-digit = 4-digit
for a in range(10, 100):
    for b in range(100, 1000):
        c = a * b

        if is_pandigital(a, b, c):
            products.add(c)

# Sum all distinct products
answer = sum(products)

print(answer)

---

Code walkthrough

Function: is_pandigital

s = str(a) + str(b) + str(c)

Concatenates the decimal representations.

Example:

39 × 186 = 7254

gives:

"391867254"

---

if len(s) != 9:
    return False

A valid identity must use exactly 9 digits.

---

return set(s) == set("123456789")

A set removes duplicates, so this guarantees:

• every digit $1$-$9$ appears
• no repeated digits
• no zero

---

First search block

for a in range(1, 10):
    for b in range(1000, 10000):

Checks all:

$$1\text{-digit} \times 4\text{-digit}$$

cases.

---

Second search block

for a in range(10, 100):
    for b in range(100, 1000):

Checks all:

$$2\text{-digit} \times 3\text{-digit}$$

cases.

---

Using a set

products = set()

Some products can arise from multiple identities.

The problem explicitly says to count each product only once.

---

Example verification

The example from the problem:

$$39 \times 186 = 7254$$

produces:

"391867254"

which contains every digit $1$-$9$ exactly once.

So:

7254

is included.

---

Final verification

The valid products found are:

$$4396,\ 5346,\ 5796,\ 6952,\ 7254,\ 7632,\ 7852$$

Their sum is:

$$4396+5346+5796+6952+7254+7632+7852 =45228$$

This magnitude is reasonable:

• only a handful of pandigital identities exist,
• all products are 4-digit numbers,
• total is therefore on the order of tens of thousands.

Therefore the computation is consistent.

---

Answer: 45228