What is the complete set of 10-digit numbers using each value ($0$-$9$) once, such that the first $n$ digits form a number divisible by $n$ (for $n \in \{1,2,...,10\}$)?
E.g. if the number were $1234567890$, $1$ must be divisible by $1$, $12$ must be divisible by $2$, $123$ must be divisible by $3$, etc...
There's only one answer:
3816547290
If leading zeroes are excluded, then there are 2492 numbers that satisfy the successive divisibility condition. This C program finds them all in a few seconds:
#include <stdio.h>
int main(void)
{
long i,j,n,c=0;
for (i=1000000080; i<=9999999990; i+=90) {
for (n=i,j=10; j>1; n/=10,j--) if (n%j) break;
if (j==1) {
c++;
printf("%ld ",i);
}
}
printf("\nTotal: %ld\n",c);
return 0;
}
// Output: 1020005640 1020061620 1020068010 ... 9876062430 9876069630 9876545640
However, 3816547290 is the only one of these numbers that contains all the digits 0-9.
On a computer, this can be solved quite quickly by restricting the range of numbers that has to be searched.
We know that the last digit must be zero, so the only remaining option for the fifth digit is 5. All the digits in the other even positions must be either 2, 4, 6 or 8. And since there are four even positions to be filled, the numbers in the odd positions (apart from 5) must be 1, 3, 7 or 9 (because there are no even digits left to go around.)
Digit: 1 2 3 4 5 6 7 8 9 10
Value: 1/3/7/9 2/4/6/8 1/3/7/9 2/4/6/8 5 2/4/6/8 1/3/7/9 2/4/6/8 1/3/7/9 0
There are only 4^8 (=65536) numbers that fit this pattern. These can be tested in just a few milliseconds.
Let us write the number as $abcdefghij$.
$ab$, $abcd$, $abcdef$, $abcdefgh$, $abcdefghij$ are all even, therefore $\{b, d, f, h, j\}$ are the even digits and the remaining digits $\{a, c, e, g, i\}$ are the odd digits.
Let's write $k \mid N$ (read "k divides N") when $N$ is a multiple of $k$.
$10 \mid abcdefghij \implies j = 0$.
$5 \mid abcde \implies e$ is $0$ or $5$. But $0$ is taken, so $e = 5$.
$4 \mid abcd$ $\implies$ $4 \mid cd$. This with $c$ odd $\implies$ $d \in \{2,6\}$.
$8 \mid abcdefgh$ $\implies$ $4 \mid gh$. This with $g$ odd $\implies$ $h \in \{2,6\}$.
The last 2 lines imply $\{d,h\} = \{2,6\}$. In either order.
We know $\{b, d, f, h, j\}$ are the even digits. Since $j=0$ and $\{d,h\} = \{2,6\}$, the remaining digits are 4 and 8. $\{b,f\}=\{4,8\}$.
$3 \mid abc \implies 3 \mid abc000$. This with $6 \mid abcdef$ implies $3 \mid def$. But we already know $e=5$, $d \in \{2,6\}$ and $f \in \{4,8\}$. Only $def=258$ and $def=654$ satisfy these conditions. The choice of $d$ and $f$ also force the value of $b$ and $h$.
So far we have 2 partial solutions: $\_4\_258\_6\_0$ and $\_8\_654\_2\_0$.
$8 \mid abcdefgh$ $\implies$ $8 \mid fgh$. But $f$ is even, $8 \mid f00$, so we just need $8 \mid gh$. This with $g \in \{1,3,7,9\}$ leaves only $gh \in \{16,32,72,96\}$.
a) Let's consider $\_4\_258\_6\_0$. In that case we have $g \in \{1,9\}$.
$3 \mid abc$ with $b=4$ and $a,c \in \{1,3,7,9\}$ leaves only 2 possibilities: $abc \in \{147, 741\}$.
If $abcdef=147258$ with $7 \mid abcdefg$ then $g=3$. But this is not possible because $g \in \{1,9\}$.
If $abcdef=741258$ with $7 \mid abcdefg$ then $g=7$. This is not possible for the same reason.
So there is no solution for case (a).
b) Let's consider $\_8\_654\_2\_0$. In that case we have $g \in \{3,7\}$.
$3 \mid abc$ with $b=8$ and $a,c \in \{1,3,7,9\}$ gives 8 possibilities: $abc \in \{183,189,381,387,783,789,981,987\}$. Two of them, $387$ and $783$, are incompatible with $g \in \{3,7\}$. They can be removed. (Thanks to frodoskywalker.)
For the remaining 6 solutions you need to find $g$ that satisfies $7 \mid abcdefg$ and verify that $g \in \{3,7\}$.
For $abc=381$, we have $abcdef=381654$. $7 \mid abcdefg$ implies $g=7$ which is valid. You can complete it with $i=9$ and you get the solution: $abcdefghij=3816547290$.
No other $abc$ under consideration gives a valid $g$.
The only solution is 3816547290.
I'm obviously misunderstanding the question, because from what I can see, the number 2485701369 also satisfies the conditions, as does 2485701396, and others.
