Cantor Expansion

Question 1

What is a Cantor Expansion? (Definition)

Answer

The Cantor Expansion of a natural number $ n $ is a sum of the form $$ n = (k_m)m! + (k_{m-1})(m-1)! + \cdots + k_{2}2! + k_{1}1! $$ with integers $ k_i $ such as $ 0 \leq k_i \leq i $

Example: 12 = 2*3! + 0*2! + 0*1!

This is the explicit sum of the factor base of the number $ n $.

Question 2

How to calculate the Cantor expansion of a number?

Answer

Start by converting the number to a factorial basis (by performing successive divisions of $ n $ by $ i $ for the numbers from $ 1 $ to $ n $, as long as the quotient of the Euclidean division is non-zero) and add figures (in factorial basis) obtained by multiplying them by the corresponding factorial.

Example: In base 10, $ 123 $ can be decomposed as $ 1 \times 100 + 2 \times 10 + 3 \times 1 $

Example: In factorial base, $ 234_{10} = 14300_{!} = 1 \times 5! + 4 \times 4! + 3 \times 3! + 0 \times 2! + 0*1! $

Question 3

What is Cantor expansion algorithm?

Answer

To code the conversion of a decimal number into a factorial base, here is an algorithm function decimal2cantor(x) { n = 1 a = [] while (x != 0) { a[n] = x mod (n+1) x = (x-a[n])/(n+1) n++ } return a[n] }

Cantor's expansion can be deduced by a[n]*n! + a[n−1]*(n-1)! + ... + a[2]*2! + a[1]*1!

To code the conversion of a number written in factorial base into a decimal number, here is an algorithm:function cantor2decimal(a[n]) { x = 0 for i=n to 1 { x = x + a[i] x = i*x } return x }

Cantor Expansion