# Numbers with all N-digit prefixes divisible by N

In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. In base 10, 3816547290 is the only such number which meets the above criteria.

My question is, how can I find these numbers for any given base? I made a program to search for them up to base 30. Out of all the bases it tried, it only found numbers for bases 2, 4, 6, 8, 10, and 14. These numbers where as follows (I use digits 0-9 and A-D):

base 2 - 10
base 4 - 1230
base 4 - 3210
base 6 - 143250
base 6 - 543210
base 8 - 32541670
base 8 - 52347610
base 8 - 56743210
base 10 - 3816547290
base 14 - 9C3A5476B812D0


I do not know if any such numbers exist in bases larger than 14. Even if such numbers do exist, I don't know how to find them. Can anybody think of a general algorithm for finding such numbers or a general proof that they do not exist?

UPDATE: my code to find said numbers can be found on Github if anybody wants to look at it. Essentially, the program uses recursion to try all permutations of the digits. If it explores a set of digits which themselves do not meet the criterion, it can stop searching for permutations with that prefix (i.e. if it got to 382 in base 10, it would realize that that number is not divisible by 3 and would thus not search anymore numbers which start with 382).

• It feels like this problem is quite hard; digits mixed with divisibility properties is complicated; for example, I dont think it has been proved that there are infinitely many palindrome primes in, say, base 2... – Per Alexandersson Dec 14 '14 at 22:35
• Looking at the sum of the digits quickly shows the base needs to be even. – zeb Dec 14 '14 at 22:42
• ...so the digits have to alternate between odd and even. You can probably use this observation to speed up your search a bit. – zeb Dec 14 '14 at 22:55
• @DenisSerre I haven't checked your others, but look at your 13240 in base 5. 1324 (base 5) in base 10 is 214. The number 214 is not divisible by 4. Thus that is not a solution. – Alex Nichol Dec 15 '14 at 19:49
• My question is related: mathoverflow.net/questions/126911/… – Will Sawin Dec 17 '14 at 3:32

## 2 Answers

This seems to be a difficult question. https://oeis.org/A111456 is "Pandigitals in some base with an extra property: each number formed by the first $i$ digits is divisible by $i$ (digits in the pandigital base)." A comment there says, "Finite? There are no more terms up to base 40. A probabilistic argument says higher bases are increasingly unlikely to produce a value." https://oeis.org/A181736 tracks the same problem and a comment says it can't happen when the base is of the form $2m(2m-1)$ with $m>1$.

Edit. I think, contrary to Gerry, that the property is likely to happen, provided that $n$ is even. Obviously, the last digit must be the zero. Given an order $a_1\cdots a_{n-1}0$ of the digits, the constraints are that $\sum_1^ka_jn^j\equiv0\,(k)$. It is always satisfied for $k=1$. For $k=n-1$, it writes $$\begin{pmatrix} n-1 \\ 2 \end{pmatrix}\equiv0\quad(n-1),$$ whence the condition that $n$ be even. The probability that the order is OK is $\frac12/(n-2)!$, if the remaining constraints are independent. Therefore the number of good orders is, expectedly'', $$\frac12\cdot\frac{(n-1)!}{(n-2)!}=\frac{n-1}2.$$

• I like this heuristic, but it seems to miss some essential feature of the problem - the number of good orders for all the bases looked at is less than $n - 1$. – Michael Lugo Dec 15 '14 at 19:13
• If $n=2m$, then $a_m =m$, since the summands of $\sum^m_1a_jn^{(m-j)}$ are all multiples of $m$ except $a_m$. By the same reasoning, every even position must be an even digit, and hence odd positions are odd, so they are not independent. – Zack Wolske Dec 16 '14 at 16:46