Editing 2835: Factorial Numbers

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 10: Line 10:
  
 
==Explanation==
 
==Explanation==
−
A {{w|factorial}} is a product of positive integers. For instance, four factorial, written '4!', means 4×3×2×1=24.  
+
{{incomplete|There is no explanation of the comic. There is a complex dive into the mathematics with no simplified explanation created to help understand the comic or its joke. Do NOT delete this tag too soon.}}
  
−
The "base" of a numbering system defines which numbers it uses as digits and what each place value in a number means.  For example, in decimal numbers (base 10), the digits go from 0 to 9, and place values are ones, tens, hundreds, etc.  So "137" means 1×100 + 3×10 + 7×1 = 137.  Numbers can also be written in other bases, such as binary (base 2, using the digits 0 and 1 and place values of 1, 2, 4, 8...) or octal  (base 8, using the digits 0-7 and place values of 1, 8, 64, and so on).  Using different bases is uncommon, but is sometimes useful in computer science.
+
This comic is based on the {{w|factorial number system}}, which is a way of writing integers or real numbers using {{w|factorial|factorials}} instead of powers.  
  
−
In the comic, [[Cueball]] proposes a {{w|factorial number system}}, where the base ''changes'' for each place value - the first digit can be 0 or 1, the next digit can be 0, 1, or 2, the third can be 0, 1, 2, or 3, and so on. Each place value is the factorial of the base.  So the number 137 in base 10 could be written as 10221, meaning 1×5! + 0×4! + 2×3! + 2×2! + 1×1!.  While this numbering system is technically usable and can express any number, it seems excessively complicated, and the only reason Cueball gives for using it is that he thinks large digits like 9 should only be used in vast numbers (9 would not be used unless the number was at least 9 digits long, or over 3.2 million in decimal). This is a silly reason for using a new numbering system,{{cn}} so the math department thinks this is a prank, and has security throw him out.
+
[[Cueball]] proposes this number system with his key point being that small value numbers are described only with the small value digits (1, 2, or 3) and saving the larger digits (8 and 9) for larger value numbers. His proposed solution is a complicated number system that some (probably including at least one person able to summon security personnel) might consider unnecessarily clunky to be actually useful.<!-- This is not to say that it will *not* have any practical use, of course! Leaving that as an exercise for future editors to ponder. ;) -->
  
−
In the title text, someone points out that a factorial number system needs more and more digits for each place value. The tenth digit in a factorial number would be in base 11, which needs 11 possible digits, and 0-9 only provides 10. In bases higher than 10, you can use letters to represent higher digits.  For example, hexadecimal (base 16) goes from 0 to 9, then from A to F.  It would be reasonable to do the same thing for higher bases in factorial numbers.  Instead, Cueball says that it's simply illegal to write numbers larger than about 3.6 million, the largest you can go without using a base greater than 10. This is an absurd limitation, as other numbering systems can go as high as you like.
+
A factorial is a product of positive integers. For instance, four factorial, written '4!', means 4×3×2×1 = 24. These can be used to write numbers in a strange way.
  
−
The number at the top of Cueball's presentation, 353011, is 3×6! + 5×5! + 3×4! + 0×3! + 1×2! + 1×1! which gives the decimal value of 2835, the number of the comic.
+
Normally, numbers are represented in a positional system with a constant base, especially base ten. This means that each digit in a number has a place value based on its position, and that value is a power of ten. For instance, the number 137 usually means 1×10<sup>2</sup> + 3×10<sup>1</sup> + 7×10<sup>0</sup>, i.e. one hundred, three tens, and seven units. We say that the 1 is in the hundreds place, the 3 in the tens place, and the 7 in the ones place (or units). The same number could be written in base sixteen as 89, meaning 8×16<sup>1</sup> + 9×16<sup>0</sup>, i.e. eight sixteens and nine units. The 8 is in the sixteens place, and the 9 is in the ones place.  
  
−
Cueball's examples of numbers written in factored appear as sequences [https://oeis.org/A007623 A007623] in the OEIS.
+
In a "factorial base," instead of each place value being an escalating power of some constant base, each place value is an escalating factorial. The amount to multiply each place value by to get the next place value increases by 1 each time. So that same number (137 in base 10) could be written 10221, meaning 1×5! + 0×4! + 2×3! + 2×2! + 1×1!. We could say there is a 1 in the 120s place, a 0 in the 24s place, a 2 in the 6s place, another 2 in the 2s place, and a 1 in the ones place.
 +
 
 +
