It's Prime Time!

In this part of the number book, we will cover a set of numbers that mathematicians have studied for centuries and that remains very mysterious: the primes. Some of what we will cover has real world uses, such as in cryptography.

The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43... These numbers have no factors other than 1 and themselves. A prime number of objects cannot be divided into any equally-sized groups.

2 is the only even prime number, as all other even numbers are divisible by 2. 1 is not prime, as it is only evenly divisible by 1. All numbers that end in 5 are not prime, because they are all divisible by 5.

Small primes are easy to hunt using a sieve. First, write down a square of integers up to any given square number, excluding 1. Then, highlight 2, and cross out all multiples of 2. Do the same for 3, 5, 7, 11, ... up to the last prime less than the square root of the number in the lower-right corner. The remaining numbers will be the primes.

Sieves are useful for hunting small primes, but what if you wanted to know if, say, 29,998,559,671,349 is prime? The only way to know if a large number is prime is to make sure there is no smaller number greater than 1 that divides into it, and the larger the number, the longer this will take.

It turns out that we don’t have to check every single number below N to know if N is prime. First of all, we can eliminate any composite numbers because if a prime doesn’t divide into N, then no integer evenly divisible by it can.

We need only check primes up to the square root of N to know whether N is prime, because a number must have at least one factor smaller than its square root and another larger than its square root. To check if 21,397 is prime, for instance, we would only need to check all primes below 146.

This method is very inefficient for large numbers, as we would already need to check all primes below a quadrillion for a 30-digit prime. However, truly gargantuan primes have been found using computers, the largest of which has over 24.8 million decimal digits, and would take thousands of pages in a Word document.

Many of the largest known primes are of the form 2n – 1, and are named Mersenne primes, after the 17th century monk Marin Mersenne. A Mersenne number is a number of the form 2n – 1, usually when n is prime.

The first few Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647 …, corresponding to indices of 2, 3, 5, 7, 13, 17, 19, 31, ... respectively.  8191 and 131071 have been known to be prime for centuries, whereas the Mersenne primes beginning at 2147483647 have all been discovered in the last few hundred years. 2147483647 is notable for being the signed 32-bit integer limit.

