Main Page
Welcome to the explain xkcd wiki!
We have an explanation for all 2835 xkcd comics,
and only 43
(2%) are incomplete. Help us finish them!
Latest comic
| Factorial Numbers |
 Title text: So what do we do when we get to base 10? Do we use A, B, C, etc? No: Numbers larger than about 3.6 million are simply illegal. |
Explanation
|
This explanation may be incomplete or incorrect: Created by a VARIABLE-BASED BOT BEING ESCORTED OUT OF THE COMPUTER SCIENCE DEPARTMENT BY SECURITY - Please change this comment when editing this page. Do NOT delete this tag too soon. |
This comic is based on the factorial number system, which is a way of writing integers or real numbers using factorials instead of powers. Unlike the 'proper' version of this system, Randall's version does not include the rightmost digit that adds no information, since it is always 0.
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.
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×102 + 3×101 + 7×100, 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×161 + 9×160, i.e. eight sixteens and nine units. The 8 is in the sixteens place, and the 9 is in the ones place.
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.
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, 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 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
|
|
This transcript is incomplete. Please help editing it! Thanks. |
- [Cueball is standing in front of a large poster. There are two uniformed officers (a Ponytail and a further Cueball, wearing badged hats) approaching Cueball.]
- [Poster:]
- Variable-base Factoradic™ numbers
Base 7 Base 6 Base 5 Base 4 Base 3 Base 2 3 5 3 0 1 1
- Left side
Base 10 Factoradic 1 1 2 10 3 11 4 20 5 21 6 100 7 101 21 311 22 320 23 321
- Right side
Base 10 Factoradic 24 1,000 25 1,001 5,038 654,320 5,039 654,321 5,040 1,000,000 999,998 266,251,210 999,999 266,251,211 1,000,000 266,251,220 1,000,001 266,251,221
- Cueball: Small numbers like seven or nineteen shouldn't use big numerals like "7" or "9".
- Cueball: I mean, "9" is the biggest numeral we have! It should be reserved for big numbers.
- Cueball: Small numbers should be written with small numerals like "1" or "2".
- Cueball: That's why my variable-base system uses...Hey! No, listen!
- [Caption under the comic:] Factorial numbers are the number system that sounds most like a prank by someone who's about to be escorted out of the math department by security.
Is this out of date? .
New here?
Last 7 days (Top 10) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
You can read a brief introduction about this wiki at explain xkcd. Feel free to sign up for an account and contribute to the wiki! We need explanations for comics, characters, themes and everything in between. If it is referenced in an xkcd web comic, it should be here.
- If you're new to wiki editing, see the explain xkcd:Editor FAQ for a specific guidance to this Wiki and the more general help on how to edit wiki pages. There's also a handy wikicode cheatsheet.
- Discussion about the wiki itself happens at the Community portal.
- You can browse the comics from List of all comics or by navigating the category tree at Category:Comics.
- There are incomplete explanations listed here. Feel free to help out by expanding them!
Rules
Don't be a jerk.
There are a lot of comics that don't have set-in-stone explanations; feel free to put multiple interpretations in the wiki page for each comic.
If you want to talk about a specific comic, use its discussion page.
Please only submit material directly related to (and helping everyone better understand) xkcd... and of course only submit material that can legally be posted (and freely edited). Off-topic or other inappropriate content is subject to removal or modification at admin discretion, and users who repeatedly post such content will be blocked.
If you need assistance from an admin, post a message to the Admin requests board.
