unambiguity of factorial base representation

Theorem 1.

For all positive integers n, it is the case that


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


hence, we have a telescoping sum:


Adding 1, we conclude that


Theorem 2.

If dmd2d1 is the factoradic representation of a positive integer n, then (dm+1)m!>ndmm!


By definition,


Since each term of the sum is nonnegative, the sum is positive, hence ndmm!. Using the fact that 0dk<k to bound each term in the sum, we have


By theorem 1, the right-hand side equals m!-1, so we have ndmm!+m!-1, which is the same as saying (dm+1)m!>n. ∎

Theorem 3.

If dmd2d1 and dmd2d1 are distinct factoradic representations with dm0 and dm0 (i.e. not padded with leading zeros), then they denote distinct integers.


Let n=k=1mdkk! and let n=k=1mdkk!.

Suppose that m and m are distinct. Without loss of generality, we may assume that m<m. Then, (m+1)!m!. By theorem 2, we have n<(dm+1)m! and dmm!n. Because dmm, we have (dm+1)m!(m+1)m!=(m+1)!. Because dm0, we have n>m!. Hence, n<n, so n does not equal n.

To completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 dmd2d1 and dmd2d1 with dm0 and dm0. By the conclusionMathworldPlanetmath of the previous paragraph, we must have m=m. By theorem 2, we must have dm=dm. Let m1 be the chosen such that dm10 but dm1+1==dm-1=0 and let m2 be the chosen such that dm20 but dm2+1==dm-1=0. Then dm1d2d1 and dm2d2d1 would be distinct factoradic representations of n-dmm! whose leading digits are not zero but this would contradict the assumptionPlanetmathPlanetmath 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