Factorial Number System

I've titled this post Factorial Number System because I made a post titled Factorial Number Base on 31st March 2018. Strictly speaking, the factorials do not form a number base. This is explained in Wikipedia:

In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digits. By converting a number less than n! to factorial representation, one obtains a sequence of \(n\) digits that can be converted to a permutation of \(n\) in a straightforward way, either using them as Lehmer code or as inversion table representation; in the former case the resulting map from integers to permutations of \(n\) lists them in lexicographical order. General mixed radix systems were studied by Georg Cantor. The term "factorial number system" is used by Knuth, while the French equivalent "numération factorielle" was first used in 1888. The term "factoradic", which is a portmanteau of factorial and mixed radix, appears to be of more recent date.

My interest in the subject was rekindled when I came across this OEIS entry for 26085 (I turned 26085 days old today):

A286590: Numbers that are divisible by the product of their factorial base digits (A208575).

In my 2018 post, I treated this number system rather narrowly so I am broadening my scope in this current post. Figure 1 shows an easy way to convert from a decimal number to its factorial representation:

Figure 1: https://www.dcode.fr/factorial-base

Using this method, the following SageMath code will carry out the conversion (input is shown in blue and output in red):

# -------------------------------------------------------

# decimal to factorial base conversion with trailing zero

# -------------------------------------------------------

number=26085

entry=number

L,n,dividend=[],1,1

while dividend!=0:

    dividend=int(number/n)

    remainder=number%n

    L.append(remainder)

    number=dividend

    n+=1

L.reverse()

print(entry,"has factorial base of",L, "with trailing zero")

# ----------------------------------------------------------

# decimal to factorial base conversion without trailing zero

# ----------------------------------------------------------

number=26085

L,n,dividend=[],2,1

while dividend!=0:

    dividend=int(number/n)

    remainder=number%n

    L.append(remainder)

    number=dividend

    n+=1

L.reverse()

print(entry,"has factorial base of",L, "without trailing zero")  

 

26085 has factorial base of [5, 1, 1, 1, 3, 1, 1, 0] with trailing zero

26085 has factorial base of [5, 1, 1, 1, 3, 1, 1] without trailing zero

Here is the permalink to SageMathCell. Notice the two possible representations: \(51113110_!\) and   \(5111311_!\). This is because "The factorial number system is sometimes defined with the 0! place omitted because it is always zero" (Wikipedia). The conversion from factorial representation to decimal is quite straightforward. Here is the SageMath code (permalink):

# ---------------------------------------------------------

# factorial base (with trailing zero) to decimal conversion 

# ---------------------------------------------------------

number=51113110

D=number.digits()

decimal,n=0,0

for d in D:

    decimal+=d*factorial(n)

    n+=1

print(decimal)

# ------------------------------------------------------------

# factorial base (without trailing zero) to decimal conversion 

# ------------------------------------------------------------

number=5111311

D=number.digits()

decimal,n=0,1

for d in D:

    decimal+=d*factorial(n)

    n+=1

print(decimal)

26085

26085

Wikipedia goes on to say:

The factorial number system provides a unique representation for each natural number, with the given restriction on the "digits" used. No number can be represented in more than one way because the sum of consecutive factorials multiplied by their index is always the next factorial minus one:$$\sum_{i=0}^n i \times i!=(n+1)!-1$$

This can be easily proved with mathematical induction, or simply by noticing that :$$\forall i,i \times i!=(i+1-1) \times i!=(i+1)!-i!$$where subsequent terms cancel each other, leaving the first and last term (see Telescoping series).

However, when using Arabic numerals to write the digits (and not including the subscripts as in the above examples), their simple concatenation becomes ambiguous for numbers having a "digit" greater than 9. The smallest such example is the number 10 × 10! = 36,288,00010, which may be written A0000000000!=10:0:0:0:0:0:0:0:0:0:0!, but not 100000000000! = 1:0:0:0:0:0:0:0:0:0:0:0! which denotes 11! = 39,916,80010. Thus using letters A–Z to denote digits 10, 11, 12, ..., 35 as in other base-N make the largest representable number 36 × 36! − 1. 

For arbitrarily greater numbers one has to choose a base for representing individual digits, say decimal, and provide a separating mark between them (for instance by subscripting each digit by its base, also given in decimal, like 24031201, this number also can be written as 2:0:1:0!). In fact the factorial number system itself is not truly a numeral system in the sense of providing a representation for all natural numbers using only a finite alphabet of symbols, as it requires an additional separation mark.

There's a lot more that could be said about this topic and I may add to it in the future. In conclusion, DCODE provides a quick conversion tool from decimal to factorial base and back again. It's an interesting site that I've used before but had forgotten about. It's a site well worth exploring.