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?

  • $\begingroup$ it's called that because there are two systems that were once both in use: youtube.com/watch?v=C-52AI_ojyQ $\endgroup$ – user451844 Oct 8 '17 at 20:54
  • $\begingroup$ "... 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\}$"? $\endgroup$ – Blue Oct 8 '17 at 21:41
  • $\begingroup$ 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. $\endgroup$ – Blue Oct 8 '17 at 22:27
  • $\begingroup$ 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.) $\endgroup$ – Blue Oct 8 '17 at 23:19

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

  • $\begingroup$ 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". :) $\endgroup$ – Blue Oct 8 '17 at 23:06
  • $\begingroup$ That solution $3816547290$ is fairly "well-known". See e.g. Wikipedia. $\endgroup$ – Robert Israel Oct 9 '17 at 3:53
  • $\begingroup$ I guess now it's even weller-known. ;) $\endgroup$ – Blue Oct 9 '17 at 3:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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