True factorial numbers also include a 0s place, representing the 0 factorial of 0! Continuing our example of 137 in base 10, the values 1×5! + 0×4! + 2×3! + 2×2! + 1×1! + 0x0! would write out to 102210, but [[Randall]]'s version truncates this rightmost 0 factorial since it is always a value of 0.
 +
 
 +
In normal base-n notation, n digits are used, running from 0 to n–1. For instance, in base ten, we use the ten digits {0,...,9}. In base sixteen, we need sixteen digits, so we use {0,...,9,A,...,F}. Any of these digits can be used in any position. But in factorial base, each position needs an increasing number of different digits to express all n-digit numbers. The comic labels each position with the equivalent base that would allow the same digits, e.g. the place value 3! is "base 4" because it uses the digits 0 to 3.
 +
 
 +
For instance, with just two digits, we can express some numbers with the digits 0, 1, and 2, like 21 = five. But we can't express 30 = six. As a result, Randall jokes that since we only have ten digits {0,...,9}, we can only express numbers with up to nine digits, making larger numbers "illegal." Randall believes that would make the largest "legal" factorial base number 987654321 = 9×9!+8×8!+7×7!+6×6!+5×5!+4×4!+3×3!+2×2!+1×1!, which in base ten is 3,628,799 (which he calls "about 3.6 million"). In fact, adding one to this number gives 1000000000, which still doesn't require any digits larger than 9, but he maybe wishes to stay away from the mere possibility of representing the digit that ''ought'' to use another symbol. The first number that actually cannot be represented with our usual ten symbols {0,...,9} comes right after 9987654321, which in decimal equals 36,287,999.
 +
 
 +