It can be easily shown that if n is composite, 2n – 1 is also composite. If a number’s binary representation is 111…111 where the number of 1s is n and m is a factor of n, then it must be divisible by 111…(m)…12 as it is 111…(m)…1……111…(m)…1……(k)……111…(m)…12 (letting k be the result of dividing n by m. On the other hand, if n is prime, 2n – 1 may or may not be prime. 11 is prime, but 211 – 1 (or 2047) is equal to 23*89, and is thus not prime. The next primes p for which 2p – 1 is composite are 23, 29, 37, 41, 43, 47, 53 , 59, 67, 71, 73, and 83. 2^53 - 1 is notable for being the largest odd integer that can be exactly represented in the double-precision floating point format.

If 2^p - 1 is composite for a prime p, then its factors will all be congruent to 1 mod p.

The largest known prime is 2136,279,841 – 1, which was found to be prime in October 2024. It is a number with 41,024,320 digits, meaning its full decimal expansion would take over 11,200 pages in normal 11-point font! 

Below are its first and last digits.

881694327503833265553939100378117358971207354509066041067156376412422630694756841441725990347723283108837509739959776874  .........

852806517931459412567957568284228288124096109707961148305849349766085764170715060409404509622104665555076706219486871551 

(WILL MOVE THIS TO AN APPENDIX PAGE)

Below are its first and last digits.

148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ..............

.........062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591 

The largest factored composite Mersenne number is 263,703 - 1, which is 42,808,417 * p, where p is a 19,169-digit prime, whose first and last digits are given below.

762578600827061870005345588829422498482464001086601511699753340801654371373948514671469866673197457638301094881203328934656345928031851110859675123451393231508......53990488888656693488542996857211864444935415352491992917263891563354483082516020631949371769675584650115490421342987816371166029442950487188748211805124530271

Prizes of $150,000 and $250,000 are being offered for the discovery of prime numbers with at least 100,000,000 digits and 1,000,000,000 digits respectively. The first candidate for a Mersenne prime with at least 100,000,000 digits is 2332,192,831 - 1, and the smallest potential Mersenne prime with at least 1,000,000,000 digits is 23,321,928,097 - 1.

Double Mersenne numbers are Mersenne numbers with indices that are themselves Mersenne primes. The first few double Mersenne numbers are 7, 127, 2147483647, and 170141183460467467231687303715884105727.

The first four double Mersenne numbers are all prime, but all further integers of the form 2^(2^n - 1) - 1 for a prime 2^n - 1 that have been tested have been found to be composite. MM₁₃, MM₁₇, MM19, and MM31 are all composite (the last one having over 646 million digits in its decimal representation), and the next double Mersenne number with a prime index, MM₆₁, is approximately 1.714009*10694,127,911,065,419,641, making it far too large for any known primality test, or even to compute its complete decimal expansion.

The sequence 2, M2, MM₂, MM(M(2)), … has been named the Catalan-Mersenne sequence. The first few Catalan-Mersenne numbers are 2, 3, 7, 127, 170141183460467467231687303715884105727, …, but the next has over 51 undecillion digits, and thus is already much larger than any number we can test for primality as of yet.

The first few primes of the form 2n - 3 are 5, 13, 29, 61, 509, 1021, 4093, 16381, 1048573, 4194301, 16777213, 536870909, ...

A number that is one more than a number of the form 22^n is called a Fermat number. However, there are only five known Fermat primes, the largest being 65,537, and it is conjectured that there are no more. The next Fermat number, 4,294,967,297, is composite, and in fact, all further Fermat numbers up to 2^2^32 + 1 (which has nearly 1.3 billion digits), as well as some larger ones, are known to be composite. The largest Fermat number proven composite is 22^3,329,780 + 1, which has more than 101,002,363 digits (!). Its prime factor is (193 x 23,329,782) + 1, which is itself a number with 1,002,367 digits.

F0 = 3 (prime)

F1 = 5 (prime)

F2 = 17 (prime)

F3 = 257 (prime)

F4 = 65,537 (the largest known Fermat prime)

F5 = 4,294,967,297

= 641 * 6,700,417

F6 = 18,446,744,073,709,551,617

= 274,177 * 67,280,421,310,721

F7 = 340,282,366,920,938,463,463,374,607,431,768,211,457

= 59,649,589,127,497,217 * 5,704,689,200,685,129,054,721

F8 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937

= 1,238,926,361,552,897 * 93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321

A twin prime pair is a pair of prime numbers that differ by 2. The twin product is the product of the two prime numbers, and is always one less than the square of the composite number between the two primes.

Below are the first pairs of twin primes.

(3, 5), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), …

It is possible to make a sieve for numbers harboring twin primes, similar to the primes themselves. First, start with all numbers from 2 up to a particular limit. Then, cross out 2, because 1 is not prime. Next, cross out all numbers that are one more or less than a multiple of 2 (that is, odd numbers). Then, cross out all numbers that are one more or less than a multiple of 3, leaving only (except for 4) the multiples of 6. Next, cross out all the remaining numbers ending in a 4 or 6, except for 4 and 6 themselves. Do the same for the primes 7, 11, 13, etc., until there are no more numbers left to cross out. The remaining numbers, when either incremented or decremented, give the twin primes.

Prime triplets are of the form  (6n-2, 6n+2, 6n+4).

Prime quadruplets are of the form (30n + 11, 30n + 13, 30n + 17, 30n + 19), except for 5,7,11,13. Below are the first numbers n such that 10n+1, 10n+3, 10n+7, and 10n+9 are all prime.

1, 10, 19, 82, 148, 187, 208, 325, 346, 565, 943, 1300, 1564, 1573, 1606, 1804, 1891, 1942, 2101, 2227, 2530, 3172, 3484, 4378, 5134, 5533, 6298, 6721, … (OEIS: A007811)

Prime quadruplets become rarer as we travel further along, much like the primes themselves. The ratio of the n-th term in the above sequence to n is always increasing: at the 2nd term it is merely 5, but by the 10th term it’s already 56.5 and by the 100th term, the ratio is just slightly above 477.

It is unknown if there are infinitely many prime quadruplets (if there were, it would imply the twin prime conjecture). However, the largest known prime quadruplet consists of four 10,132-digit primes, specifically (667674063382677*233,608 – 1,  667674063382677*233,608 + 1, 667674063382677*233,608 + 5, 667674063382677*233,608 + 7), the smallest of which is below.

There are also constants known to generate primes. An example is Mills’ constant; whose decimal representation begins 1.306377…  When repeatedly cubing Mills’ constant, the integer part of each result is a prime:

2
11
1361
2521008887
16022236204009818131831320183
4113101149215104800030529537915953170486139623539759933135949994882770404074832568499

The next Mills’ prime (below) is a number of 254 digits.

69583804376962741608539276573538592864835917395924759602456009555710439562534603942132717654085619871657656850305900008136962235482689306913393638227620908148480337200487348871845278976469184329953753965251639715257390268487534179757699110378097045955949

There exists a similar constant equal to about 1.453…, which, when repeatedly cubed, will also generate a series of primes:

3
29
24391

Another similar constant exists (equal to 1.5246999605380943599233635756884211622202236231…), which will give a prime in the integer part when repeatedly squared:

2
5
29
853
727613
529420677791
280286254072681840639693
78560384222095957698731679318817728959447134363

6171733969123343492646848506619169923409997533838936981763723291254666901983578165372575415773

38090300185630979407862526915375227897406420243104962293692328497413516471480867341214171470690428491487104955851086223324879408923333614818925286486522328331074171625051233528423817187667

2105026566456950576974765791617310405080182799403528900317501493517070407298733921181990193407231801437794083149308245499471107123178944807453730031592160963225170483125962942848266675605616441846432145924606837701476025109370522412427317600804201258577526178670425681313958905750815647744490724245456156220323712712771592771580569516537900462274408633824748961582141083837458534816036730734320316375100153043900776523429738080239485678997202748850179172561562860490011852688695130391626471544292163501827664696110096809557007351405735419350432680968098490345589626427576292913792186687056204262958193134713610968747162958098925522964507589344726976276271163934758185867446989768887541305780135020808082967563934122807704444794896789338846027416989917

and another constant that generates every single prime when plugged into the following formula: fn+1 = floor(fn)*(fn – floor(fn) + 1). The constant is equal to 2.92005097731613471209256… Below are the first few values of fn.

2*(2.920050977316134712… - 2 + 1) = 2*1.920050977316134712… = 3.840101954632269424…
3*(3.840101954632269424… - 3 + 1) = 3*1.840101954632269424… = 5.520305863896807272…
5*(5.520305863896807272… - 5 + 1) = 5*1.520305863896807272… = 7.601529319484036362…
7*(7.601529319484036362… - 7 + 1) = 7*1.601529319484036362… = 11.21070523638825452…
11*(11.21070523638825452… - 11 + 1) = 11*1.210705236388254… = 13.317757600270799

The smallest primes in arithmetic progression of 3 are 3, 5, 7, followed by 31, 37, and 43. The smallest arithmetic progression of 4 primes is 61, 67, 73, and 79. The smallest progression of 5, is 107, 137, 167, 197, and 227. This is also the first arithmetic progression of 6 since it can be continued for one more term, 257.

The smallest arithmetic progression of seven primes is 47, 257, 467, 677, 887, 1097, and 1307.

Prime numbers become increasingly rare as you travel further along the number line, but there is no largest prime, which can be proven as follows. Suppose you have a list that supposedly contains all primes. However, by multiplying all the primes on your list together and adding 1, you have found a number that leaves a remainder of 1 when divided by all the primes on your list, meaning it must be either divisible by a prime not on your list, or a prime number itself. Either way, you have discovered a prime not included on your list.

Among the first 10 whole numbers, there are 4 primes, meaning that 40% of the integers from 1 to 10 are prime. There are 25 primes from 1 to 100, so only 25% of the integers from 1 to 100 are prime. From 1 to 1000, there are 168 primes, which is only 16.8%.

