Large Numbers — Notes
This page goes into greater detail on certain topics related to large numbers and quickly-growing functions described on my large numbers page. The topics are presented in about the same order as on that page.
Contents
My Personal Large-Numbers Interest
Origins of the Chuquet Number Names
Some History of Short vs. Long Scale Names
More Conway-Wechsler Number Names
Comparing the Graham-Gardner Number to Chained Arrow Numbers
What Turing and Church Did Not Prove
Busy Beavers and BB Candidate Record-Setters
Analysis of the 1997 Marxen-Buntrock BB_{6} Record-Setter
Analysis of the Oct 2000 Marxen-Buntrock BB_{6} Record-Setter 'q'
Links to Moved Content
My notes on googol and googolplex have been moved to a separate article:
My description of an extension of the hyper4 function to reals has moved to my Hyper4 article:
My Extension to Real-Valued Arguments.
My descriptions of the different versions of Ackermann's function are now in my "Large Numbers — Long Notes" article:
Versions of Ackermann's Function.
My analysis of the 1997 Marxen-Buntrock Busy Beaver record-setter that established BB_{6} >= 95,524,079 is in a later section of the current page:
Analysis of the 1997 Marxen-Buntrock BB_{6} Record-Setter.
Notes on Fermat numbers
The Fermat Numbers, Sloane's A000215, are all numbers of the form 2^{2N}+1:
3
5
17
257
65537
4294967297
18446744073709551617
340282366920938463463374607431768211457
...
Their factorizations are:
3
5
17
257
65537
641 × 6700417
274177 × 67280421310721
59649589127497217 × 5704689200685129054721
...
All of the factors of all of the Fermat numbers, arranged in ascending order, make Sloane's sequence A023394. The smallest one not shown here is 114689, which factors F_{12}=2^{212}+1. There is a shared computing project, similar to the Mersenne prime search, to find all terms in this sequence; see my page on A023394.
Goldbach's Proof That There are an Infinite Number of Primes
There are many proofs of the "infinitude" of primes. Eleven are listed in a book by Paulo Ribenboim [48].
This is Goldbach's proof, which he gave in a letter written to Euler in 1730. I have expanded and rewritten it from Caldwell ^{14}
Lemma (Goldbach, 1730): Any two Fermat numbers F_{n}=2^{2n}+1 are relatively prime to each other.
Proof: First notice that
F_{x} - 2 = 2^{2x} - 1
Now set
F_{n+1} - 2 = 2^{2n+1} - 1
Substitute a^2 - 1 for (a - 1) × (a + 1) on the right hand side:
F_{n+1} - 2 = (2^{2n} - 1) × (2^{2n} + 1)
therefore (substituting x for n+1) we have
F_{x} - 2 = (F_{x-1} - 2) × F_{x-1}
we also have
F_{1} - 2 = F_{0}
Therefore (by induction) it is true in general that
F_{n} - 2 = F_{0} × F_{1} × ... × F_{n-1}
Let m be any integer less than n. F_{m} is one of the terms on the right-hand side. Let d by any common factor of F_{m} and F_{n}. Since F_{m} appears on the right side, d must be a factor of F_{n}-2. Since d is a factor of F_{n} and of F_{n}-2, d is a factor of 2. But every Fermat number is odd, so d must be 1. Thus, the only common factor of any Fermat number and any other smaller Fermat number is 1: so the two Fermat numbers are relatively prime.
Theorem (Goldbach, 1730): There are infinitely many primes.
Proof: For each Fermat number F_{n}, choose a single prime divisor p_{n}. Since the Fermat numbers are relatively prime to each other (just proven) we know that any two primes p_{m} and p_{n} are different. Therefore there is at least one prime p_{n} for each Fermat number F_{n}, that is, at least one prime for every integer n.
Since any two Fermat numbers are relatively prime to each other, the Fermat sequence is called pairwise relatively prime. Any other pairwise relatively prime sequence can also be used to prove that there is an infinite number of primes. Here is another example:
w_{1} = 2
w_{2} = w_{1} + 1
w_{3} = w_{1} × w_{2} + 1
w_{4} = w_{1} × w_{2} × w_{3} + 1
etc.
(Other valid sequences result if you change the initial 2 and the 1's at the end of subsequent lines to any other pair of numbers that are relatively prime to each other). Another form of the same sequence is:
a_{1} = 2
a_{n+1} = a_{n}^{2} - a_{n} + 1
This is called Sylvester's sequence (Sloane's A000058). The sequence starts:
2 | (prime) |
3 | (prime) |
7 | (prime) |
43 | (prime) |
1807 | = 13 × 139 |
3263443 | (prime) |
10650056950807 | = 547 × 607 × 1033 × 31051 |
113423713055421844361000443 | = 29881 × 67003 × 9119521 × 6212157481 |
etc. |
Other sequences, such as the Mersenne numbers are relatively prime, but there is no simple iterative formula to generate them.
Perfect numbers
Following are the smaller perfect numbers. All are of the form
P_{p} = 2^{p-1}(2^{p}-1)
where p is one of the Mersenne primes listed below. The issue of odd perfect numbers is still unresolved.
n | p | P_{p} |
1 | 2 | 6 |
2 | 3 | 28 |
3 | 5 | 496 |
4 | 7 | 8128 |
5 | 13 | 33550336 |
6 | 17 | 8589869056 |
7 | 19 | 137438691328 |
8 | 31 | 2305843008139952128 |
9 | 61 | 2658455991569831744654692615953842176 |
10 | 89 | 191561942608236107294793378084303638130997321548169216 |
11 | 107 | 13164036458569648337239753460458722910223472318386943117783728128 |
12 | 127 | 14474011154664524427946373126085988481573677491474835889066354349131199152128 |
13 | 521 | 2^{520}(2^{521}-1) ≈ 2.356272×10^{313} (a bit too long to show all the digits) |
14 | 607 | 2^{606}*(2^{607}-1) ≈ 1.410537×10^{365} |
For more perfect numbers, check the list of Mersenne primes below and use the formula P_{p} = 2^{p-1}(2^{p}-1).
Mersenne Numbers
The Mersenne numbers are numbers of the form 2^{p}-1 where p is prime. Here are the first 25. Because the Mersennes are pairwise relatively prime, each prime number will occur at most once in the factors column of this table:
p | 2^{p}-1 | factors |
2 | 3 | (prime) |
3 | 7 | (prime) |
5 | 31 | (prime) |
7 | 127 | (prime) |
11 | 2047 | = 23 × 89 |
13 | 8191 | (prime) |
17 | 131071 | (prime) |
19 | 524287 | (prime) |
23 | 8388607 | = 47 × 178481 |
29 | 536870911 | = 233 × 1103 × 2089 |
31 | 2147483647 | (prime) |
37 | 137438953471 | = 223 × 616318177 |
41 | 2199023255551 | = 13367 × 164511353 |
43 | 8796093022207 | = 431 × 9719 × 2099863 |
47 | 140737488355327 | = 2351 × 4513 × 13264529 |
53 | 9007199254740991 | = 6361 × 69431 × 20394401 |
59 | 576460752303423487 | = 179951 × 3203431780337 |
61 | 2305843009213693951 | (prime) |
67 | 147573952589676412927 | = 193707721 × 761838257287 |
71 | 2361183241434822606847 | = 228479 × 48544121 × 212885833 |
73 | 9444732965739290427391 | = 439 × 2298041 × 9361973132609 |
79 | 604462909807314587353087 | = 2687 × 202029703 × 1113491139767 |
83 | 9671406556917033397649407 | = 167 × 57912614113275649087721 |
89 | 618970019642690137449562111 | (prime) |
97 | 158456325028528675187087900671 | = 11447 × 13842607235828485645766393 |
Mersenne Primes
A Mersenne number is a Mersenne prime if it is prime. In the above list, the Mersenne primes are M_{2} = 3, M_{3} = 7, M_{5} = 31, M_{7} = 127, M_{13} = 8191, etc. For each Mersenne prime there is also a perfect number P_{p} given by
P_{p} = 2^{p-1}(2^{p}-1).
Here is a (reasonably complete) list of known primes p for which M_{p} is a Mersenne prime. For the first few, the "discovery" credit refers to the discovery of the corresponding perfect number:
n | p | digits in M_{p} | digits in P_{p} | year found | discoverer(s) |
1 | 2 | 1 | 1 | ~500BC | unknown |
2 | 3 | 1 | 2 | ~275BC | Euclid |
3 | 5 | 2 | 3 | ~275BC | Euclid |
4 | 7 | 3 | 4 | ~275BC | Euclid |
5 | 13 | 4 | 8 | 1456 | unknown |
6 | 17 | 6 | 10 | 1588 | Cataldi |
7 | 19 | 6 | 12 | 1588 | Cataldi |
8 | 31 | 10 | 19 | 1772 | Euler |
9 | 61 | 19 | 37 | 1883 | Pervouchine (or "Pervushin") |
10 | 89 | 27 | 54 | 1911 | Powers |
11 | 107 | 33 | 65 | 1914 | Powers (also claimed by Fauquembergue) |
12 | 127 | 39 | 77 | 1876 | Lucas |
13 | 521 | 157 | 314 | 19520130 | Robinson |
14 | 607 | 183 | 366 | 19520130 | Robinson |
15 | 1279 | 386 | 770 | 19520626 | Robinson |
16 | 2203 | 664 | 1327 | 19521007 | Robinson |
17 | 2281 | 687 | 1373 | 19521009 | Robinson |
18 | 3217 | 969 | 1937 | 19570908 | Riesel |
19 | 4253 | 1281 | 2561 | 19611103 | Hurwitz & Selfridge |
20 | 4423 | 1332 | 2663 | 19611103 | Hurwitz & Selfridge |
21 | 9689 | 2917 | 5834 | 19630511 | Gillies |
22 | 9941 | 2993 | 5985 | 19630516 | Gillies |
23 | 11213 | 3376 | 6751 | 19630602 | Gillies |
24 | 19937 | 6002 | 12003 | 19710304 | Tuckerman |
25 | 21701 | 6533 | 13066 | 19781030 | Noll & Nickel |
26 | 23209 | 6987 | 13973 | 19790209 | Noll |
27 | 44497 | 13395 | 26790 | 19790408 | Nelson & Slowinski |
28 | 86243 | 25962 | 51924 | 19821025 | Slowinski |
29 | 110503 | 33265 | 66530 | 19880128 | Colquitt & Welsh |
30 | 132049 | 39751 | 79502 | 19830919 | Slowinski |
31 | 216091 | 65050 | 130100 | 19850901 | Slowinski |
32 | 756839 | 227832 | 455663 | 19920401 | Slowinski & Gage |
33 | 859433 | 258716 | 517430 | 19940201 | Slowinski & Gage |
34 | 1257787 | 378632 | 757263 | 19960903 | Slowinski & Gage |
35 | 1398269 | 420921 | 841842 | 19961113 | Armengaud, Woltman et al. |
36 | 2976221 | 895932 | 1791864 | 19970824 | Spence, Woltman et al. |
37 | 3021377 | 909526 | 1819050 | 19980127 | Clarkson, Woltman, Kurowski et al. |
38 | 6972593 | 2098960 | 4197919 | 19990601 | Hajratwala, Woltman, Kurowski et al. |
39 | 13466917 | 4053946 | 8107892 | 20011114 | Cameron, Woltman, Kurowski, et al. |
40 | 20996011 | 6320430 | 12640858 | 20031202 | Shafer, GIMPS et al. |
41 | 24036583 | 7235733 | 14471465 | 20040515 | Findley, GIMPS et al. |
42 | 25964951 | 7816230 | 15632458 | 20050218 | Nowak, GIMPS et al. |
43 | 30402457 | 9152052 | 18304103 | 20051215 | Cooper, Boone, GIMPS et al. |
44 | 32582657 | 9808358 | 19616714 | 20060904 | Cooper, Boone, GIMPS et al. |
?? | 37156667 | 11185272 | 20080906 | Elvenich, GIMPS et al. | |
?? | 42643801 | 12837064 | 20090412 | Strindmo, GIMPS et al. | |
?? | 43112609 | 12978188 | 20080823 | Smith, GIMPS et al. | |
?? | 57885161 | 17425170 | 20130125 | Cooper, GIMPS et al. | |
?? | 74207281 | 22338618 | 20160107 | Cooper, GIMPS et al. | |
?? | 77232917 | 23249425 | 20180103 | Pace, GIMPS et al. |
(Sources: GIMPS, Prime Pages
For the primes near the end of the list labeled with "??", it is not known if there are Mersenne primes in the region between them, because the eligible primes have not all been completely tested. (For example, the 29th Mersenne prime was found in 1988, five years after the immediately preceding and following Mersenne primes.) All values of p less than 4395400 have been tested (only the prime values need to be tested, because p must be prime for M_{p} = 2^{p}-1 to be prime.) See the Mersenne Search Status page ^{15} for the most current information (and find out how you can set up your computer to join in the search!).
Searches for Mersenne primes are simplified by a number of special tests, that are not generally applicable to searches for all primes. For example, if p is prime, then N = 2^{p}-1, when represented in binary, has p 1's and no 0's. It is not a multiple of 3 (except for the case p=2) because the number of binary digits is odd — so if you group the binary digits in groups of 2 and add modulo 3 (a process analogous to "casting out 9's") you'll get 1 left over. A similar process for groups of 3 1's shows that N is not a multiple of 7 except for the case p=3.
Highly Composite Numbers
The smallest number that has at least a googol distinct factors is about 4.57936...×10^{917}. Its digits (in groups of 30) are: 457936006084633875 260691932542213506579481395376 080192442872707759996212114957 373537195900697943283211344130 969977204683723647091975242566 556807073476262370119366712949 612051508874565615465951982148 103948322515169952026557331614 199239782652240565877185274882 891122589783986489974588207230 026310073238799349251084594897 863556829085566422093207975001 895285824382289647389848615424 710629561529529589935914349946 023950287863307022313442880758 800532983282085207377266536998 146723331964258315488766981883 904240306133944424567760471103 539279962416731476757145320641 439420037963516042879919957607 890943287019373144639492683640 803862704805497501551907216898 677744138585826270309663329962 841518933729157858558919253022 063551926057138672786596389094 200184031909805595086778342937 081605771699885426749776777391 919555685119629369584896777148 250878775274042686107865894781 763500774758450843791837394393 056896301600021929961984000000.
My Personal Large-Numbers Interest
Large numbers have interested me almost all my life. At age 5 100 was the biggest number I knew, by age 6 it was 1000000, at age 7 I asked my Mom what was after 1000 and a million and she told me about the (lesser) billion and trillion (10^{12}); at age 8 I learned about vigintillion (10^{63}) in a book from the school library. I loved vigintillion so much I wrote it in the sand in the schoolyard:
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
prompting much harassment from the other children!
The same year, bored while waiting in the lunch line, I decided to count whenever I was waiting in line. My count continued from one day to the next, always picking up where I had left off. I got up to around 35,000 after a few months, at which point I had lost my place so many times I decided it was not worth the effort.
I made personal Chuquet extensions at age 10, inventing names like bigintillion=10^{93}, cigintillion=10^{123}, etc. (continuing with different letters of the alphabet) to permit successive sets of ten names like unbigintillion=10^{96}, duobigintillion=10^{99}, and so on. This system had plenty of problems — for example, in a hypothetical standard American English pronunciation, at least two of cigintillion, kigintillion and sigintillion must sound the same. Soon I realized that I could have gotten more range by using dipthongs (blingintillion, bringintillion, ...) and that my system was redundant to the existing standard — my bigintillion is the same as the standard trigintillion, etc. Within a month or two I switched to scientific notation and never looked back.
I kept going: by age 10 I had (re-)invented the higher dyadic operators and by age 13 I knew the Steinhaus-Moser notation. That was about as high as anyone had gone at the time, so I turned my attention to computers and began to write programs to manipulate large Class-2 numbers. My latest accomplishment in that area is HyperCalc, first made as a calculator program for the Palm Pilot, and now in Perl and JavaScript versions. It literally cannot overflow, even by running in a loop that endlessly replaces a number with its own factorial.
. . . Forward to page 2 . . . Last page (page 6)
This page was written in the "embarrassingly readable" markup language RHTF, and some sections were last updated on 2020 Mar 26. s.11