# “American Billions” puzzle: Find a 10-digit number (no repeats), where the first $n$ digits give a number divisible by $n$, for all $n = 1,\ldots,9$

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?

• it's called that because there are two systems that were once both in use: youtube.com/watch?v=C-52AI_ojyQ – user451844 Oct 8 '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 8 '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 8 '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 8 '17 at 23:19

By brutish force, I find four solutions: $$3816547209, 3816547290, 7832041659, 8016547239$$
• 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 8 '17 at 23:06
• That solution $3816547290$ is fairly "well-known". See e.g. Wikipedia. – Robert Israel Oct 9 '17 at 3:53
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.