# unambiguity of factorial base representation

###### Theorem 1.

For all positive integers $n$, it is the case that

$$n!=1+\sum _{k=1}^{n-1}k\cdot k!$$ |

###### Proof.

We first consider two degenerate cases. When $n=0$ or $n=1$, the sum has no terms because the lower limit is bigger than the upper limit. By the convention that a sum with no terms equals zero, the equation reduces to $0!=1$ or $1!=1$, which is correct.

Next, assume that $n>1$. Note that

$$k\cdot k!=(k+1)k!-k!=(k+1)!-k!,$$ |

hence, we have a telescoping sum:

$$\sum _{k=1}^{n-1}k\cdot k!=\sum _{k=1}^{n-1}\left((k+1)!-k!\right)=n!-1$$ |

Adding 1, we conclude that

$$n!=1+\sum _{k=1}^{n-1}k\cdot k!$$ |

∎

###### Theorem 2.

If ${d}_{m}\mathit{}\mathrm{\dots}\mathit{}{d}_{\mathrm{2}}\mathit{}{d}_{\mathrm{1}}$ is the factoradic representation of a positive integer $n$, then $\mathrm{(}{d}_{m}\mathrm{+}\mathrm{1}\mathrm{)}\mathit{}m\mathrm{!}\mathrm{>}n\mathrm{\ge}{d}_{m}\mathrm{\cdot}m\mathrm{!}$

###### Proof.

By definition,

$$n={d}_{m}\cdot m!+\sum _{k=1}^{m-1}{d}_{k}\cdot k!.$$ |

Since each term of the sum is nonnegative, the sum is positive, hence $n\ge {d}_{m}\cdot m!$. Using the fact that $$ to bound each term in the sum, we have

$$n\le {d}_{m}\cdot m!+\sum _{k=1}^{m-1}k\cdot k!.$$ |

By theorem 1, the right-hand side equals $m!-1$, so we have $n\le {d}_{m}\cdot m!+m!-1$, which is the same as saying $({d}_{m}+1)m!>n$. ∎

###### Theorem 3.

If ${d}_{m}\mathit{}\mathrm{\dots}\mathit{}{d}_{\mathrm{2}}\mathit{}{d}_{\mathrm{1}}$ and $d^{\mathrm{\prime}}{}_{{m}^{\mathrm{\prime}}}\mathit{}\mathrm{\dots}\mathit{}d^{\mathrm{\prime}}{}_{\mathrm{2}}\mathit{}d^{\mathrm{\prime}}{}_{\mathrm{1}}$ are distinct factoradic representations with ${d}_{m}\mathrm{\ne}\mathrm{0}$ and $d^{\mathrm{\prime}}{}_{{m}^{\mathrm{\prime}}}\mathrm{\ne}\mathrm{0}$ (i.e. not padded with leading zeros), then they denote distinct integers.

###### Proof.

Let $n={\sum}_{k=1}^{m}{d}_{k}\cdot k!$ and let ${n}^{\prime}={\sum}_{k=1}^{{m}^{\prime}}d^{\prime}{}_{k}\cdot k!$.

Suppose that $m$ and ${m}^{\prime}$ are distinct. Without loss of generality, we may assume that $$. Then, $(m+1)!\le {m}^{\prime}!$. By theorem 2, we have $$ and ${d}_{{m}^{\prime}}\cdot {m}^{\prime}!\le {n}^{\prime}$. Because ${d}_{m}\le m$, we have $({d}_{m}+1)m!\le (m+1)m!=(m+1)!$. Because ${d}_{{m}^{\prime}}\ne 0$, we have ${n}^{\prime}>{m}^{\prime}!$. Hence, $$, so $n$ does not equal ${n}^{\prime}$.

To complete^{} the proof, we use the method of infinite descent. Assume
that factoradic representations are not unique. Then there must exist
a least integer $n$ such that $n$ has two distinct factoradic
representations ${d}_{m}\mathrm{\dots}{d}_{2}{d}_{1}$ and $d^{\prime}{}_{{m}^{\prime}}\mathrm{\dots}d^{\prime}{}_{2}d^{\prime}{}_{1}$
with ${d}_{m}\ne 0$ and $d^{\prime}{}_{{m}^{\prime}}\ne 0$. By the conclusion^{} of the
previous paragraph, we must have $m={m}^{\prime}$. By theorem 2, we must have
${d}_{m}=d^{\prime}{}_{m}$. Let ${m}_{1}$ be the chosen such
that ${d}_{{m}_{1}}\ne 0$ but ${d}_{{m}_{1}+1}=\mathrm{\cdots}={d}_{m-1}=0$ and let
${m}_{2}$ be the chosen such that $d^{\prime}{}_{{m}_{2}}\ne 0$ but $d^{\prime}{}_{{m}_{2}+1}=\mathrm{\cdots}=d^{\prime}{}_{m-1}=0$. Then ${d}_{{m}_{1}}\mathrm{\dots}{d}_{2}{d}_{1}$ and $d^{\prime}{}_{{m}_{2}}\mathrm{\dots}d^{\prime}{}_{2}d^{\prime}{}_{1}$ would be distinct factoradic representations of
$n-{d}_{m}\cdot m!$ whose leading digits are not zero but this would
contradict the assumption^{} that $n$ is the smallest number with this
property.
∎

Title | unambiguity of factorial base representation |
---|---|

Canonical name | UnambiguityOfFactorialBaseRepresentation |

Date of creation | 2013-03-22 16:38:35 |

Last modified on | 2013-03-22 16:38:35 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 14 |

Author | rspuzio (6075) |

Entry type | Definition |

Classification | msc 11A63 |

Related topic | UniquenessOfDigitalRepresentation |