A finite sequence of decimal digits from $\{0,1,\cdots, 9\}$ is said to be common if for each sufficiently large positive integer $n$, there exists a positive integer $m$ such that the expansion of $n$ in base $m$ ends with this sequence of digits. For example, $0$ is common because for any large $n$, the expansion of $n$ in base $n$ is $10$, whereas $00$ is not common because for any squarefree $n$, the expansion of $n$ in any base cannot end with $00$. Determine all common sequences. Proposed by Wong Jer Ren
Problem
Source: Malaysian SST 2024 P2
Tags: number theory, Digits
06.09.2024 08:28
Might be fakesolve womp womp Note that $\sum_{i=2}^\infty \frac{1}{i^k} < \frac{1}{2}$ for $k \ge 3$. Let $\overline{a_k a_{k-1} \dots a_0}$ be a common sequence which is not all $0$. For each $i$, the number of $n \in [1, N]$ for which $n$ expands in base $i$ in that behavior is at most $\left\lceil \frac{n}{i^k} \right\rceil$. This means that asymptotically, we have that at most \[ \sum_{i=2}^n \frac{n}{i^k} + \sqrt{n} < n \]numbers are covered. This means that a common sequence has $k \le 2$. $k = 1$ works so let's consider common sequences $\overline{ab}$. If $a \ge 2$, then we have that \[ \frac{\pi^2}{6} - 1 - \frac{1}{4} + \frac{1}{2} < 1 \]so there is no solution. For $\overline{1r}$, taking $n-r$ suffices. Then it follows that the only common sequences are $0, 1, 2, \dots, 9$ and $10, 11, \dots, 19$.
06.09.2024 09:22
@Above, but for 1r, for any n>r you can simply take base n-r to get the representation 1r in that base
07.09.2024 19:12
The only such sequences are the numbers from $0$ to $19$. These are clearly achievable by taking $m=n-d$ where $d$ is the final digit of the sequence. Let $d$ be the final digit of the sequence. Let $n=p+d$ for a sufficiently large prime $p$. Then $m|n-d$ so we must have $m=p$. But then $n=1d_{m}$ leading to the above forms.