Question

Describe an algorithm to add two integers from their Cantor expansions.

Short answer

$\begin{array}{r}\text{for}i:=10\text{to}n\\ \\ c_i:=a_i+b_i\\ \\ \text{for}j:=1\text{to}n-1\\ \\ \text{if}{c}_j>j\text{then}\\ \\ c_j:=c_j-(j+1)\\ \\ c_{j+1}:=c_{j+1}+1\\ \\ k:n\\ \\ \text{if}{c}_n>n\text{then}\\ \\ c_n:=c_n-(n+1)\\ \\ c_{n+1}:=1\\ \\ k:n+1\\ \\ \text{return}{c}_k\cdots \dots c_2{c}_1\end{array}$

Step-by-step solution

Step 1:

A cantor expansion is the sum $a_{n}n!+a_n-1(n-1)!+\dots +a_{2}2!+a_{1}1!\text{with}{a}_i$integers such that $0\le a_i\le i_{\text{for}}i=1,2,\dots .n$

Let us call algorithm “sum” and the input of the algorithm is the cantor expansions with n digits of two integers ( if one of the cantor expansions contains less digits then the other cantor expansions, then add leading 0)

we first add the corresponding digits $a_i\text{and}{b}_i$of each cantor expansion, while c, will represent the digits of the digits of the cantor expansion of the sum of the two integer

localid="1668523695048" $\begin{array}{r}\text{fori}:=10\text{ton}\\ \\ c_j:=a_i+b_i\end{array}$

Next we need to check if the condition $0\le c_i\le i$holds for $i=1,2\dots \dots n$

if the condition become true and each time $c_i$was decreased we add i to

$c_{i+1}(\mathrm{as}(i+1)i!=(i+1)!)$

$$\begin{gathered} \text{for}j:=1\text{to}n-1 \\ \text{if}{c}_j>j\text{then} \\ {c}_j:=c_j-(j+1) \\ {c}_{j+1}:=c_{j+1}+1k:=nif{c}_n>n\text{then} \\ {c}_n:=c_n-(n+1) \\ {c}_{n+1}:=1 \\ k:n+1 \end{gathered}$$

.

Finally we return the number $c_k\dots \dots c_2{c}_1$which is the cantor expansion of the sum of the two integers

return $c_k\dots \dots c_2{c}_1$

Step 2:

Minimum of two steps are required.