Related Links (Outside this Site)

---

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

A positive integer  p  is said to be  prime  when it has just two divisors among positive integers  (1 and p).  The symbol    denotes the set of all primes.

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

Fundamental Theorem of Arithmetic

The  fundamental theorem of arithmetic  states that any positive integer has a  unique  factorization into primes.  For example:

168   =   2 ³  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, ... )

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.

---

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

It suffices to prove that there's at least one prime greater than 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. 

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

---

(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 result and showed that the primes include arbirarily long  polynomial  progressions.  More precisely:

For any sequence of  k  integer-valued polynomials  (Q₁, Q₂ ... Q_k )  and any positive e, there are infinitely many choices of integers  x  and  m < x ^e  which make all expressions  x+mQ_i(m)  simultaneously prime.

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

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

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

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...

Green-Tao theorem (Wikipedia)   |   PAP   |   Ten consecutive primes in arithmetic progression

---

(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

The function  L  is named after Hans von Mangoldt (1854-1925) who obtained his doctorate in 1878 at the University of Berlin, working under Karl Weierstrass (1815-1897) and Ernst Kummer (1810-1893).

The introduction of the  von Mangoldt function  paved the way for the first two proofs of the celebrated Prime Number Theorem (PNT) in 1896.

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

In 1792, at age 15, Gauss made the above statement as a private conjecture in his notebook.  This is more often stated in terms of various (asymptotically equivalent) approximations to the so-called  prime counting function  which gives the number  p(x)  of the primes that do not exceed a positive number x.

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

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

The above conjectural remark of the young Gauss would equate   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).

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 )  would be equivalent to the following statement:

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

Against all available numerical evidence, which never show  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 less.

n	p(n)
1	0
2	1
3	2
4	2
10	4
100	25
1000	168
10000	1229
100000	9592
1000000	78498
10000000	664579
100000000	5761455
1000000000	50847534
10000000000	455052511

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

---

(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  2ⁿ-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  2¹²⁷-1  and  2⁵²¹-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  2²¹⁶⁰⁹¹-1  (Slowinski, 1985)  and that of  2⁷⁵⁶⁸³⁹-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 ²¹⁶¹⁹³ - 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 17-digit number  13373763765986881  divides the  360^th 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 Sanzey).  It has even been argued that the number of Le Lasseur was (briefly) the largest "known" prime, as the prime status of M127 (39 digits) was not yet firmly established.  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 the largest prime whose primality had been established by general-purpose methods.  It was more than  4000  times larger than the runner-up  3203431780337  (Landry's number, 1867).

By contrast, the Frenchman A. 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.

We insist that 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  2⁴²⁵³-1  before that of  2⁴⁴²³-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  p^th  Mersenne number   2^p-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 by Edouard Lucas in 1878 and streamlined by D.H. Lehmer in 1930:

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

L₀  =  4         L_n+1  =  L_n² - 2   [mod 2^p-1]

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

So, the primality of  2^p-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  2^p-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   x³ⁿ   will  always  round down to a  prime  integer.  This was shown in 1947 by  William H. Mills  using 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:

• x¹, rounded down, is the lowest prime, namely 2
• x³, rounded down, is the lowest prime between 2³ and 3³, namely 11
• x⁹, rounded down, is the lowest prime between 11³ and 12³, i.e., 1361
• x²⁷, rounded down, is the lowest prime between 1361³ and 1362³, etc.

Thus, raising  x = 2.229494772491595235722852237656-  to the power of  3ⁿ  (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   A³, A⁹... A³ⁿ...  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 pointing that out, on 2008-09-23  (and for reminding me that we attended graduate school together).

A  =  x^1/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  p^th  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  p^th  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  p^th  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 ...