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

Notes on Fermat numbers

Perfect numbers

Mersenne Numbers

Mersenne Primes

Highly Composite Numbers

My Personal Large-Numbers Interest

Origins of the Chuquet Number Names

Some History of Short vs. Long Scale Names

Latin Number Names

More Conway-Wechsler Number Names

Ad-hoc Chuquet Extensions

SI Prefixes

Googol and Googolplex

Real-valued hyper4 operator

Gödel's undecidable sentence

Notes on Skewes Number

Ackermann's Function

Comparing the Graham-Gardner Number to Chained Arrow Numbers

What Turing and Church Did Not Prove

Notes on Busy Beaver Function

Busy Beavers and BB Candidate Record-Setters

Analysis of the 1997 Marxen-Buntrock BB6 Record-Setter

Analysis of the Oct 2000 Marxen-Buntrock BB6 Record-Setter 'q'

Footnotes


Links to Moved Content

My notes on googol and googolplex have been moved to a separate article:

Googol and Googolplex

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 BB6 >= 95,524,079 is in a later section of the current page:

Analysis of the 1997 Marxen-Buntrock BB6 Record-Setter.


Notes on Fermat numbers

The Fermat Numbers, Sloane's A000215, are all numbers of the form 22N+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 F12=2212+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 Fn=22n+1 are relatively prime to each other.

Proof: First notice that

Fx - 2 = 22x - 1

Now set

Fn+1 - 2 = 22n+1 - 1

Substitute a^2 - 1 for (a - 1) × (a + 1) on the right hand side:

Fn+1 - 2 = (22n - 1) × (22n + 1)

therefore (substituting x for n+1) we have

Fx - 2 = (Fx-1 - 2) × Fx-1

we also have

F1 - 2 = F0

Therefore (by induction) it is true in general that

Fn - 2 = F0 × F1 × ... × Fn-1

Let m be any integer less than n. Fm is one of the terms on the right-hand side. Let d by any common factor of Fm and Fn. Since Fm appears on the right side, d must be a factor of Fn-2. Since d is a factor of Fn and of Fn-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 Fn, choose a single prime divisor pn. Since the Fermat numbers are relatively prime to each other (just proven) we know that any two primes pm and pn are different. Therefore there is at least one prime pn for each Fermat number Fn, 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:

w1 = 2
w2 = w1 + 1
w3 = w1 × w2 + 1
w4 = w1 × w2 × w3 + 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:

a1 = 2
an+1 = an2 - an + 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

Pp = 2p-1(2p-1)

where p is one of the Mersenne primes listed below. The issue of odd perfect numbers is still unresolved.

n p Pp
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 2520(2521-1) ≈ 2.356272×10313 (a bit too long to show all the digits)
14 607 2606*(2607-1) ≈ 1.410537×10365

For more perfect numbers, check the list of Mersenne primes below and use the formula Pp = 2p-1(2p-1).


Mersenne Numbers

The Mersenne numbers are numbers of the form 2p-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 2p-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 M2 = 3, M3 = 7, M5 = 31, M7 = 127, M13 = 8191, etc. For each Mersenne prime there is also a perfect number Pp given by

Pp = 2p-1(2p-1).

Here is a (reasonably complete) list of known primes p for which Mp is a Mersenne prime. For the first few, the "discovery" credit refers to the discovery of the corresponding perfect number:

n p digits
in Mp
digits
in Pp
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.

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 Mp = 2p-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 = 2p-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...×10917. 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 (1012); at age 8 I learned about vigintillion (1063) 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=1093, cigintillion=10123, etc. (continuing with different letters of the alphabet) to permit successive sets of ten names like unbigintillion=1096, duobigintillion=1099, 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)



Robert Munafo's home pages on HostMDS   © 1996-2016 Robert P. Munafo.
aboutcontact    mrob    mrob27    @mrob_27    mrob27
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and some sections were last updated on 2016 Nov 26. s.11