# Cantor representation of natural numbers

A while ago I encountered this theorem:

Cantor Representation: For any $n\in\mathbb{N}^*$, we can write $n$ uniquely as $\sum\limits_{i=1}^k c_i\cdot i!$, with $c_i$ a natural number such that $c_i\leq i$ for all $1\leq i\leq k$ and $c_k\neq 0$

After trying out some numbers and seeing that it works out, I believe it (not that I really had to, because considering it is named, it is not likely to be incorrect), however I don't really have much of an idea how I would go about proving it. I can't find much information about it on the internet, so I am asking your help. I think a good first step would be to consider an arbitrary number $n\in \mathbb{N}^*$ and for it find $k$ as stated in the theorem, but I'm not sure how I would do this.

By the way I am not sure if the tag I gave the question is correct.

Thank you

-

Note that for such a representation, we have $$\tag1 k!\le c_kk!\le \sum_{i=1}^k c_i i! \le \sum_{i=1}^k i\cdot i!<(k+1)!$$ where the last step follows by induction: It is true for $k=1$ and if $\sum_{i=1}^{k-1} i\cdot i!<k!$, then $$\sum_{i=1}^{k} i\cdot i!=k\cdot k!+\sum_{i=1}^{k-1} i\cdot i!<k\cdot k!+k!=(k+1)\cdot k!=(k+1)!.$$ Dividing by $k!$ gives $$\tag2 1\le c_k<k+1.$$ Given $n$, there is a smallest $k$ with $(k+1)!> n$ because factorial has monotonuous (for $k\ge 1$) and unbounded growth. Then $k!\le n <(k+1)k!$, i.e. we can write $n=c_k k!+r$ with $1\le c_k\le k$ and $0\le r<k!$ (by division mith remainder). If $r=0$, we are done. Otherwise we may assume that $r$ as a representation. By $(1)$ we see that the representation for $r$ can at most involve terms up to $i=k-1$, hence we can combine to a representation of $n$. So much for existance. We obtain uniqueness because $(1)$ shows that no other choice for $k$ is possible, $(2)$ show that no ozther choice for $c_k$ is possible and by induction, the representation for $r$ is unique.

-
Thanks, I think I see it now. –  user50407 Nov 25 '12 at 15:35

If we just consider the largest digit of a $k$ digit number $c_k \cdot k!$ this can express $k+1$ different multiples of $k!$: $0$, $k!$, $2 \cdot k!$, $\ldots$, $k \cdot k!$. (Much like how we can express 0, 1000, 2000, 3000, ..., 9000 in decimal)

So for this type of number system to be able to represent every number we need numbers with fewer digits than $k$ - ones of the form $\sum\limits_{i=1}^{k-1} c_i\cdot i!$ - to be able to express everything between the gaps (much like how every number below 10000 is some thousand + a number from 0 to 999). Specifically it needs to be able to express every number from $0$ up to $k!-1$.

Let us check that the biggest number we can express with $k$ digits

Lemma $$k! - 1 = \sum_{i=1}^{k-1} i \cdot i!.$$

Example

$$\begin{array}{} && (5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + 1 \cdot 1!) + 1 \\ &=& 5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + (1 \cdot 1! + 1 \cdot 1!) \\ &=& 5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + (2 \cdot 1!) \\ &=& 5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + (1 \cdot 2!) \\ &=& 5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 3 \cdot 2! \\ &=& 5 \cdot 5! + 4 \cdot 4! + 3 \cdot 3! + 1 \cdot 3! \\ &=& 5 \cdot 5! + 4 \cdot 4! + 4 \cdot 3! \\ &=& 5 \cdot 5! + 4 \cdot 4! + 1 \cdot 4! \\ &=& 5 \cdot 5! + 5 \cdot 4! \\ &=& 5 \cdot 5! + 1 \cdot 5! \\ &=& 6 \cdot 5! \\ &=& 6! \\ \end{array}$$

proof: Induction on $k$. We want to show $(k+1)! - 1 = \sum_{i=1}^{k} i \cdot i!$, using the inductive hypothesis we have $(k+1)! - 1 = k \cdot k! + k! - 1$ which clearly holds.

This lemma tells us that if we can express every number from $0$ to $k!-1$ in $k-1$ digits, we can also express every number from $0$ to $(k+1)!-1$ with $k$ digits.

Theorem Every natural number is uniquely expressed as a Cantor number.

proof: We will show that this is true for every number $n < (k+1)!$ for all $k$ by induction on $k$. The base case is trivial. For the inductive case we note there is a unique $c_k$ such that $n - c_k \cdot k!$ is positive and $< k!$ (by Lemma) therefore $n = c_k \cdot k! + \text{the representation given by induction}$.

We can apply this proof to find the Cantor representation of a specific number. For example for $38$ the first step is to find the smallest $(k+1)! > 38$, since $4! = 24$ and $5! = 120$ we choose $k=4$. Now $38-1\cdot 4! = 14$ gives the first digit, $14 - 2 \cdot 3! = 2$ gives the second, $2 = 2!$ gives the next and the last must be $0$, therefore 38 = [1,2,1,0] in Cantor representation.

-