home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2016   Gérard P. Michon, Ph.D.

The Set of Primes

God may not play dice with the universe, but
 something strange is going on with the prime numbers
.
Paul Erdös  (1913-1996)
 
We have reason to believe that [the sequence of the primes]
 is a mystery into which the mind will never penetrate
.
Leonhard Euler  (1707-1783)

Related articles on this site:

Related Links (Outside this Site)

Structure and randomness in the prime numbers.  by  Terence Chi-Shen Tao.
How Many Primes Are There?  by  Chris K. Caldwell.
Pseudoprimes & Probable Primes  by Jon Grantham
Proving Primality in Polynomial Time by Chris Caldwell.
Dirichlet's Theorem: A real variable approach.  by Robin Chapman.
Sloane's On-Line Encyclopedia of Integer Sequences
 
border
border

Introduction to Prime Numbers

With our order of presentation, fundamental concepts aren't used before they're introduced.  The edifice rests on greatest common divisors, Euclid's algorithm and Bézout's lemma.
 
The basic structure of the prime numbers can then be freely examined in the second part.


(2015-01-25)   Relatively prime  (or  coprime )  integers.
Two integers are  coprime  when their  greatest common divisor  is 1.

The  greatest common divisor  (GCD)  of two integers is defined as the largest positive integer that divides both of them evenly.  The  GCD  is easily computed using  Euclid's algorithm  (and/or its subtractive version).

Likewise, several integers are coprime when their only common positive divisor is  1  (French:  nombres premiers entre euxnombres étrangers ).  Such numbers need not be  pairwise coprime  (e.g., 6, 10 and 15).

Arguably, the most important fact about coprime integers is this:

If the number  d  divides   m n   and is coprime with  n,  then  d  divides  m.

