Project Euler Problem 43

Project Euler Problem 43

Solution

Answer: 16695334890

1. Mathematical analysis

We seek all 0–9 pandigital numbers $d_1d_2\dots d_{10}$ satisfying:

$$d_2d_3d_4 \equiv 0 \pmod 2$$

$$d_3d_4d_5 \equiv 0 \pmod 3$$

$$d_4d_5d_6 \equiv 0 \pmod 5$$

$$d_5d_6d_7 \equiv 0 \pmod 7$$

$$d_6d_7d_8 \equiv 0 \pmod {11}$$

$$d_7d_8d_9 \equiv 0 \pmod {13}$$

$$d_8d_9d_{10} \equiv 0 \pmod {17}$$

A brute force over all $10! = 3,628,800$ pandigital numbers is possible, but we can exploit the structure.

Key observations

1. Divisibility by 5

Since $d_4d_5d_6$ must be divisible by 5:

$$d_6 \in {0,5}$$

But digits are unique and later constraints eliminate many possibilities.

2. Overlapping windows

Each divisibility rule involves a 3-digit overlapping substring:

• $d_2d_3d_4$
• $d_3d_4d_5$
• $d_4d_5d_6$
• etc.

This suggests building numbers backwards.

Example:

Start from a 3-digit multiple of 17 for $d_8d_9d_{10}$.

Then prepend a digit to make a multiple of 13:

$$d_7d_8d_9 \equiv 0 \pmod{13}$$

Continue:

$$13 \to 11 \to 7 \to 5 \to 3 \to 2$$

At each stage we only keep candidates with distinct digits.

This prunes the search dramatically.

Backtracking idea

Suppose we already have:

$$d_8d_9d_{10}=289$$

Since $728$ is divisible by $13$, we prepend $7$:

$$7289$$

Then because $572$ is divisible by $11$:

$$57289$$

Continue until all digits are placed.

Finally insert the missing leading digit $d_1$.

The problem statement’s example

$$1406357289$$

is generated exactly this way.

---

2. Python implementation

from itertools import permutations

def solve():
    primes = [17, 13, 11, 7, 5, 3, 2]

    # Start with valid 3-digit multiples of 17
    candidates = []

    for n in range(17, 1000, 17):
        s = f"{n:03d}"  # preserve leading zeros
        if len(set(s)) == 3:
            candidates.append(s)

    # Build numbers backwards using substring divisibility
    for p in primes[1:]:
        new_candidates = []

        for candidate in candidates:
            used = set(candidate)

            for digit in "0123456789":
                if digit in used:
                    continue

                # Form new 3-digit substring
                triple = digit + candidate[:2]

                if int(triple) % p == 0:
                    new_candidates.append(digit + candidate)

        candidates = new_candidates

    total = 0

    # Add the missing first digit
    for candidate in candidates:
        missing_digit = (
            set("0123456789") - set(candidate)
        ).pop()

        pandigital = int(missing_digit + candidate)
        total += pandigital

    return total

print(solve())

---

3. Code walkthrough

Step 1: Define divisibility sequence

primes = [17, 13, 11, 7, 5, 3, 2]

We process the constraints backwards.

Why backwards?

Because the last constraint only depends on:

$$d_8d_9d_{10}$$

Once those digits are fixed, earlier windows overlap naturally.

---

Step 2: Generate valid endings

for n in range(17, 1000, 17):

We enumerate all multiples of 17 below 1000.

s = f"{n:03d}"

This preserves leading zeros.

Example:

17 → "017"

which is important because substrings like 063 are allowed.

We keep only numbers with distinct digits:

if len(set(s)) == 3:

---

Step 3: Extend candidates backward

For each prime:

for p in primes[1:]:

we prepend one digit.

Suppose candidate is:

289

and prime is 13.

We try digits:

728

because:

$$728 \div 13 = 56$$

So we prepend 7:

7289

This maintains overlap:

• new triple = first 3 digits
• last two digits automatically align

---

Step 4: Complete pandigital number

After all divisibility rules are satisfied, one digit remains unused.

missing_digit = (
    set("0123456789") - set(candidate)
).pop()

Prepend it:

pandigital = int(missing_digit + candidate)

and sum all valid numbers.

---

Small example verification

The example number:

$$1406357289$$

satisfies:

• $406 \div 2$
• $063 \div 3$
• $635 \div 5$
• $357 \div 7$
• $572 \div 11$
• $728 \div 13$
• $289 \div 17$

All are integers, confirming correctness.

---

4. Final verification

There are only a small number of valid pandigital numbers satisfying all constraints, so the total should be on the order of tens of billions (each number is about $10^{10}$).

The computed sum is:

$$16,!695,!334,!890$$

which is plausible in magnitude and matches all divisibility constraints.

Answer: 16695334890