This site is supported by donations to The OEIS Foundation.
Factorial numeral system
Since we have (it is easily proved by [mathematical] induction)[1]
this provides a unique representation for each natural number, with the restriction (0 to ) on the "digits" used with the place-value . This gives the factorial numeral system, also called factoradic, a mixed radix numeral system adapted to numbering permutations in lexicographic order or in reverse lexicographic order (since a factoradic numeral maps to a permutation's Lehmer code).
Since 0 is the only "digit" allowed with the place-value , we may just omit it (unless considering Lehmer codes), i.e.
where for we get the empty sum, i.e. 0.
index: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0* |
radix: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0* |
place value: | 7! = 5040 | 6! = 720 | 5! = 120 | 4! = 24 | 3! = 6 | 2! = 2 | 1! = 1 | 0! = 1* |
digit: | 0 to 7 | 0 to 6 | 0 to 5 | 0 to 4 | 0 to 3 | 0 to 2 | 0 to 1 | 0 to 0* |
- * May be omitted (unless considering Lehmer codes) for convenience, since the only allowed "digit" is zero!
A007623 Integers written in factorial base (without its index 0 "digit", which is always 0). (Above 10*10! - 1, we need to use "digits" separators, e.g. colons.) (A124252 divided by 10.)
- {0, 1, 10, 11, 20, 21, 100, 101, 110, 111, 120, 121, 200, 201, 210, 211, 220, 221, 300, 301, 310, 311, 320, 321, 1000, 1001, 1010, 1011, 1020, 1021, 1100, 1101, 1110, 1111, ...}
The concatenation of
- {{0}, {1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}, {1, 2, 0}, {1, 2, 1}, {2, 0, 0}, {2, 0, 1}, {2, 1, 0}, {2, 1, 1}, {2, 2, 0}, {2, 2, 1}, ...}
where we have , rows (zero-indexed from to ) with elements gives the following sequence. (If we applied the rule of not displaying the leading 0 to zero, we would have nothing to show for it: there would be no row for .)
A108731 Triangle read by rows: row n gives digits of n in base factorial.
- {0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 2, 0, 1, 2, 1, 2, 0, 0, 2, 0, 1, 2, 1, 0, 2, 1, 1, 2, 2, 0, 2, 2, 1, 3, 0, 0, 3, 0, 1, 3, 1, 0, 3, 1, 1, ...}
A124252 Integers written in factorial base (with its index 0 "digit", which is always 0). (Above 10*10! - 1, we need to use "digits" separators, e.g. colons.) (10 times A007623.)
- {0, 10, 100, 110, 200, 210, 1000, 1010, 1100, 1110, 1200, 1210, 2000, 2010, 2100, 2110, 2200, 2210, 3000, 3010, 3100, 3110, 3200, 3210, 10000, 10010, 10100, 10110, 10200, ...}
Contents
Table of factoradics
In the following table, the primes, except for {2, 3}, all congruent to {1, 5} (mod 6), are shown in bold italic.
In factoradic representation, except for {1:0#, 1:1#}, all primes end with
- 0:1#, 2:1#
where the primes congruent to 1 (mod 6) end with 0:1#, while the primes congruent to 5 (mod 6) end with 2:1#.
Among the numbers coprime to 120 (as given by the totient function), 1 is a unit and the following four numbers
- 7^2 = 49, 7*11 = 77, 7*13 = 91, 7*17 = 119,
are composite, so we have 27 primes which are coprime to 120. If we count the primes {2, 3, 5} we get primes up to 120 (as given by the prime counting function).
Note that starting from 10 * 10! = 3628800010 = 10:0:0:0:0:0:0:0:0:0!, the need to use colon separators becomes obvious!
|
|
|
|
|
Lehmer code of a permutation
A factoradic numeral corresponds to a permutation's Lehmer code.[2]
For example, the factoradic numeral 3:1:1! (3:1:1:0! if we append the index 0 "digit", which is always 0) corresponds to the zero-indexed Lehmer code (3, 1, 1, 0) of the permutation (d, b, c, a) of (a, b, c, d), where
- d has zero-index 3 in (a, b, c, d),
- b has zero-index 1 in remaining (a, b, c),
- c has zero-index 1 in remaining (a, c),
- a has zero-index 0 in remaining (a), which is necessarily always 0,
and among the 4! = 24 permutations (in lexicographic order, zero-indexed from 0 to 23) of (a, b, c, d), the permutation (d, b, c, a) has zero-index 21.
n10 | n! | Lehmer_code | permutation |
---|---|---|---|
0 | 0 | (0, 0, 0, 0) | (a, b, c, d) |
1 | 1 | (0, 0, 1, 0) | (a, b, d, c) |
2 | 1:0 | (0, 1, 0, 0) | (a, c, b, d) |
3 | 1:1 | (0, 1, 1, 0) | (a, c, d, b) |
4 | 2:0 | (0, 2, 0, 0) | (a, d, b, c) |
5 | 2:1 | (0, 2, 1, 0) | (a, d, c, b) |
6 | 1:0:0 | (1, 0, 0, 0) | (b, a, c, d) |
7 | 1:0:1 | (1, 0, 1, 0) | (b, a, d, c) |
8 | 1:1:0 | (1, 1, 0, 0) | (b, c, a, d) |
9 | 1:1:1 | (1, 1, 1, 0) | (b, c, d, a) |
10 | 1:2:0 | (1, 2, 0, 0) | (b, d, a, c) |
11 | 1:2:1 | (1, 2, 1, 0) | (b, d, c, a) |
12 | 2:0:0 | (2, 0, 0, 0) | (c, a, b, d) |
13 | 2:0:1 | (2, 0, 1, 0) | (c, a, d, b) |
14 | 2:1:0 | (2, 1, 0, 0) | (c, b, a, d) |
15 | 2:1:1 | (2, 1, 1, 0) | (c, b, d, a) |
16 | 2:2:0 | (2, 2, 0, 0) | (c, d, a, b) |
17 | 2:2:1 | (2, 2, 1, 0) | (c, d, b, a) |
18 | 3:0:0 | (3, 0, 0, 0) | (d, a, b, c) |
19 | 3:0:1 | (3, 0, 1, 0) | (d, a, c, b) |
20 | 3:1:0 | (3, 1, 0, 0) | (d, b, a, c) |
21 | 3:1:1 | (3, 1, 1, 0) | (d, b, c, a) |
22 | 3:2:0 | (3, 2, 0, 0) | (d, c, a, b) |
23 | 3:2:1 | (3, 2, 1, 0) | (d, c, b, a) |
Factoradic representation of rational numbers
The factoradic representation of a rational number (considered in reduced form) in the open unit interval, i.e. , is defined as[3]
where is the "factoradic digit" for place-value , and is the number of "factoradic digits" after the "factoradic point" ( is the smallest integer such that is divisible by the denominator of , considered in reduced form).
Note that can't be equal to since
By using only the terminating form for rationals (see factoradic representation of real numbers for the non-terminating form), we get a unique factoradic representation for any rational number by adding the integer part to the fractional part (i.e. within the open unit interval).
|
|
|
|
Factoradic representation of real numbers
The factoradic representation of a real number in the open unit interval, i.e. , is defined as
where is the "factoradic digit" for place-value .
Note that rational numbers have two factoradic representations, since it is easily proved that[4]
where on the left side we have the terminating form, while on the right we have the nonterminating form.
This is analogous to
in fixed radix base .
By using only the terminating form for rationals, we get a unique factoradic representation for any real number by adding the integer part to the fractional part (i.e. within the open unit interval).
Examples of real numbers with a factoradic representation having a regular pattern
- 1:0.1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:...
- 0.0:2:0:4:0:6:0:8:0:10:0:12:0:14:...
- 0.1:2:0:0:5:6:0:0:9:10:0:0:13:14:...
- 0.1:0:0:4:5:0:0:8:9:0:0:12:13:0:0:...
- 1.0:1:0:1:0:1:0:1:0:1:0:1:0:1:0:1:...
- 1.1:0:1:0:1:0:1:0:1:0:1:0:1:0:1:0:...
See also
Notes
- ↑ Inductive proof:
Base case:
- True for .
Induction step:
if and only if
if and only if
- ↑ Keith Schwarz (htiek@cs.stanford.edu), File: FactoradicPermutation.hh.
- ↑ http://planetmath.org/factorialbaserepresentationoffractions
- ↑ Proof: