mathematics - 10 digit number where first n digits are divisible by n

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...

Answer

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 


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.