Powerful number systems

Question

Imagine I have two positive integers, $a$ and $b$. Can you find the last digit of the sum $a+b$ given only the last digits of $a$ and $b$? More generally, can you find the last $n$ digits of $a+b$ given only the last $n$ digits of $a$ and $b$? The answer to both questions is yes: for example, any number of the form $...123$ added to any number of the form $...789$ always results in a number of the form $...912$.

What about the last $n$ digits of the product $a\times b$? There is also a unique answer in this case: for example, $(...47) \times (...38) = ...86$ always.

What about the last $n$ digits of the power $a^b$? Sadly, here the whole thing breaks down: except in very rare cases, the last digits of a power cannot in general be determined from the last digits of the base and exponent. For example, $13^{14} = ...9$, but $13^{24}=...1$, so $(...3)^{...4}$ is not uniquely determined. So our ordinary decimal notation behaves well with respect to sums and products, but not with respect to exponentiation. That's a shame! Could this "issue" perhaps be fixed by changing our number system to something more... powerful?

---

Let $\operatorname{last}_n a$ denote the number obtained by taking the last $n$ digits of the number $a$ (and $\operatorname{last}_n a = a$ if $a$ has less than $n$ digits). For example, we have $\operatorname{last}_3 14835 = 835$, $\operatorname{last}_4 57 = 57$ and $\operatorname{last}_2 302 = 02 = 2$. We've seen that $\operatorname{last}_n (a+b) = \operatorname{last}_n(\operatorname{last}_n a + \operatorname{last}_n b)$ and $\operatorname{last}_n (a\times b) = \operatorname{last}_n(\operatorname{last}_n a \times \operatorname{last}_n b)$ for all $a, b$ and all $n>0$. We'll say that a number system is a powerful number system if additionally we have $$\operatorname{last}_n (a^b) = \operatorname{last}_n((\operatorname{last}_n a)^{\operatorname{last}_n b}).$$

Unfortunately, ordinary base-$B$ positional notation isn't powerful for any $B$ (consider $(...10)^{...01}$), so we're forced to turn to more exotic systems:

• The bijective base-$B$ number systems are like ordinary base-$B$ numbers, but instead of the digits going from $0$ to $B-1$, they go from $1$ to $B$. The most famous instance is unary notation or bijective base-$1$, in which a number is represented by writing that many $1$s in succession. For example, the list of positive numbers in bijective base-$10$ notation goes like $1, 2, 3, 4, 5, 6, 7, 8, 9, \mathrm A, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1{\mathrm A}, 21, \ldots$ (where the digit $\mathrm A$ represents ten).

• The factorial number system is a system which is not tied to any base in particular; instead, it is such that the $k$th digit is allowed to vary from $0$ to $k-1$ (so in theory this base needs infinitely many symbols, but only a finite amount is needed to represent a given number). The list of positive numbers in this notation goes like $10, 100, 110, 200, 210, 1000, 1010, 1100, 1110, 1200, 1210, 2000, 2010, 2100, 2110, 2200, 2210, 3000, 3010, \ldots$. This number system is called as such because the factorial $N! = N \times (N-1) \times \cdots \times 2 \times 1$ of any number $N$ is easily expressed in this notation as an $1$ followed by $N$ zeros. For example, $6!$ is expressed as $1000000$.

• Finally, we can combine the ideas of the bijective and factorial number systems by defining the bijectorial number system: a system such that the $k$th digit is allowed to vary from $1$ to $k$. The numbers in this notation go like $1, 11, 21, 111, 121, 211, 221, 311, 321, 1111, \ldots$

Can you find all powerful number systems among the mentioned ones (bijective base-$B$ for some $B$, factorial, bijectorial)?

---

Hint:

There are finitely many.

Hint 2:

Focus on the last digit only. Look at small bases like unary, bijective base-$2$, bijective base-$3$, etc. (you can use a computer if you want). See if you can find some pattern in the cases that work, and what's the problem in the cases that don't.

Hint 3:

Try to express the patterns you found in terms of modular arithmetic. As with anything involving modulos and powers, you will need this, or some strengthened version of it.

Answer 1

None of these systems are powerful. The factorial and bijectorial systems are powerful for some $n$, but not all $n$.

Ordinary and Bijective base-$B$

The last$_n$ operation defines an equivalence on the positive integers - two integers are equivalent if they have the same last $n$ digits. For both ordinary and bijective base-$B$ systems, two integers are equivalent if $10^n$ divides their difference. This means we can replace last$_n$ in these two systems with $\bmod 10^n$, and use the same counterexample from the ordinary system for the bijective system. That is $3^{14} \bmod 10 \neq 3^{14 \bmod 10} \bmod 10$.

Factorial and Bijectorial

For the factorial (resp. bijectorial) number system, two integers are equivalent if $n!$ (resp. $(n-1)!$) divides their difference. In order to find a counterexample, we use Euler's totient theorem: $$x^y \bmod k \equiv (x \bmod k)^{y \bmod \phi(k)}.$$That is, the power depends on the exponent $\bmod \phi(k)$, not $\bmod k$, so we look for $n$ where $\phi(n!)$ does not divide $n!$. The smallest example is at $5$, using $b=121=5!+1!=(100010)_{FNS}$ which gives last$_5(121)=(00010)_{FNS}=1$, and $\phi(120)=32$ $$last_5(2^{121})=2^{121} \bmod 120 \equiv 2^{25} \bmod 120 \equiv 32=(11100)_{FNS}.$$ We also notice that the factorial (resp., bijectorial) system is powerful for up to $4$ (resp., $5$) digits, because $\phi(24)=8$, $\phi(6)=2$, but never again, since the exponent of $2$ in $\phi(n!)$ is always larger than the exponent in $n!$.