1

I have no idea why the problem is apparently called this but here it is.

Using only the digits $0$, $1$, $2$, $\ldots$, $9$, find a ten-digit number such that the number up to the $n$-th digit is divisible by $n$, for all $n\in\{1,\ldots,9\}$.

In other words, the first digit is divisible by $1$ (easy); the number made from just the first two digits is divisible by $2$ (again, easy - just make the second number even); and so on. Since there are ten digits and only nine are needed to satisfy the divisibility rule, there should be one left over at the end.

The closest I have gotten so far is the number $309258641$. $$\begin{align} 3 &= 1 \times 3 \\ 30 &= 2 \times 15 \\ 309 &= 3 \times 103 \\ 3092 &= 4 \times 773 \\ 30925 &= 5 \times 6185 \\ 309258 &= 6 \times 51543 \\ 3092586 &= 7 \times 441798 \\ 30925864 &= 8 \times 3865733 \\ 309258641 &= \color{red}{\text{not divisible by $9$}} \\ 309258647 &= \color{red}{\text{not divisible by $9$}} \end{align}$$

However, this was obtained by trial and error (following some simple rules like the second digit must be even, and the first, second and third digits must add to a multiple of $3$, etc.).

My question is:

Does anyone know of a systematic way of finding the answer, or showing that there isn't one?

Blue
  • 75,673
user458984
  • 325
  • it's called that because there are two systems that were once both in use: https://www.youtube.com/watch?v=C-52AI_ojyQ –  Oct 08 '17 at 20:54
  • "... divisible by $n$ for all $n \in {0,\ldots,9}$". Divisibility by zero is a tricky condition. :) Do you mean "... divisible by $n$ for all $n \in {1,\ldots,9}$"? – Blue Oct 08 '17 at 21:41
  • If the last digit were $0$, then there would be no need to allow the last digit to fail the divisible-by-$n$ rule. So, the last digit is probably not $0$ (unless the rules are being intentionally tricky). Now, the $9$-digit number being divisible by $9$ implies, by a well-known rule, that the sum of the digits is divisible by $9$; since $0$ is (probably) one of those digits, then $9$ cannot be one of the other eight. (Why?) Consequently: The number's final digit must be $9$. (Probably.) Beyond that, I don't have a useful observation. – Blue Oct 08 '17 at 22:27
  • Robert's answer includes a solution with a trailing $0$, so the divisibility rule is rather unnecessarily restricted to $n=9$. Go figure. (So, the "probably"s in my above comment were warranted.) – Blue Oct 08 '17 at 23:19

2 Answers2

4

By brutish force, I find four solutions: $$3816547209, 3816547290, 7832041659, 8016547239$$

Robert Israel
  • 448,999
  • Interestingly, you have a solution with a trailing $0$, so the divisibility rule holds for $n=10$, as well. I trust that your analysis is comprehensive, so that divisibility through $n=10$ makes the solution unique. I have to wonder why the divisibility rule only requires up to $n=9$. (I'm glad my comment to the question keeps repeating the disclaimer "probably". :) – Blue Oct 08 '17 at 23:06
  • That solution $3816547290$ is fairly "well-known". See e.g. Wikipedia. – Robert Israel Oct 09 '17 at 03:53
  • I guess now it's even weller-known. ;) – Blue Oct 09 '17 at 03:56
1

If you want a ten digit solution, $0$ must be the tenth digit and $5$ must be the fifth. The other evens have to go in the even places. Each block of three digits must be divisible by $3$. That means that either each block of three has all three digits the same $\bmod 3$ or has a $0$, a $1$, and a $2$. The fourth and eighth place must be $2$ and $6$ (in either order) because they are preceded by an odd digit and the number to that point needs to be divisible by $4$. The second and sixth places are then $4$ and $8$ (in either order). This reduces the number of possibilities considerably, but there is still a bunch of trial and error.

Ross Millikan
  • 374,822