This site is supported by donations to The OEIS Foundation.

Factorial numeral system

From OeisWiki
(Redirected from Factoradic)
Jump to: navigation, search


This article page is a stub, please help by expanding it.



This article needs more work.

Please help by expanding it!


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.

Factorial numeral system (successive positive integers as radix, whose place values are factorial numbers)
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, ...}

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!

Factoradic representation (index 0 omitted) of nonnegative integers from 0 to 5! − 1


n10 n!
0 0
1 1
2 1:0
3 1:1
4 2:0
5 2:1
6 1:0:0
7 1:0:1
8 1:1:0
9 1:1:1
10 1:2:0
11 1:2:1
12 2:0:0
13 2:0:1
14 2:1:0
15 2:1:1
16 2:2:0
17 2:2:1
18 3:0:0
19 3:0:1
20 3:1:0
21 3:1:1
22 3:2:0
23 3:2:1


n10 n!
24 1:0:0:0
25 1:0:0:1
26 1:0:1:0
27 1:0:1:1
28 1:0:2:0
29 1:0:2:1
30 1:1:0:0
31 1:1:0:1
32 1:1:1:0
33 1:1:1:1
34 1:1:2:0
35 1:1:2:1
36 1:2:0:0
37 1:2:0:1
38 1:2:1:0
39 1:2:1:1
40 1:2:2:0
41 1:2:2:1
42 1:3:0:0
43 1:3:0:1
44 1:3:1:0
45 1:3:1:1
46 1:3:2:0
47 1:3:2:1


n10 n!
48 2:0:0:0
49 2:0:0:1
50 2:0:1:0
51 2:0:1:1
52 2:0:2:0
53 2:0:2:1
54 2:1:0:0
55 2:1:0:1
56 2:1:1:0
57 2:1:1:1
58 2:1:2:0
59 2:1:2:1
60 2:2:0:0
61 2:2:0:1
62 2:2:1:0
63 2:2:1:1
64 2:2:2:0
65 2:2:2:1
66 2:3:0:0
67 2:3:0:1
68 2:3:1:0
69 2:3:1:1
70 2:3:2:0
71 2:3:2:1


n10 n!
72 3:0:0:0
73 3:0:0:1
74 3:0:1:0
75 3:0:1:1
76 3:0:2:0
77 3:0:2:1
78 3:1:0:0
79 3:1:0:1
80 3:1:1:0
81 3:1:1:1
82 3:1:2:0
83 3:1:2:1
84 3:2:0:0
85 3:2:0:1
86 3:2:1:0
87 3:2:1:1
88 3:2:2:0
89 3:2:2:1
90 3:3:0:0
91 3:3:0:1
92 3:3:1:0
93 3:3:1:1
94 3:3:2:0
95 3:3:2:1


n10 n!
96 4:0:0:0
97 4:0:0:1
98 4:0:1:0
99 4:0:1:1
100 4:0:2:0
101 4:0:2:1
102 4:1:0:0
103 4:1:0:1
104 4:1:1:0
105 4:1:1:1
106 4:1:2:0
107 4:1:2:1
108 4:2:0:0
109 4:2:0:1
110 4:2:1:0
111 4:2:1:1
112 4:2:2:0
113 4:2:2:1
114 4:3:0:0
115 4:3:0:1
116 4:3:1:0
117 4:3:1:1
118 4:3:2:0
119 4:3:2:1

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.


Permutations of (a, b, c, d) in lexicographic order
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 fractions in the open unit interval with denominator up to 12


Fraction Factoradic
1/2 0.1
1/3 0.0:2
2/3 0.1:1


Fraction Factoradic
1/4 0.0:1:2
3/4 0.1:1:2
1/5 0.0:1:0:4
2/5 0.0:2:1:3
3/5 0.1:0:2:2
4/5 0.1:1:3:1
1/6 0.0:1
5/6 0.1:2
1/7 0.0:0:3:2:0:6
2/7 0.0:1:2:4:1:5
3/7 0.0:2:2:1:2:4
4/7 0.1:0:1:3:3:3
5/7 0.1:1:1:0:4:2
6/7 0.1:2:0:2:5:1


Fraction Factoradic
1/8 0.0:0:3
3/8 0.0:2:1
5/8 0.1:0:3
7/8 0.1:2:1
1/9 0.0:0:2:3:2
2/9 0.0:1:1:1:4
4/9 0.0:2:2:3:2
5/9 0.1:0:1:1:4
7/9 0.1:1:2:3:2
8/9 0.1:2:1:1:4
1/10 0.0:0:2:2
3/10 0.0:1:3:1
7/10 0.1:1:0:4
9/10 0.1:2:1:3


Fraction Factoradic
1/11 0.0:0:2:0:5:3:1:4:0:10
2/11 0.0:1:0:1:4:6:2:8:1:9
3/11 0.0:1:2:2:4:2:4:3:2:8
4/11 0.0:2:0:3:3:5:5:7:3:7
5/11 0.0:2:2:4:3:1:7:2:4:6
6/11 0.1:0:1:0:2:5:0:6:5:5
7/11 0.1:0:3:1:2:1:2:1:6:4
8/11 0.1:1:1:2:1:4:3:5:7:3
9/11 0.1:1:3:3:1:0:5:0:8:2
10/11 0.1:2:1:4:0:3:6:4:9:1
1/12 0.0:0:2
5/12 0.0:2:2
7/12 0.1:0:2
11/12 0.1:2:2

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

  1. Inductive proof:

    Base case:

    True for .

    Induction step:

    if and only if

    if and only if

  2. Keith Schwarz (htiek@cs.stanford.edu), File: FactoradicPermutation.hh.
  3. http://planetmath.org/factorialbaserepresentationoffractions
  4. Proof: