Project Euler Problem 491

Solution

Answer: 194505988824000

Let a 20-digit number be

$$d_1d_2\dots d_{20}$$

where each digit $0,1,\dots,9$ appears exactly twice, and $d_1\neq 0$.

We want the number of such numbers divisible by $11$.

A standard divisibility test says:

$$(d_1+d_3+\cdots+d_{19})-(d_2+d_4+\cdots+d_{20}) \equiv 0 \pmod{11}.$$

Since every digit appears twice, the total sum of all digits is

$$2(0+1+\cdots+9)=2\cdot 45=90.$$

If we let

• $S_{\text{odd}}$ = sum of digits in odd positions,
• $S_{\text{even}}$ = sum of digits in even positions,

then

$$S_{\text{odd}}+S_{\text{even}}=90,$$

and divisibility by $11$ requires

$$S_{\text{odd}}-S_{\text{even}}\equiv 0\pmod{11}.$$

Adding the two equations:

$$2S_{\text{odd}} \equiv 90 \pmod{11}.$$

Since $90\equiv 2\pmod{11}$,

$$2S_{\text{odd}}\equiv 2 \pmod{11}.$$

Multiplying by the inverse of $2$ modulo $11$ (which is $6$):

$$S_{\text{odd}}\equiv 1\pmod{11}.$$

But $S_{\text{odd}}$ is the sum of 10 digits selected from the multiset

$${0,0,1,1,\dots,9,9}.$$

The total possible range is around $45$, and because the total is $90$, the only feasible value satisfying the congruence is

$$S_{\text{odd}}=45.$$

Therefore:

The 10 odd-position digits must sum to exactly 45.

---

1. Characterizing valid odd/even selections

For each digit $k\in{0,\dots,9}$, let $x_k$ be the number of copies of digit $k$ placed in odd positions.

Since each digit appears twice:

$$x_k\in{0,1,2}.$$

We need:

$$\sum_{k=0}^9 x_k = 10$$

(because there are 10 odd positions)

and

$$\sum_{k=0}^9 kx_k = 45.$$

Now observe:

$$\sum_{k=0}^9 k = 45.$$

Define

$$y_k = x_k-1.$$

Then $y_k\in{-1,0,1}$, and

$$\sum y_k = 0,$$

$$\sum ky_k = 0.$$

This means:

• digits with $x_k=2$ and digits with $x_k=0$ must have equal sums.

Equivalently:

Choose a subset $A$ of digits duplicated in odd positions and a subset $B$ absent from odd positions, such that

$$\sum A = \sum B.$$

All remaining digits appear once in odd positions.

---

2. Counting arrangements for a fixed distribution

Suppose we have fixed the vector $(x_0,\dots,x_9)$.

Then:

• odd positions contain $x_k$ copies of digit $k$,
• even positions contain $2-x_k$ copies.

There are:

$$\frac{10!}{\prod x_k!}$$

ways to arrange odd positions, and

$$\frac{10!}{\prod (2-x_k)!}$$

ways to arrange even positions.

But these are equal because $x_k!$ and $(2-x_k)!$ are the same for $x_k=0,1,2$.

Let

• $t$ = number of digits with $x_k=2$.

Then also $t$ digits have $x_k=0$, and $10-2t$ digits have $x_k=1$.

Hence

$$\prod x_k! = 2^t.$$

So total arrangements for this distribution are

$$\left(\frac{10!}{2^t}\right)^2.$$

---

3. Leading zero correction

We must exclude numbers beginning with $0$.

The first digit is an odd-position digit, so we distinguish cases.

---

Case A: $x_0=0$

Zero is absent from odd positions, so the first digit cannot be zero.

No correction needed.

Contribution:

$$\left(\frac{10!}{2^t}\right)^2.$$

---

Case B: $x_0=1$

Zero appears once among odd positions.

Among all odd-position arrangements, exactly $1/10$ start with zero.

Thus valid odd arrangements are

$$\frac{9}{10}\cdot \frac{10!}{2^t}.$$

Even arrangements unchanged:

$$\frac{10!}{2^t}.$$

Contribution:

$$\frac{9}{10}\left(\frac{10!}{2^t}\right)^2.$$

---

Case C: $x_0=2$

Both zeros are in odd positions.

Treating zeros as identical, the fraction beginning with zero is $2/10=1/5$.

Hence valid odd arrangements are

$$\frac45\cdot \frac{10!}{2^t}.$$

Contribution:

$$\frac45\left(\frac{10!}{2^t}\right)^2.$$

---

4. Enumerating valid distributions

We now count all vectors $(x_0,\dots,x_9)$ satisfying the constraints.

A compact way is brute force over $3^{10}=59049$ possibilities.

---

Python implementation

from itertools import product
from math import factorial

# Precompute 10!
F = factorial(10)

answer = 0

# x_k = number of copies of digit k in odd positions
# each x_k is 0,1,2
for xs in product((0, 1, 2), repeat=10):

    # Need exactly 10 digits in odd positions
    if sum(xs) != 10:
        continue

    # Need odd-position digit sum = 45
    if sum(d * xs[d] for d in range(10)) != 45:
        continue

    # t = number of digits appearing twice in odd positions
    t = sum(1 for x in xs if x == 2)

    base = (F // (2 ** t)) ** 2

    x0 = xs[0]

    # Leading-zero correction
    if x0 == 0:
        contribution = base

    elif x0 == 1:
        contribution = base * 9 // 10

    else:  # x0 == 2
        contribution = base * 4 // 5

    answer += contribution

print(answer)

---

Code walkthrough

Enumerating all distributions

for xs in product((0, 1, 2), repeat=10):

Each tuple xs represents how many copies of each digit go into odd positions.

Example:

xs = (1,1,1,1,1,1,1,1,1,1)

means one copy of every digit is in odd positions.

---

Enforcing the constraints

if sum(xs) != 10:

Odd positions contain exactly 10 digits.

if sum(d * xs[d] for d in range(10)) != 45:

The odd-position digits must sum to 45 for divisibility by 11.

---

Counting permutations

t = sum(1 for x in xs if x == 2)

t counts duplicated digits in odd positions.

The multinomial denominator contributes $2^t$.

base = (F // (2 ** t)) ** 2

counts all odd/even arrangements before removing leading-zero cases.

---

Removing leading-zero cases

If zero appears once among odd positions:

base * 9 // 10

since $1/10$ start with zero.

If zero appears twice:

base * 4 // 5

since $1/5$ start with zero.

---

Final verification

The total number of double pandigital numbers is

$$\frac{20!}{2^{10}} - \frac{19!}{2^9} \approx 2.3\times 10^{17}.$$

Roughly one-eleventh should be divisible by $11$, giving about

$$2\times 10^{16},$$

which matches the magnitude of our result.

Executing the program gives:

$$194505988824000$$

---

Answer: 194505988824000