The prime-counting function, denoted by the Greek letter π (pi), gives the number of primes from 1 to the input. Its growth rate is of particular interest in number theory, and was conjectured in the late 1700s to be approximately equal to x/ln(x), where ln denotes the natural logarithm, 

We see that the number of cousin primes up to n gets closer and closer to the number of twin primes up to n, but is always slightly less. However, prime gaps of 6 are the most common, comprising about 13% of prime gaps up to 108.

Below are the first values of the 10n-th prime. We will denote the n-th prime function (or in other words, the inverse of the prime-counting function) as Π(n) (using the capital pi).

1st prime: 2
10th prime: 29
100th prime: 541
1,000th prime: 7919
10,000th prime: 104729
100,000th prime: 1299709
(106)th prime: 15485863
(107)th prime: 179424673
(108)th prime: 2038074743
(109)th prime: 22801763489
(1010)th prime: 252097800623
(1011)th prime: 2760727302517
(1012)th prime: 29996224275833
(1013)th prime: 323780508946331
(1014)th prime: 3475385758524527
(1015)th prime: 37124508045065437
(1016)th prime: 394906913903735329
(1017)th prime: 4185296581467695669
(1018)th prime: 44211790234832169331
(1019)th prime: 465675465116607065549
(1020)th prime: 4892055594575155744537
(1021)th prime: 51271091498016403471853
(1022)th prime: 536193870744162118627429
(1023)th prime: 5596564467986980643073683
(1024)th prime: 58310039994836584070534263

Using methods to estimate П(n) for large n, we find that the googolth prime (for example) is between 2.347125653*10102 and 2.347125801*10102, determining the first 7 digits and narrowing down the possibilities for the 8th digit to 6, 7, or 8. If we assume the Riemann hypothesis, we can obtain more digits of the googolth prime:

2,347,125,735,865,764,178,036,135,909,936,302,071,965,422,425,97x,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxx,xxX where x is an unknown digit and X could be 1, 3, 7, or 9.

We can also find the number of primes in a certain arithmetic progression. The number of primes congruent to 1 mod 4 up to a given n (which we can denote π4,1(n)) is, on the long term, roughly equivalent to the number of primes congruent to 3 mod 4 up to n (which we can denote π4,3(n)), however, the primes congruent to 3 mod 4 seem to be ahead in the race until 26861. 

J. E. Littlewood showed in 1914 that there are infinitely many sign changes of π4,3(n) - π4,1(n), and also showed that the difference between pi(x) and another function we will mention changes infinitely many times.

There is an interesting pattern in the last digits of primes that may not be very obvious at first.

Among the first 5,800,000 primes, there are 1,449,824 primes that end in 1, 1 that ends in 2 (obviously), 1,450,185 that end in 3, just 1 that ends in a 5 (obviously) 1,450,153 that end in a 7, and 1,449,836 that end in a 9.

The distribution among the 4 digits coprime to 10 seems pretty uniform, so there is no pattern in the last digits of specific primes, but if we look at pairs of consecutive primes, we find something quite interesting.

There are only three primes ending in a 1 followed by another prime ending in a 1 below 1,000 (241, 421, 811), but there are 10 pairs of primes below 1000 that consist of a prime ending in a 1 followed by a prime ending in a 3.

An even better approximation for the prime-counting function than x/ln x is the logarithmic integral function, denoted li(x). The asymptotic ratio of π(x) to li(x) (that is, as x goes toward infinity) is 1, meaning that the logarithmic integral function gets closer to the value of π(x) as x increases.

X                         π(x)                    li(x)

10                       4                     
100                     25
1000                   168
10000                1229
100000              9592
1000000            78498
10000000         664579

The sign of π(x) – li(x) is known to change infinitely many times, but where the first sign change is on the number line is still an unsolved problem:

The prime-counting function, usually denoted with the Greek letter pi, returns the number of primes up to its input, while the logarithmic integral li(x) is the definite integral of 1/ln(x) from 2 to x. For most values of x, pi(x) < li(x). However, it was proven that the sign of pi(x) - li(x) changes infinitely many times, implying that there is some integer out there for which pi(x) is greater than li(x).

