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.
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 descriptions of the different versions of Ackermann's function are now in my "Large Numbers — Long Notes" article:
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:
The list of "Busy Beavers and BB Candidate Record-Setters" has been moved to its own article, History of Busy Beaver Turing Machine Records.
Notes on Fermat numbers
The Fermat Numbers, Sloane's A000215, are all numbers of the form 22N+1:
Their factorizations are:
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 .
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
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
(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:
|1807||= 13 × 139|
|10650056950807||= 547 × 607 × 1033 × 31051|
|113423713055421844361000443||= 29881 × 67003 × 9119521 × 6212157481|
Other sequences, such as the Mersenne numbers are relatively prime, but there is no simple iterative formula to generate them.
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.
|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).
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:
|11||2047||= 23 × 89|
|23||8388607||= 47 × 178481|
|29||536870911||= 233 × 1103 × 2089|
|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|
|67||147573952589676412927||= 193707721 × 761838257287|
|71||2361183241434822606847||= 228479 × 48544121 × 212885833|
|73||9444732965739290427391||= 439 × 2298041 × 9361973132609|
|79||604462909807314587353087||= 2687 × 202029703 × 1113491139767|
|83||9671406556917033397649407||= 167 × 57912614113275649087721|
|97||158456325028528675187087900671||= 11447 × 13842607235828485645766393|
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:
|9||61||19||37||1883||Pervouchine (or "Pervushin")|
|11||107||33||65||1914||Powers (also claimed by Fauquembergue)|
|19||4253||1281||2561||19611103||Hurwitz & Selfridge|
|20||4423||1332||2663||19611103||Hurwitz & Selfridge|
|25||21701||6533||13066||19781030||Noll & Nickel|
|27||44497||13395||26790||19790408||Nelson & Slowinski|
|29||110503||33265||66530||19880128||Colquitt & Welsh|
|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.|
|45||37156667||11185272||22370543||20080906||Elvenich, GIMPS et al.|
|46||42643801||12837064||25674127||20090412||Strindmo, GIMPS et al.|
|47||43112609||12978188||25956377||20080823||Smith, GIMPS et al.|
|48||57885161||17425170||34850340||20130125||Cooper, GIMPS et al.|
|??||74207281||22338618||44677235||20160107||Cooper, GIMPS et al.|
|??||77232917||23249425||46498850||20180103||Pace, GIMPS et al.|
|??||82589933||24862048||49724095||20181221||Laroche, 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:
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. (As Randall Munroe says, "life is too short to sit around counting zeros and then looking up the Latin prefixes for big numbers".)
This page was written in the "embarrassingly readable" markup language RHTF, and some sections were last updated on 2023 Nov 03. s.27