Factorial numeral system

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]

\sum _{i=0}^{n}{i\cdot i!}=(n+1)!-1,\quad n\geq 0,\,

this provides a unique representation for each natural number, with the restriction (0 to $\scriptstyle i\,$ ) on the "digits" used with the place-value $\scriptstyle i!\,$ . 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 $\scriptstyle 0!\,$ , we may just omit it (unless considering Lehmer codes), i.e.

\sum _{i=1}^{n}{i\cdot i!}={(n+1)!}-1,\quad n\geq 0,\,

where for $\scriptstyle n\,=\,0\,$ 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 $k\cdot k!,\,k\geq 1$ , rows (zero-indexed from $k!$ to $(k+1)!-1$ ) with $k$ 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 $k=0$ .)

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 $\phi (120)=32$ 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 $\pi (120)=30$ primes up to 120 (as given by the prime counting function).

Note that starting from 10 * 10! = 36288000₁₀ = 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

n₁₀	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

n₁₀	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

n₁₀	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

n₁₀	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

n₁₀	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**
n₁₀	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 ${\tfrac {a}{b}}$ (considered in reduced form) in the open unit interval, i.e. $0<{\tfrac {a}{b}}<1$ , is defined as^[3]

{\frac {a}{b}}:=\sum _{i=1}^{N}{\frac {d_{i}}{(i+1)!}},\quad 0\leq d_{i}\leq i,\,

where $d_{i},\,0\leq d_{i}\leq i,$ is the "factoradic digit" for place-value ${\frac {1}{(i+1)!}}$ , and $N$ is the number of "factoradic digits" after the "factoradic point" ( $N$ is the smallest integer such that $(N+1)!$ is divisible by the denominator of ${\tfrac {a}{b}}$ , considered in reduced form).

Note that $d_{i}$ can't be equal to $i+1$ since

{\frac {i+1}{(i+1)!}}={\frac {1}{i!}}.\,

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 $x$ in the open unit interval, i.e. $0<x<1$ , is defined as

x:=\sum _{i=1}^{\infty }{\frac {d_{i}}{(i+1)!}},\quad 0\leq d_{i}\leq i,\,

where $d_{i},\,0\leq d_{i}\leq i,$ is the "factoradic digit" for place-value ${\frac {1}{(i+1)!}}$ .

Note that rational numbers have two factoradic representations, since it is easily proved that^[4]

{\frac {1}{m!}}=\sum _{i=m}^{\infty }{\frac {i}{(i+1)!}},\quad m\geq 1,\,

where on the left side we have the terminating form, while on the right we have the nonterminating form.

This is analogous to

{\frac {1}{b^{m}}}=\sum _{i=m}^{\infty }{\frac {b-1}{b^{i+1}}},\quad m\geq 0,\,b\geq 2,\,

in fixed radix base $b$ .

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

e=

1:0.1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:...

e^{-1}=

0.0:2:0:4:0:6:0:8:0:10:0:12:0:14:...

\sin(1)=

0.1:2:0:0:5:6:0:0:9:10:0:0:13:14:...

\cos(1)=

0.1:0:0:4:5:0:0:8:9:0:0:12:13:0:0:...

\sinh(1)=

1.0:1:0:1:0:1:0:1:0:1:0:1:0:1:0:1:...

\cosh(1)=

1.1:0:1:0:1:0:1:0:1:0:1:0:1:0:1:0:...

Notes

↑ Inductive proof:

Base case:

True for $n=0$ .

Induction step:

$\sum _{i=0}^{n}{i\cdot i!}=(n+1)!-1,\quad n\geq 0,\,$

if and only if

$\sum _{i=0}^{n-1}{i\cdot i!}+n\cdot n!=(n+1)\cdot n!-1=n\cdot n!+n!-1,\quad n\geq 0,\,$

if and only if

$\sum _{i=0}^{n-1}{i\cdot i!}=n!-1,\quad n\geq 0.\,$
↑ Keith Schwarz (htiek@cs.stanford.edu), File: FactoradicPermutation.hh.
↑ http://planetmath.org/factorialbaserepresentationoffractions
↑ Proof:
$\sum _{i=m}^{\infty }{\frac {i}{(i+1)!}}=\sum _{i=m+1}^{\infty }{\frac {i-1}{i!}}=\sum _{i=m+1}^{\infty }{\frac {1}{(i-1)!}}\,-\sum _{i=m+1}^{\infty }{\frac {1}{i!}}=\sum _{i=m}^{\infty }{\frac {1}{i!}}\,-\sum _{i=m+1}^{\infty }{\frac {1}{i!}}={\frac {1}{m!}},\quad m\geq 1.$

[1] Inductive proof:

Base case:

True for $n=0$ .

Induction step:

$\sum _{i=0}^{n}{i\cdot i!}=(n+1)!-1,\quad n\geq 0,\,$

if and only if

$\sum _{i=0}^{n-1}{i\cdot i!}+n\cdot n!=(n+1)\cdot n!-1=n\cdot n!+n!-1,\quad n\geq 0,\,$

if and only if

$\sum _{i=0}^{n-1}{i\cdot i!}=n!-1,\quad n\geq 0.\,$

[2] Keith Schwarz (htiek@cs.stanford.edu), File: FactoradicPermutation.hh.

[3] ttp://planetmath.org/factorialbaserepresentationoffractions

[4] Proof:
$\sum _{i=m}^{\infty }{\frac {i}{(i+1)!}}=\sum _{i=m+1}^{\infty }{\frac {i-1}{i!}}=\sum _{i=m+1}^{\infty }{\frac {1}{(i-1)!}}\,-\sum _{i=m+1}^{\infty }{\frac {1}{i!}}=\sum _{i=m}^{\infty }{\frac {1}{i!}}\,-\sum _{i=m+1}^{\infty }{\frac {1}{i!}}={\frac {1}{m!}},\quad m\geq 1.$

[1]

[2]

[3]

[4]

Factorial numeral system

Contents

Table of factoradics

Lehmer code of a permutation

Factoradic representation of rational numbers

Factoradic representation of real numbers

Examples of real numbers with a factoradic representation having a regular pattern

See also

Notes

Navigation menu

Views

Personal tools

Navigation

Search

Tools