Detailed mathematical approach

Problem Summary

A double pandigital number uses each digit \(0,1,\dots,9\) exactly twice, so every valid candidate has 20 digits. We must count those 20-digit numbers that do not start with \(0\) and are divisible by \(11\). Directly permuting a multiset of size 20 is far too expensive, so the solution reorganizes the search around how many copies of each digit are placed in odd positions and how many are forced into even positions.

Mathematical Approach

The divisibility test for \(11\) is the key. For a 20-digit number, let positions \(1,3,5,\dots,19\) be the odd positions and \(2,4,6,\dots,20\) be the even positions. A number is divisible by \(11\) exactly when the alternating digit sum is a multiple of \(11\).

Step 1: Encode the Odd-Position Choice

For each digit \(d\in\{0,1,\dots,9\}\), define \(k_d\) to be the number of copies of \(d\) placed in odd positions. Since each digit appears twice, we always have

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

There are 10 odd positions in total, so the first global constraint is

$\sum_{d=0}^{9} k_d = 10.$

Once the values \(k_0,\dots,k_9\) are fixed, the even positions are also fixed automatically: digit \(d\) appears

$2-k_d$

times in even positions.

Step 2: Translate Divisibility by 11 into a Digit-Sum Condition

Let

$W=\sum_{d=0}^{9} d\,k_d$

be the sum of the digits occupying odd positions. The sum of all digits \(0+1+\cdots+9\) is

$45,$

so the total sum of all 20 digits is

$2\cdot 45=90.$

Therefore the sum of digits in even positions is

$90-W.$

The divisibility rule for \(11\) requires

$W-(90-W)\equiv 0 \pmod{11}.$

Simplifying gives

$2W-90\equiv 0 \pmod{11},$

which is equivalent to

$W-45\equiv 0 \pmod{11}.$

So a vector \((k_0,\dots,k_9)\) is admissible precisely when

$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$

Step 3: Count the Odd-Position Arrangements

Fix an admissible vector \((k_0,\dots,k_9)\). If we momentarily ignore the leading-zero restriction, the odd positions contain a multiset with multiplicities \(k_0,\dots,k_9\), so the number of arrangements is the multinomial count

$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$

However, position 1 is an odd position, and the number may not start with \(0\). If \(k_0=0\), no correction is needed. If \(k_0\ge 1\), then the invalid arrangements with leading zero are obtained by fixing one zero in the first position and arranging the remaining 9 odd positions:

$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$

Hence the valid odd-position count is

$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$

where \(N_{\mathrm{odd,lead0}}=0\) when \(k_0=0\).

Step 4: Count the Even-Position Arrangements

The even positions contain the complementary multiset with multiplicities \(2-k_d\). There is no leading-digit restriction on even positions, so the count is simply

$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$

Once the odd and even arrangements are chosen independently, they interleave uniquely into one 20-digit number. Therefore the contribution of the fixed vector is

$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$

Step 5: Sum over All Feasible Vectors

Each \(k_d\) can only be \(0\), \(1\), or \(2\), so there are at most

$3^{10}=59{,}049$

possible vectors to inspect. The final answer is

$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$

This formula is exactly what the implementations evaluate.

Worked Example: Digits \(0,1,2\) Used Twice Each

A smaller version makes the counting transparent. Suppose we only use digits \(0,1,2\), each twice, so the number has 6 digits. Then there are 3 odd positions and 3 even positions, and we need

$k_0+k_1+k_2=3.$

The sum of the distinct digits is

$0+1+2=3,$

so the divisibility condition becomes

$k_1+2k_2-3\equiv 0 \pmod{11}.$

Because the left-hand side lies between \(-3\) and \(3\), it must actually be \(0\), hence

$k_1+2k_2=3.$

With \(k_d\in\{0,1,2\}\), the only solution is

$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$

So odd positions contain one copy each of \(0,1,2\), and even positions do as well. The counts are

$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$

$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$

$N_{\mathrm{odd,valid}}=6-2=4,$

$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$

Therefore this miniature problem has

$4\cdot 6=24$

valid numbers. The full problem is the same counting argument with digits \(0\) through \(9\).

How the Code Works

The C++, Python, and Java implementations precompute factorials from \(0!\) through \(20!\) so that every multinomial count can be formed by exact integer division. They then enumerate the ten values \(k_0,\dots,k_9\) with a depth-first search. During that search, the implementation keeps track of two running quantities: how many odd positions have already been filled and the current weighted odd-position sum \(\sum d\,k_d\).

When the search reaches digit \(9\), it first checks whether exactly 10 odd slots were used. If not, that branch is discarded immediately. It then checks the congruence

$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$

Only terminal states satisfying both conditions contribute. For each such state, the implementation computes the unrestricted odd multinomial, subtracts the leading-zero cases when necessary, computes the even multinomial from the complementary counts \(2-k_d\), and adds the product to the running total.

The search space is already tiny, but the recursion still prunes many branches early because any partial assignment that has already used more than 10 odd slots cannot lead to a valid completion.

Complexity Analysis

For the actual problem there are at most \(3^{10}=59{,}049\) vectors \((k_0,\dots,k_9)\). Each completed vector requires only \(O(10)\) arithmetic operations to evaluate the multinomial factors, so the overall running time is \(O(3^{10}\cdot 10)\), which is effectively constant for this fixed input size. The memory usage is \(O(10)\) for the current count vector and the small factorial table.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=491
2. Divisibility rule for 11: Wikipedia — Divisibility rule
3. Multinomial coefficient: Wikipedia — Multinomial theorem
4. Permutations of multisets: Wikipedia — Permutations of multisets