14
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Sounds more like a math problem (number theory) to me. Maybe you can ask it there $\endgroup$ – Mathias711 Oct 18 '14 at 20:11
  • 1
    $\begingroup$ Well there's 9999999999 $\endgroup$ – warspyking Oct 18 '14 at 20:51
  • $\begingroup$ I ran a script on my iPod and there were so many numbers that it couldn't fit on the screen. $\endgroup$ – warspyking Oct 18 '14 at 21:49
  • 3
    $\begingroup$ @warspyking, 9999999999 fails both the using each value (0-9) once and the first n digits must be divisible by n requirements. For example, 99 is not divisible by 2. $\endgroup$ – frodoskywalker Oct 18 '14 at 22:27
  • $\begingroup$ Oh, I misunderstood the question. $\endgroup$ – warspyking Oct 19 '14 at 2:20
20
$\begingroup$

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.

$\endgroup$
27
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I believe your condition on 8 must be 8|gh with g odd (instead of 4 divides, should be eight divides). This as while for example 12 would satisfy the 4 divides requirement, it is insufficient. $\endgroup$ – Pieter Geerkens Oct 19 '14 at 3:25
  • 1
    $\begingroup$ When you have 8 solutions for abc, 2 of them (387, 783) are ruled out by $g\le \{3,7\}$ $\endgroup$ – frodoskywalker Oct 19 '14 at 6:56
  • 1
    $\begingroup$ @PieterGeerkens at that point I only want to show that h is in {2,6}. The stricter condition for 8 is used later. $\endgroup$ – Florian F Oct 19 '14 at 15:35
  • $\begingroup$ @frodoskywalker: you are right, nice shortcut. $\endgroup$ – Florian F Oct 19 '14 at 15:45
  • $\begingroup$ Thanks to John Cena who spotted a typo with case b=8 after 8 months! $\endgroup$ – Florian F Jun 26 '16 at 11:34
-1
$\begingroup$

I'm obviously misunderstanding the question, because from what I can see, the number 2485701369 also satisfies the conditions, as does 2485701396, and others.

$\endgroup$
  • 2
    $\begingroup$ Welcome to Puzzling! (Take the Tour!) Could you please explain why you believe this is the answer? The question says the first digit must be evenly divisible by 1, first two by 2, first three by 3, .... In your examples, the first three digits form the number $248$ which is not evenly divisible by $3$, so neither is a valid answer to the question. $\endgroup$ – Rubio Aug 3 '17 at 2:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.