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:

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

Analysis of the 1997 Marxen-Buntrock BB₆ Record-Setter.

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 2^{2^N}+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₁₂=2^2¹²+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 [59].

This is Goldbach's proof, which he gave in a letter written to Euler in 1730. I have expanded and rewritten it from Caldwell ¹⁴

Lemma (Goldbach, 1730): Any two Fermat numbers F_n=2^2ⁿ+1 are relatively prime to each other.

Proof: First notice that

F_x - 2 = 2^{2^x} - 1

Now set

F_n+1 - 2 = 2^2ⁿ⁺¹ - 1

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

F_n+1 - 2 = (2^2ⁿ - 1) × (2^2ⁿ + 1)

therefore (substituting x for n+1) we have

F_x - 2 = (F_x-1 - 2) × F_x-1

we also have

F₁ - 2 = F₀

Therefore (by induction) it is true in general that

F_n - 2 = F₀ × F₁ × ... × 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₁ = 2
w₂ = w₁ + 1
w₃ = w₁ × w₂ + 1
w₄ = w₁ × w₂ × w₃ + 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₁ = 2
a_n+1 = a_n² - 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⁵²⁰(2⁵²¹-1) ≈ 2.356272×10³¹³ (a bit too long to show all the digits)
14	607	2⁶⁰⁶*(2⁶⁰⁷-1) ≈ 1.410537×10³⁶⁵

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₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127, M₁₃ = 8191, etc. For each Mersenne prime 2^p-1 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.
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.
??	136279841	41024320	82048640	20241021	Durant, 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 57885161 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 ¹⁵ 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⁹¹⁷. 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¹²); at age 8 I learned about vigintillion (10⁶³) 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⁹³, cigintillion=10¹²³, etc. (continuing with different letters of the alphabet) to permit successive sets of ten names like unbigintillion=10⁹⁶, duobigintillion=10⁹⁹, 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".)

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 8)

This page was written in the "embarrassingly readable" markup language RHTF, and some sections were last updated on 2024 Nov 09.

s.30