The first Skewes' number was the upper-bound for the first such integer assuming the Riemann hypothesis is true. It is exactly equal to e^(e^(e^79)). It is normally approximated at 10^(10^(10^34)), and sometimes more accurately to 10^(10^(8.852142*10^33)).

e79 = 20382810665126687668323137537172632.374...

log10(e)*e79 = 8852142197543270606106100452735038.912894...

log10(e)*e79 + log10(log10(e)) = 8852142197543270606106100452735038.550679... (about 1033.9470483)

So the number of digits in the integer part of the first Skewes' number is approximately 3.55*108852142197543270606106100452735038 (about 10^0.550679 multiplied by 108852142197543270606106100452735038). We will never know any of the digits, as it becomes impossible to calculate the first digits of nontrivial exponential numbers around 10^10^10^10, which is still much smaller than 10^10^8.852142*10^33, and with a non-integer base there is no modular exponentiation trick for the last digits of the integer part as there is for integer powers. 

Now, we will see how much larger the first Skewes' number is than a googolplex.

(10^10^100)(10^10^100) = 10^(2*10^100) = 10^10^100.3010299956... = 10^10^10^2.0013053928...

So multiplying a googolplex by itself does not get us to 10^10^10^2.002, let alone anywhere near Skewes' number. Now we will try multiplying a googolplex by itself twice, or cubing the googolplex:

(10^10^100)(10^10^100)(10^10^100) = 10^(3*10^100) = 10^10^100.4771212547... = 10^10^10^2.002067183...

Even multiplying by a googolplex again does not get us past 10^10^10^2.0025, let alone 10^10^10^33.947048. So now we will try the tenth, hundredth, thousandth, and googolth powers of the googolplex:

(10^10^100)^10 = 10^10^101 = 10^10^10^2.004321373...

(10^10^100)^100 = 10^10^102 = 10^10^10^2.008600171...

(10^10^100)^1000 = 10^10^103 = 10^10^10^2.012837224...

(10^10^100)^10^100 = 10^10^200 = 10^10^10^2.301029995...

Raising the googolplex to the googolth power still does not get us anywhere near 10^10^10^33.947048. The power that we will have to raise a googolplex to to get to approximately the first Skewes' number is: 3.55*108852142197543270606106100452734938. What?! That's barely smaller than the number of digits in Skewes' number! Well actually it is 1/10^100 of that number.

And, the power we would have to raise Skewes' number to in order to reach the common approximation of 10^10^10^34 is about 2.81*101147857802456729393893899547264961. While 10^10^10^34 doesn't seem much larger than 10^10^10^33.947048, it is actually like taking an entire universe with 10^(10^(8.8521422*10^33)) particles, and imagining a larger multiverse that is exactly identical but each particle is a universe, then an omniverse with as many such multiverses as there are particles in the Skewes' universe, and continue for 10^(1.1478578*10^33) of these steps!

The second Skewes' number is the upper bound to the same problem if the Riemann hypothesis is false. It is commonly approximated to 10^10^10^1000, or more accurately 10^10^10^963. It is actually closer to 10^(10^(10^963.5185)). 

Now, using computer calcuation, we have been able to determine that the crossover is actually around 1.397162*10316. There is no specific integer known to satisfy pi(x) > li(x), and in fact the value in this paragraph is not even known to be the first crossing. The original upper-bounds are now merely footnotes in mathematical history, which now merely serve as examples of surprisingly large numbers arising from a serious mathematical proof.

The current best bounds for where such Far Lands of pi(x) vs li(x) begin are: 1019 < x < 1.397162*10316.

The Ramanujan primes are the primes that satisfy a result proved by Srinivasa Ramanujan. The n-th Ramanujan prime is the first prime p where π(p) – π(p/2) ≥ n. The first few Ramanujan primes are 2, 11, 17, 29, 41, 47, 59, 67, 71, 97, 101, 107, 127…

This result suggests that the number of primes between n/2 and n is always increasing as we travel further along, despite the general thinning out of the primes.