7
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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!$.

$\endgroup$
1
  • $\begingroup$ Unfortunately your answer is not correct, e.g. ROT13 (gurer vf na boivbhf cbjreshy ahzore flfgrz (hanel). Gur vqrn bs hfvat rdhvinyrapr pynffrf vf irel tbbq, ohg sbe gur "ovwrp-" flfgrzf bar zhfg or pnershy, nf gur fgehpgher bognvarq vf abg gur vagrtref zbqhyb $B^n$! Gur vffhr vf gung abg nyy vagrtref ner rdhvinyrag vs $B^n$ qvivqrf gurve qvssrerapr; guvax nobhg jung unccraf jura bar bs gur vagrtref unf yrff guna $a$ qvtvgf. Gur vqrn bs hfvat Rhyre'f gurberz vf nyfb tbbq, gurer vf n ersvarzrag gung zvtug uryc.) $\endgroup$
    – pregunton
    Sep 3 at 8:57

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.