Imagine I’ve two nonnegative integers, $a$ and $b$. Can you discover the final digit of the sum $a+b$ given solely the final digits of $a$ and $b$? More typically, can you discover the final $n$ digits of $a+b$ given solely the final $n$ digits of $a$ and $b$? The reply to each questions is sure: for instance, any variety of the shape $…123$ added to any variety of the shape $…789$ all the time leads to plenty of the shape $…912$.

What in regards to the final $n$ digits of the product $atimes b$? There can also be a singular reply on this case: for instance, $(…47) occasions (…38) = …86$ all the time.

What in regards to the final $n$ digits of the ability $a^b$ (the place we take $0^0=1$)? Sadly, right here the entire thing breaks down: besides in very uncommon circumstances, the final digits of an influence can not basically be decided from the final digits of the bottom and exponent. For instance, $13^{14} = …9$, however $13^{24}=…1$, so $(…3)^{…4}$ isn’t uniquely decided. So our bizarre decimal notation behaves effectively with respect to sums and merchandise, however not with respect to exponentiation. That’s a disgrace! Could this “subject” maybe be fastened by altering our quantity system to one thing extra… highly effective?

Let $operatorname{final}_n a$ denote the quantity obtained by taking the final $n$ digits of the quantity $a$ (and $operatorname{final}_n a = a$ if $a$ has lower than $n$ digits). For instance, we have now $operatorname{final}_3 14835 = 835$, $operatorname{final}_4 57 = 57$ and $operatorname{final}_2 302 = 02 = 2$. We’ve seen that $operatorname{final}_n (a+b) = operatorname{final}_n(operatorname{final}_n a + operatorname{final}_n b)$ and $operatorname{final}_n (atimes b) = operatorname{final}_n(operatorname{final}_n a occasions operatorname{final}_n b)$ for all $a, b$ and all $n>0$. We’ll say {that a} quantity system is a highly effective quantity system if moreover we have now $$operatorname{final}_n (a^b) = operatorname{final}_n((operatorname{final}_n a)^{operatorname{final}_n b}).$$

Unfortunately, bizarre base-$B$ positional notation is not highly effective for any $B$ (are you able to see why?), so we’re compelled to show to extra unique methods:

• The bijective base-$B$ quantity methods are like bizarre base-$B$ numbers, however as a substitute of the digits going from $0$ to $B-1$, they go from $1$ to $B$ (and nil is represented by the empty string). The most well-known occasion is unary notation or bijective base-$1$, during which a quantity is represented by writing that many $1$s in succession. For instance, the checklist of numbers in bijective base-$10$ notation goes like $textual content{(empty)}, 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$ (the place the digit $mathrm A$ represents ten).

• The factorial quantity system is a system which isn’t tied to any base particularly; as a substitute, it’s such that the $okay$th digit is allowed to differ from $0$ to $k-1$ (so in idea this base wants infinitely many symbols, however solely a finite quantity is required to signify a given quantity). The checklist of optimistic numbers on this notation goes like $0, 10, 100, 110, 200, 210, 1000, 1010, 1100, 1110, 1200, 1210, 2000, 2010, 2100, 2110, 2200, 2210, 3000, 3010, ldots$. This quantity system is named as such as a result of the factorial $N! = N occasions (N-1) occasions cdots occasions 2 occasions 1$ of any quantity $N$ is definitely expressed on this notation as an $1$ adopted by $N$ zeros. For instance, $6!$ is expressed as $1000000$.

• Finally, we are able to mix the concepts of the bijective and factorial quantity methods by defining the bijectorial quantity system: a system such that the $okay$th digit is allowed to differ from $1$ to $okay$. The numbers on this notation go like $textual content{(empty)}, 1, 11, 21, 111, 121, 211, 221, 311, 321, 1111, ldots$

Can you discover all highly effective quantity methods among the many talked about ones (bijective base-$B$ for some $B$, factorial, bijectorial)?

Hint:

There are finitely many.