In the comic, the top example represents 3×720 + 5×120 + 3×24 + 0×6 + 1×2 + 1×1, after calculating each factorial accordingly, which gives the decimal value of 2835, [[2835|this comic's number]].
 +
 
 +
 
 +
For completion of the examples shown in the panel, the numbers up to 200 in this variable base are:
 +
 
 +
1=1
 +
2=10
 +
3=11
 +
4=20
 +
5=21
 +
6=100
 +
7=101
 +
8=110
 +
9=111
 +
10=120
 +
11=121
 +
12=200
 +
13=201
 +
14=210
 +
15=211
 +
16=220
 +
17=221
 +
18=300
 +
19=301
 +
20=310
 +
21=311
 +
22=320
 +
23=321
 +
24=1000
 +
25=1001
 +
26=1010
 +
27=1011
 +
28=1020
 +
29=1021
 +
30=1100
 +
31=1101
 +
32=1110
 +
33=1111
 +
34=1120
 +
35=1121
 +
36=1200
 +
37=1201
 +
38=1210
 +
39=1211
 +
40=1220
 +
41=1221
 +
42=1300
 +
43=1301
 +
44=1310
 +
45=1311
 +
46=1320
 +
47=1321
 +
48=2000
 +
49=2001
 +
50=2010
 +
51=2011
 +
52=2020
 +
53=2021
 +
54=2100
 +
55=2101
 +
56=2110
 +
57=2111
 +
58=2120
 +
59=2121
 +
60=2200
 +
61=2201
 +
62=2210
 +
63=2211
 +
64=2220
 +
65=2221
 +
66=2300
 +
67=2301
 +
68=2310
 +
69=2311
 +
70=2320
 +
71=2321
 +
72=3000
 +
73=3001
 +
74=3010
 +
75=3011
 +
76=3020
 +
77=3021
 +
78=3100
 +
79=3101
 +
80=3110
 +
81=3111
 +
82=3120
 +
83=3121
 +
84=3200
 +
85=3201
 +
86=3210
 +
87=3211
 +
88=3220
 +
89=3221
 +
90=3300
 +
91=3301
 +
92=3310
 +
93=3311
 +
94=3320
 +
95=3321
 +
96=4000
 +
97=4001
 +
98=4010
 +
99=4011
 +
100=4020
 +
101=4021
 +
102=4100
 +
103=4101
 +
104=4110
 +
105=4111
 +
106=4120
 +
107=4121
 +
108=4200
 +
109=4201
 +
110=4210
 +
111=4211
 +
112=4220
 +
113=4221
 +
114=4300
 +
115=4301
 +
116=4310
 +
117=4311
 +
118=4320
 +
119=4321
 +
120=10000
 +
121=10001
 +
122=10010
 +
123=10011
 +
124=10020
 +
125=10021
 +
126=10100
 +
127=10101
 +
128=10110
 +
129=10111
 +
130=10120
 +
131=10121
 +
132=10200
 +
133=10201
 +
134=10210
 +
135=10211
 +
136=10220
 +
137=10221
 +
138=10300
 +
139=10301
 +
140=10310
 +
141=10311
 +
142=10320
 +
143=10321
 +
144=11000
 +
145=11001
 +
146=11010
 +
147=11011
 +
148=11020
 +
149=11021
 +
150=11100
 +
151=11101
 +
152=11110
 +
153=11111
 +
154=11120
 +
155=11121
 +
156=11200
 +
157=11201
 +
158=11210
 +
159=11211
 +
160=11220
 +
161=11221
 +
162=11300
 +
163=11301
 +
164=11310
 +
165=11311
 +
166=11320
 +
167=11321
 +
168=12000
 +
169=12001
 +
170=12010
 +
171=12011
 +
172=12020
 +
173=12021
 +
174=12100
 +
175=12101
 +
176=12110
 +
177=12111
 +
178=12120
 +
179=12121
 +
180=12200
 +
181=12201
 +
182=12210
 +
183=12211
 +
184=12220
 +
185=12221
 +
186=12300
 +
187=12301
 +
188=12310
 +
189=12311
 +
190=12320
 +
191=12321
 +
192=13000
 +
193=13001
 +
194=13010
 +
195=13011
 +
196=13020
 +
197=13021
 +
198=13100
 +
199=13101
 +
200=13110
 +
 
 +
Note the apparent gap at 24 (4!) and 120 (5!) - apparent for those of us who are used to decimal numbers.
 +
 
 +
Factoradic™ numbers are actually less efficient than any other base. "Efficiency" for a base is normally defined by the radix economy. The actual definition is the size of the base (i.e. the number of possible digits) times the number of digits in a number, although it can be compared to {{w|binary-coded decimal|binary-coded decimals}}. Instead of using actual binary, a binary-coded decimal stores each decimal digit as a binary number. For example, 42 becomes (0100)(0010). This uses 8 bits, which is less efficient than the actual binary value of 101010, which is only 6 bits. It can vary which base is more efficient, like how from 9 to 15, quaternary is more efficient (base 4 * 2 digits = radix economy 8) than ternary (base 3 * 3 digits = radix economy 9). But as the number being represented goes up to infinity, the further you get from a hypothetical base e, the less efficient you become. As a quick example to demonstrate why large bases are less efficient, consider the number 3600. In base 60, it's only three digits, 1;0;0, but because each of those digits can have 60 possible values, its radix economy is 3*60=180. But even though the decimal representation uses a 4th digit, since there are only 10 possible values for each digit, the radix economy is only 4*10=40.
 +
 
 +
For a k-digit factoradic™ number, the 1st digit can have 2 values, the 2nd can have 3, the 3rd can have 4, up to the k-th digit having k+1 possible values, so the radix economy is effectively (k+1)(k+2)/2 - 1. Unfortunately, this is substantially more difficult to calculate, because it involved the inverse gamma function. But if you use ln n / ln ln n as an approximation of the asymptotic behavior of the inverse of Stirling's approximation, you can set up the limit ln n / ln^2 ln n, which diverges as n approaches infinity. Therefore, at least if you let factoradic™ numbers use other symbols for digits and increase past 10!, then no matter how large and inefficient of a base you're comparing it to, factoradic™ numbers will eventually be less efficient. Meanwhile, if you do stop at 10!-1, it's 9 digits, so its radix economy is 54. And if you solve 54 = b*floor(1+ln(10!-1)/ln(b)) for b, you find that b is approximately 6.75. So factoradic™ is more efficient than base 7 and up, but less efficient than binary, ternary, quaternary, quinary, and senary.
  
 
==Transcript==
 
==Transcript==
Line 27: Line 245:
 
:[Poster:]
 
:[Poster:]
  
−
: Variable-base Factoradic™ numbers
+
:Variable-base Factoradic™ numbers
 
:{|
 
:{|
 
|Base 7||Base 6||Base 5||Base 4||Base 3||Base 2
 
|Base 7||Base 6||Base 5||Base 4||Base 3||Base 2
Line 34: Line 252:
 
|}
 
|}
  
−
: Left side
+
:Left side
  
 
:{| class="wikitable"
 
:{| class="wikitable"
Line 62: Line 280:
 
|}
 
|}
  
−
: Right side
+
:Right side
  
 
:{| class="wikitable"
 
:{| class="wikitable"

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)

Templates used on this page:

Retrieved from "https://www.explainxkcd.com/wiki/index.php/2835:_Factorial_Numbers"