Let's prove that statement:  Using  Bézout's lemma,  (itself a consequence of  Euclid's algorithm,  quoted in the above definition of  coprime numbers)  we know that there exists two integers  u  and  v  such that:

u d  +  v n   =   1

Since  d  divides  m n  it also divides the following quantity:

u d m  +  v m n   =   m ( u d  +  v n )   =   m   QED

Note that this result is crucial in the  proof of the fundamental theorem of arithmetic  given below.  (In other words, the above establishes the unicity of prime factorizations; it's not the other way around.)


(2006-11-25)   Prime Integers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 ... (A000040)

The symbol  P  denotes the set of all primes.

A positive integer  p  is said to be  prime  when it has just two distinct divisors among positive integers  (1 and p). 

Besides the number 1 (one) itself, which is not considered prime, any positive integer is thus either a prime or a composite number  (namely, the product of two lesser factors).

Two distinct prime numbers  p  and  q  are clearly  coprime  (HINT:  the set of their common divisors is the intersection of  {1,p}  and  {1,q}).  This fact implies that a prime which divides a product of distinct primes must be equal to one of them.  That's needed to prove the following important statement:


(2006-11-25)   Fundamental Theorem of Arithmetic
Every positive integer has a  unique  factorization into primes.

For example:     168   =   2 3  3  7

Such a factorization can be specified by the sequence of the exponents to which the successive primes should be raised.  In the example of 168, this is:

( 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ... )

We say that  "2  has  multiplicity  3  in  168".  The multiplicities of  3  and  7  in  168  are equal to  1.  Any other prime has multiplicity  0.
 
When discussing the prime divisors of a certain integer, it's sometimes more elegant to consider the multiplicity of a prime without assuming it's nonzero.  (On 2015-12-31, I found it convenient to formulate this way a conjecture about the prime divisors of the form  6n+1  of the  Wendt determinant  of odd order  n).

Conversely, any sequence of nonnegative integers with finitely many nonzero elements is associated with a unique positive integer.  In the factorization of the integer  1,  all exponents are zero:

( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... )

The sequence of exponents associated with the product of two positive integers is the  direct sum  of the sequences associated with those factors.

Such sequences can be represented by lists ending at the last nonzero term.  That would be the list  (3,1,0,1)  for  168  and the empty list  ( )  for  1.

Proof of the Fundamental Theorem of Arithmetic :

First, let's establish, by induction, that every integer  greater than 1  has at least one prime divisor:  Such an integer is either prime or composite.  If it's prime, we're done  (the prime divisor we're after is the number itself).  Otherwise, the number is the product of two smaller factors.  Using the  induction hypothesis, we know that either of those factors has at least one prime divisor.  As that divisor divides the original number, we're done.

Using that lemma, we can prove  (by induction)  that any positive integer  n  has a prime factorization  (i.e., it's a product of prime numbers only):

  • If  n = 1,  the factorization we seek is simply  empty.
  • Otherwise, by the above lemma, we know that  n  has a prime divisor  p.  The  induction hypothesis  tells us that the positive integer  n/p  has a prime factorization.  Combining  p  with that factorization, we obtain a prime factorization of  n.

Finally, we find that the prime factorization of a positive integer must be  unique :  Dividing repeatedly two such factorizations by any prime they have in common, we must obtain an  empty product.

Otherwise, we'd have a prime dividing a product of primes without being equal to any of them  (which contradicts the coprimality  of distinct primes).


(2006-05-25)   Euclid's Proof  [ only  nicer ]   (c. 300 BC)
There are infinitely many prime numbers.

We just have to prove the existence of a prime above  any  given prime P :

If Q is the product of all primes less than or equal to P, then any prime factor of  Q+1  can't divide  Q  and must, therefore, be a prime greater than P.  QED

This great proof is often  needlessly  presented as a proof by contradiction.

border
border
 
border
border

The Set of Prime Numbers


(2007-04-30)   Dirichlet's theorem on primes in arithmetic progressions:
If a and N are coprime, infinitely many primes are of the form  kN+a.

This statement was conjectured by Gauss  (Euler had previously stated the special case  a = 1).  It was proved by Dirichlet in 1837, using the Dirichlet characters and related L-series which he introduced for that very purpose.


(2007-04-30)   Green-Tao Theorem   (2004)
There are arbitrarily long prime arithmetic progressions (PAP).

This was proved in 2004 by Terence Tao (1975-) and Ben Green (1977-).

In 2006 (pdf), Tao and Tamar Ziegler generalized that, by showing that there are arbirarily long  polynomial  progressions of primes.  More precisely:

For any sequence of  k  integer-valued polynomials  (Q1, Q2 ... Q)  and any positive e, there are infinitely many choices of integers  x  and  m < x e  which make all expressions  x+mQi(m)  prime.

The original Green-Tao theorem corresponds to the special case  Qi(m) = i.

The existence of infinitely many arithmetic progressions of length 3 among primes was established in 1939, by the Dutch mathematician Johannes van der Corput (1890-1971).  Originally, Green and Tao wanted to prove that there are infinitely many equally spaced sequences of 4 primes, but they saw that their methods proved the existence of such sequences of any length...

Smallest Prime Arithmetic Progressions (PAP) of Given Length
AuthorLengthNPrime Numbers   a + kN
  1, 21 2, 3.
32 3, 5, 7.
4, 56 5, 11, 17, 23, 29.
G. Lemaire
(1909)
630 = 5# 7, 37, 67, 97, 127, 157.
7150 7, 157, 307, 457, 607, 757, 907.
Edward B. Escott (1910) 8, 9
10
210 = 7# 199, 409, 619, 829, 1039,
1249, 1459, 1669, 1879, 2089.
Edgar Karst
(1967)
11
12
13860
= 6 . 11#
110437, 124297, 138157, 152017,
165877, 179737, 193597, 207457,
221317, 235177, 249037, 262897.
V. N. Seredinskij
(1963)
1360060
= 2 . 13#
4943, 65003, 125063, 185123, 245183, 305243, 365303, 425363, 485423,
545483, 605543, 665603, 725663.
Paul A. Pritchard (1983) 1414 . 13# 31385539, 31805959  ...  36850999.
15138 . 13# 115453391, 119597531  ...  173471351.
Sol Weintraub
(1976-1977)
16323 . 13# 53297929, 62997619  ...  198793279.
17171 . 17# 3430751869, 3518049079 ... 4827507229
Paul A. Pritchard (1984) 181406 . 17# 4808316343   ...   17010526363
19431 . 19# 8297644387   ...   83547839407
Jeff Young &
James Fry (1987)
201943 . 19# 214861583621   ...   72945039351
Pritchard (1992) 212681 . 19# 5749146449311   ...   6269243827111

If  an arithmetic progression (AP) of k primes  starts above  k,  then its  common difference  (N)  must be a multiple of all the primes less than or equal to k  (or else, one such prime would be a proper factor of a term in the progression).  This is made explicit in the above, using the (fairly standard) notation  p#  to denote the  primorial  of  p,  namely the product of all primes between 2 and  p  (A002110).

Recent Results and New Records :

Since the record breakers are rarely found in strict order of size, we can't reliably extend the above table.  Instead, we'll just mention some newer results, starting with the first known example of 22 primes in arithmetic progression, discovered by Andrew Moran, Paul A. Pritchard and Anthony Thyssen on 1993-03-17:

11410337850553  +  4609098694200 k     (k = 0 to 21).

On 2004-07-24, Markus Frind, Paul Jobling and Paul Underwood found an arithmetic progression of 23 primes  (ending with 449924511422857) :

56211383760397  +  44546738095860 k     (k = 0 to 22).

A smaller instance  (ending with 1036239621869317)  was later found by Frind  (2006-04-01)  featuring a  common difference  N = 9523 . 23#.

403185216600637  +  2124513401010 k     (k = 0 to 22).

The first arithmetic progression of 24 primes was discovered by Jaroslaw "Jarek" Wróblewski on 2007-01-18:

468395662504823  +  k . 205619 . 23#     (k = 0 to 23).

Wróblewski and Raanan Chermoni found a PAP of length 25 on 2008-05-17:

6171054912832631  +  k . 366384 . 23#     (k = 0 to 24).

In a distributed PrimeGrid project using software written by Jaroslaw Wroblewski and Geoff Reynolds, the  Playstation 3  of Benoît Périchon  found 26 primes in arithmetic progression on 2010-04-12:

43142746595714191 + k . 23681770 . 23#     (k = 0 to 25).   A204189

The second example, discovered on 2012-03-16 by James Fry, is smaller:

3486107472997423 + k . 1666981 . 23#     (k = 0 to 25).

Consecutive Primes in Arithmetic Progression :

It's much more difficult to find  consecutive  primes in arithmetic progression.  A sequence of length 10 was first found on 1998-03-02.  Namely,  P + 210 k  (for k = 0 to 9)  with the following 93-digit value for P.

100996972469714247637786655587969840329509324689190041803603417758904341703348882159067229719

It's highly unlikely that a longer sequence (length 11) will be found any time soon, although it's conjectured that there are infinitely many instances of  k  consecutive  primes in arithmetic progression, for  any  k...

Van der Waerden theorem (1927)
Green-Tao theorem (Wikipedia)   |   PAP   |   Ten consecutive primes in arithmetic progression
Primes in Arithmetic Progression Records  (page created and maintained by  Jens Kruse Andersen).


(2009-06-26)   The von Mangoldt function  L(n)
L(n) = Log p   if  n  is a power of the prime  p.  Otherwise,  L(n) = 0

The fundamental theorem of arithmetic is essentially equivalent to the following relation, which states that the logarithm of an integer is equal to the sum of the values of the  von Mangoldt function  over all its divisors:

Log n   =    å   L(d)
  d | n  

That Dirichlet convolution can be inverted, using the Möbius function:

L (n)   =    å   m(d)  Log (n/d)   =    å   - m(d)  Log d
  d | n   d | n

The function  L  is named after Hans von Mangoldt (1854-1925)  who got his doctorate at Berlin under Weierstrass and Kummer.  He paved the way for the two proofs of the Prime number theorem (1896) by providing rigorous proofs for two statements which had only partial proofs in Riemann's 1859 seminal paper on the Zeta function.
 
In 1895, von Mangoldt proved a conjecture stated by Bernhard Riemann (1826-1866)  in 1859.  The number of roots of the zeta function with a positive imaginary part less than  2kp  is indeed:

k Log k  -  k  +  O(Log k)

Mangoldt Function  (Mathworld)
von Mangoldt function (Monday Math 95)  by  Twisted One 151


(2006-11-25)   PNT:  The Prime Number Theorem   (1896)
A random integer N is prime with a probability roughly equal to 1/ln(N).

 Carl Friedrich Gauss 
 (1777-1855)  In 1792, at age 15, Gauss made the above statement as a private conjecture in his notebook.  This is usually recast in terms of various (equivalent) approximations to the  prime counting function  which lets  p(x)  denote the number of primes below  x :

 (Normalized) Prime Counting Function

There's no controversy about the value of  p(x)  between prime values of  x.  At those points of discontinuity however, the modern convention is used  (consistent with the results of Fourier analysis)  which makes the value at a jump discontinuity equal to the half-sum of the left and right limits.  Bizarre as it may look at first, this normalization is also adopted for other counting functions, including the prime-power counting function (J)  discussed below.

p(1) = 0 ,  p(2) = 1/2p(3) = 3/2p(4) = 2 ,  p(5) = 5/2p(6) = 3 ,  ...

In terms of  Kronecker's  signum  and/or  Heaviside's  step function :

p(x)  =    å   ½  [ 1 + sgn (x-p) ]
p prime
= å H ( x-p )
p prime
This flavor of the prime counting function is what Riemann described when he introduced the concept in 1859  (in his paper, he used the symbol F for this).  That's sometimes called the  normalized  prime counting function, using a nought subscript to single it out.  However, since there's no agreement on what the  unnormalized  version should be, I recommend dropping both the qualifier and the subscript !

In 1808, Legendre proposed the following approximation, involving a parameter B  (about -1.08366)  sometimes known as  Legendre's constant.  (For  extremely  large values of N, the best value of B would be 1.)  Adrien-Marie Legendre 
 (1752-1833)

p(x)   ~   x / (B + ln x)

The aforementioned conjectural remark of the young Gauss is equivalent to equating   p(x)  and either flavor of the  logaritmic integral  li(x) or Li(x).  Gauss put it in this form in 1849  (although his remark appeared in print only posthumously, in 1863).  The resulting statement became known as the  prime number theorem (PNT).

p(x)~ li(x)   ~   Li(x)
 ~ x / ln(x)  +  x / (ln x)2  +  2x / (ln x)3  +  ...  +  k! x / (ln x)k+1  +  ...

The PNT is usually stated by retaining only the leading term  x/ln(x)  in the above asymptotic development of the  logarithmic integral  (although a better approximation would be obtained by retaining the first 3 terms).

 Charles de la Vallee-Poussin 
 (1866-1962) Baron in 1928 Two independent proofs of this famous theorem were given in 1896, by  Hadamard  and  Vallée-Poussin.  In 1951, Wiener made clear that both of those proofs rely on the established fact that the Riemann Zeta Function  z  does not have any zeroes of the form  1+it.

In 1949, a beautiful  elementary  proof of the PNT was again found by two mathematicians simultaneously: Paul Erdös and Atle Selberg.

The celebrated Riemann Hypothesis  (which states that the nontrivial zeroes of  z  are all of the form  ½+it )  is equivalent to the following statement:

p(x)   =   Li(x)  +  O(Öx ln x)   =   li(x)  +  O(Öx ln x)

Against all numerical evidence, which never shows  p(x)  above  li(x),  John E. Littlewood proved, in 1914, that the sign of  p(x)-li(x)  changes infinitely many times.  It's now known that the first such reversal of sign must happen for some number  x  with 370 digits or fewer.

np(n) li(n)n / ln(n)
2 0.51.0452.885
3 1.52.1642.730
4 2   2.9682.885
5 2.53.6353.107
10 4   5.1204.343
100 25   30.12621.715
1000 168   177.610144.765
10000 1229   1246.1371085.736
100000 9592   9629.8098685.890
1000000 78498   78627.54972382.414
10000000 664579   664918.405620420.688
100000000 5761455   5762209.3655428681.024
1000000000 50847534   50849234.95748254942.434
10000000000 455052511   455055614.587434294481.904

Prime Number Theorem  (Theorem of the Day #33)   by  Robin Whitty


(2014-07-24)   Riemann's weighted  prime power  counting function  J
Giving  partial credit  to the powers of primes.

It turns out that Euler's  Zeta function,  the undisputed Queen of analytic number theory, is directly tied with a special counting function closely related to the prime-counting function:

Instead of just counting the primes below x,  like the function p does,  the function  J  also gives a fractional score of  1/n  to the n-th power of a prime.  Since there are clearly  p ( x1/n )  such numbers below  x,  we have:

J ( x )   =   p ( x )  +  p ( x1/2 ) / 2  +  p ( x1/3 ) / 3  +  p ( x1/4 ) / 4  +  ...

J  has jump discontinuities at prime powers,  where its value is defined as the half-sum of its lower and upper limits  (to be consistent with  Fourier analysis).  The above formula can be inverted using the Möbius function  m :

p ( x )   =   J ( x )  -  J( x1/2 ) / 2  -  J( x1/3 ) / 3  + ... +   m(n)  J( x1/n ) / n  + ...

Proof :   To check this, expand the RHS using the above definition of  J:
å m å n m(n) p( x1/mn ) / mn   =   å k [ å n|k m(n) ] p( xk ) / k     (using k = mn)
The bracketed sum is a known function of k which vanishes unless k=1.   QED

J  is sometimes termed  Riemann's Jump FunctionBernhard Riemann  introduced it  (using the symbol  f  at the time)  in his famous 1859 paper on the  Zeta function,  as part of the following construction...

The paper entitled "Über die Anzahl der Primzahlen unter einer gegebenen Grösse" (Nov. 1859) is the  only one  Riemann ever wrote on the subject of the Zeta function  (z)  and/or Number Theory.  In it, he formulates the wonderful conjecture now known as the  Riemann hypothesis (RH)  but the rest of the paper doesn't depend on that.

When  Re(z) > 1,  the series are absolutely convergent and we may write:

Log  z(z)   =   å - Log ( 1-p-z )   =   åp-z + åp-2z/2 + åp-3z/3 + åp-4z/4 + ...

Riemann then substitutes every occurrence of  p-kz  with a definite integral:

   p-kz   =   z   ò  ¥    x-z-1  dx
pk

This turns the whole sum into an integral involving the above function  J :

Log  z(z)   =   z   ò  ¥   J(x)  x-z-1  dx
0

Riemann's Explicit Formula  (1859) :

Now comes the great part:  The above integral transformation would later be called a Mellin transform  (Hjalmar Mellin was only 5 years old at the time).  Riemann realized that it could be inverted to retrieve J from z.  As we already know how the prime-counting function is derived from J, this will give us an explicit way to obtain it from z...

 Come back later, we're
 still working on this one...

The sum is understood to be performed over all the zeroes of the Zeta function, taken in increasing order of magnitude  (the value of the sum depends on this order because the series isn't absolutely convergent).

Riemann Prime Counting Function(s)  by  Eric W. Weisstein  ("J" is called "f" in that article)
Wikipedia :   Explicit formulae for L-functions   |   Mellin inversion theorem


(2009-06-26)   Number of divisors of an integer  N
A large number  N  is expected to have about  Log N  divisors.

In 1838, Dirichlet evaluated the average number of divisors of all positive numbers not exceeding  N.  This involves the Euler-Mascheroni constant  g :

Log N   +   2 g   -  1     »     Log N   +   0.15443...


(2009-06-26)   On the number  w(N)  of prime factors of an integer  N
A large number  N  has about  Log Log N   prime  factors  (1917)

The number of distinct prime factors of  n  is traditionally denoted  w(n).  The function  w  (see A001221)  is an  additive  function.  That's to say:

w( ab )   =   w( a )  +  w( b )     whenever  a  and  b  are  coprime.

In 1917, G.H. Hardy and S. Ramanujan proved  w(n)  to be asymptotically equal to  Log Log n .  In 1933, Paul Turán (1910-1976) gave an innovative one-page proof of that fact, also featured in his doctoral dissertation (1934).


(2006-05-24)   The Largest Known Prime
Until a fast formula is found, the record will be broken again and again.

The  largest known prime  has very often been of the form  2n-1.  Such numbers are called Mersenne numbers and their prime values are known as  Mersenne primes  (we discuss elsewhere their history, the special form of their factors and the connection with  perfect numbers).  It's easy to see that a Mersenne number can't be prime unless the exponent (n) is itself prime.  (This happens to be also a consequence of a nice general property of integer sequences which start with 0 and 1 and obey a second-order recurrence, as we demonstrate elsewhere.)

The primality of the exponent is not sufficient.  For example, the 11th Mersenne number 2047 is the product of 23 and 89, whereas the 23rd is divisible by 47...  Nevertheless, the primality of Mersenne primes is (currently) significantly easier to establish than that of all other integers of similar magnitudes.

The gap between the Mersenne primes  2127-1  and  2521-1  was sufficiently large to allow other approaches to break the record, as documented in the table below.

This happened again between the discovery of the primality of  2216091-1  (Slowinski, 1985)  and that of  2756839-1  (Slowinski, Gage et al., 1992)  when an "Amdahl 1200" computer was used to prove the primality of the following number  (J. Brown, C. Noll, B. Parady, G. Smith, J. Smith and S. Zarantonello, 1989).

391581 ´ 2 216193 - 1

Since 1996, the scene has been dominated by the "Great Internet Mersenne Prime Search"  (GIMPS)  which has harnessed thousands of microcomputers and found  all  the latest record primes  (see GIMPS for an update).

The "Largest Known Prime", by Date  (until the dawn of the Computer Era)
WhenWhoHowExpressionDigits
January 30, 1952 Raphael M.
Robinson
SWAC 2607 - 1183
2521 - 1157
Early July 1951
(see note below)
J.C.P. Miller
D. J. Wheeler
EDSAC 180 (2127 - 1 )2 + 179
Aimé FerrierMechanical
Desk Calculator
(2148+1) / 1744
June 1951J.C.P. Miller
D. J. Wheeler
EDSAC 978 (2127 - 1) + 142
June 7, 1951 934 (2127 - 1) + 1
May-June, 1951 k (2127 - 1) + 1
for k = 696, 738, 774, 780
k (2127 - 1) + 1
for k = 114, 124, 388, 408, 498
41
1876E. LucasLucas Test 2127-139
1867Fortuné LandryTrial Division
(Optimized)
(259-1) / 17995113
1851W. Looff 1012 - 106 + 112
before 1772Leonhard Euler 231-110
1588CataldiTrial Division 219-16
217-1
Le Lasseur's Number :   The 17-digit number  13373763765986881  divides the  360th Fibonacci number.  It was the second-largest known prime when it was discovered in 1879 by the noted French amateur  Henri Le Lasseur  (Henri Le Lasseur de Ranzay, 1821-1894; also spelled "de Ranzey").  It has been argued that this number was (briefly) the largest "known" prime, as the prime status of M127 (39 digits) was supposedly not firmly established at the time.  This ain't so, unfortunately.  The heroic proof of the primality of a "general" number as large as Le Lasseur's number would have deserved a bright spot in the record books, instead of a mere footnote...  Le Lasseur's number was then the largest prime whose primality had been established by general-purpose methods.  It's more than  4000  times larger than the runner-up  3203431780337  (Landry's number, 1867).

By contrast, the Frenchman  Aimé Ferrier  officially reported his 44-digit record-breaking prime on Bastille day, July 14, 1951.  He had been working on this since May and Jeff Miller may have been aware of Ferrier's ongoing work.  According to the 1997 recollections of family member David Miller  as reported by Chris Caldwell :  "Jeff Miller went to some length to make sure Ferrier's result was not overlooked ".  Miller may well have changed his original strategy (leading to his 79-digit record) specifically to beat Ferrier's upcoming result which would have overshadowed Miller's other results (the first of which broke the 75-year old record of Lucas).  However, Miller deliberately reported  both  his own 79-digit number and Ferrier's 44-digit prime as having been discovered "in early July".  This may have been a professional courtesy to Ferrier, although a deeper enquiry (which probably never took place) may or may not have revealed that Ferrier's results came a few hours too late to enter the record book.  Giving priority to Ferrier puts both numbers in the record book and still gives credit to Miller and Wheeler for having broken the long-standing record of Lucas with the earliest of their 41-digit numbers.  Ferrier's number itself stands out as the largest prime ever discovered without the help of an electronic computer.

This healthy ambiguity ought to be strictly respected now.  This is just what D.H. Lehmer did when he summarized the  "Recent Discoveries of Large Primes"  very shortly after those events  [MTAC, 5, 36, Oct. 1951].

A machine  printed  the primality of  24253-1  before that of  24423-1.  However, a human being  (Alexander Hurwitz)  read about the latter  before  anybody knew about the former, which was thus never largest anong "known primes"  (for more details, see our presentation of Mersenne primes and perfect numbers).

Largest Known Prime by Year  (Chris Caldwell)


(2007-05-08)   The Lucas-Lehmer Test
A fast way to check the primality of the  pth  Mersenne number   2p-1.

The Lucas-Lehmer test is a special case of the modern way to check the primality of  n  when all the prime factors of  n+1  are known.  It boils down to a procedure devised in 1878 by Edouard Lucas (1842-1991) and streamlined by  D.H. Lehmer  (1905-1991)  in 1930:

Consider the following recursively-defined sequence, modulo  2p-1

L0  =  4         Ln+1  =  Ln2 - 2   [mod 2p-1]

For an odd prime p,  2p-1   is prime  if and only if  Lp-2  is zero.  That's all!

So, the primality of  2p-1   can be determined with just  p-2  multiplications.

The Lucas-Lehmer Test  (Theorem of the Day #127)  by Robin Whitty


(2006-05-24)   Is there a formula which gives only primes?
What's a "formula" anyway?

As of this writing, checking the primality of  2p-1  for increasingly large values of the exponent  p  is the most efficient way to name large primes  (see GIMPS).

Anything faster than that would be major news.  Something  vastly  faster could essentially end the above record-breaking game by making it easy to "name" explicitely primes with so many digits that they could not possibly be written down.  This would not necessarily end the search for primes of a specific type  (like "Mersenne primes")  but it would make the title of "largest known prime" as meaningless as that of "largest known integer"  (whatever integer is named, something like "two to the power of that" will name something vastly larger).

It's not enough to have a "formula" for larger primes.  It must be an  effective  formula...  The formula discussed next isn't an effective one!

Mills' Formula :

There are  uncountably many  values of  x  for which   x3n   will  always  round down to a  prime  integer.  This was shown in 1947 by  a student of Emil Artin at Princeton:  William H. Mills (1921-2007 ?).  Mills used deep results about prime gaps which had been obtained by  Guido Hoheisel (1894-1968)  in 1930 and by Albert Ingham (1900-1967) in 1937.

Assuming the Riemann Hypothesis to be true, the  lowest  such  x  may be explicitely computed, by bracketing its powers:

  • x1, rounded down, is the lowest prime, namely 2
  • x3, rounded down, is the lowest prime between 23 and 33, namely 11
  • x9, rounded down, is the lowest prime between 113 and 123, i.e., 1361
  • x27, rounded down, is the lowest prime between 13613 and 13623, etc.

Thus, raising  x = 2.229494772491595235722852237656-  to the power of  3n  (and rounding down) only yields prime numbers, namely:

2, 11, 1361, 2521008887, 16022236204009818131831320183, etc.

One fallacy with that "etc." is that we had to prove the primality of the last value to obtain  x  with this much precision  (conversely, the precision given is barely enough to obtain this last prime number correctly).  The whole thing is merely a way to  encode  an infinite sequence of prime values into the infinitely many decimals of a real number.  It doesn't help in  constructing  such a sequence.

The other fallacy is that the iteration of the process depends on the "obvious fact" that there's always a prime between consecutive cubes.  Although the  Hoheisel-Ingham theorem  does guarantees that for  sufficiently large  cubes, it doesn't say exactly how large is  large.  Therefore, we  cannot  proceed "by inspection" for the above sequence until a putative lower bound is reached.  Currently, our only option is to assume the validity of Riemann's hypothesis and conclude on that conditional basis  (otherwise  no  satisfactory value of  x  can be established).

The above sequence is usually expressed as   A3, A9... A3n...  where  n  is a  nonzero  integer and  A  (the cube root of the above x)  is now known as  Mills' constant  (cf. A051021).  Thanks to T.D. Noe for clarifying this, on 2008-09-23  (reminding me that we attended graduate school together).

A  =  x1/3  =  1.306377883863080690468614492602605712916784585156713644368...

Using squares instead of cubes in the above would be fine if we knew that there's always a prime between consecutive squares.  If that's true, then the lowest number that truncates down to a prime when raised to the power of a 2-power is  2.3247099696648664983923017- The first primes so obtained are  2, 5, 29, 853, 727613, 529420677791  and  280286254072681840639693.  See A059784.

Mills' Theorem   |   Mills' Constant   |   Prime Formulas   |   A143935  (Noe's conjecture)


(2009-01-23)   Ulam's Lucky Numbers and Ludic Numbers
Prime-likes sequences obtained by modifying the  Sieve of Erathostenes.

The prime numbers not exceeding some integer  n  can be obtained by crossing out some of the positive integers not exceeding  n,  according to the following sieving procedure, known as the  Sieve of Eratosthenes  which was devised by Eratosthenes of Cyrene (276-194 BC).

  • Cross out the number  1  (which is not prime).
  • Circle the smallest number  p  not yet crossed out (or circled) and cross out every  pth  number thereafter  (i.e., cross out  2p, 3p, 4p, 5p, etc.)
  • Repeat the above step until all numbers in your table (up to n) is either circled or crossed.  The circled numbers are the prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499  (A000040)

In the above, we could instead cross out every  pth  number  among the subsequent numbers not yet crossed out.  In this case, we do not obtain the sequence of primes, but the so-called  ludic numbers 

2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107, 115, 119, 121, 127, 131, 143, 149, 157, 161, 173, 175, 179, 181, 193, 209, 211, 221, 223, 227, 233, 235, 239, 247, 257, 265, 277, 283, 287, 301, 307, 313, 329, 331, 337, 341, 353, 359, 361, 377, 383, 389, 397, 407, 415, 419, 421, 431, 433, 437, 445, 463, 467, 475, 481, 493, 497  (A003309)

If we start with the odd numbers and repeatedly remove every  pth  number  (counting from the very beginning of the surviving sequence)  we obtain the  [odd] lucky numbers  (French:  nombres fastes ):

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303, 307, 319, 321, 327, 331, 339, 349, 357, 361, 367, 385, 391, 393, 399, 409, 415, 421, 427, 429, 433, 451, 463, 475, 477, 483, 487, 489, 495, 511, 517, 519, 529, 535, 537, 541, 553, 559, 577, 579, 583, 591, 601, 613, 615, 619, 621, 631, 639, 643, 645, 651, 655, 673, 679, 685, 693, 699, 717, 723, 727, 729, 735, 739, 741, 745, 769, 777, 781, 787, 801, 805, 819, 823, 831, 841, 855, 867, 873, 883, 885, 895, 897, 903, 925, 927, 931, 933, 937, 957, 961, 975, 979, 981, 991, 993, 997 (A000959)

This latest process applied to the even numbers yields the even lucky numbers :

2, 4, 6, 10, 12, 18, 20, 22, 26, 34, 36, 42, 44, 50, 52, 54, 58, 68, 70, 76, 84, 90, 98, 100, 102, 108, 114, 116, 118, 130, 132, 138, 140, 148, 150, 164, 170, 172, 178, 182, 186, 196, 198, 212, 214, 218, 228, 230, 234, 244, 246, 260, 262, 268, 278, 282, 290, 298, 300, 308, 310, 314, 324, 326, 332, 346, 354, 358, 362, 372, 374, 386, 388, 390, 394, 406, 418, 420, 426, 434, 436, 438, 442, 452, 458, 470, 474, 482, 490, 498, 502, 516, 518, 522, 524, 532, 534, 546, 548, 570, 578, 586, 588, 596, 598, 602, 614, 628, 630, 642, 644, 646, 660, 666, 674, 684, 690, 706, 708, 710, 714, 716, 724, 738, 740, 742, 746, 754, 772, 778, 780, 790, 794, 804, 818, 822, 826, 838, 852, 868, 870, 874, 882, 884, 886, 900, 906, 914, 916, 922, 938, 946, 954, 962, 964, 966, 972, 982, 986, 994, 996, 998  (A045954)

With even numbers, we may also start the sieving directly with p=2, which yields:

2, 6, 10, 14, 18, 26, 30, 34, 38, 50, 54, 58, 62, 74, 78, 82, 86, 102, 106, 110, 114, 122, 126, 130, 134, 154, 158, 162, 170, 178, 182, 194, 202, 210, 222, 226, 230, 246, 250, 254, 258, 266, 270, 274, 278, 290, 298, 314, 318, 326, 338, 342, 346, 354, 370, 374, 386, 394, 398, 410, 414, 434, 438, 446, 450, 458, 466, 470, 482, 486, 494, 498, 510, 530, 534, 538, 542, 558, 562, 566, 578, 586, 594, 602, 606, 630, 634, 638, 642, 654, 658, 678, 682, 686, 690, 698, 702, 706, 722, 726, 734, 758, 770, 774, 782, 794, 798, 806, 826, 834, 842, 846, 850, 866, 878, 882, 894, 898, 902, 914, 918, 942, 946, 950, 962, 974, 978, 986, 990 ...

border
border
visits since November 25, 2006
 (c) Copyright 2000-2016, Gerard P. Michon, Ph.D.