Transcript Perfect, Prime, and Sierpinski Numbers

Perfect, Prime, and Sierpiński
Numbers
A mathematical excursion from the time of
Pythagoras to the computer age
Lane Community College
Academic Colloquium – April 9, 2009
Phil Moore
Euclid’s Elements, ~300 B.C.
Book VII, Definition 22:
“A perfect number is that which is equal to
its own parts.”
Examples:
6=3+2+1
28 = 14 + 7 + 4 + 2 + 1
Source of the concept
• Plato’s Theaetetus contains a section
indicating that the idea predates Euclid.
• Later tradition credits the Pythagoreans,
but Aristotle documents a different use by
them of the term perfect number.
• The unit fractions of the Egyptians have
also been suggested as a source:
1/2 + 1/3 + 1/6 = 1, for example.
Euclid’s Elements, Book IX,
Proposition 36
“If as many numbers as we please,
beginning from a unit be set out
continuously in double proportion, until the
sum of all becomes prime, and if the sum
multiplied into the last make some number,
the product will be perfect.”
Illustration in proof: 1 + 2 + 4 + 8 + 16 = 31
is prime, so 31 x 16 = 496 is perfect.
Euclid’s formula:
If 2 –1 is
n-1 n
prime, then 2 (2 –1) is perfect.
n
Eratosthenes, ~250 B.C.
• Showed how to systematically produce
tables of primes using a “sieve”.
• Presumably could have easily discovered
that 27-1 = 127 was prime, thus proving
that 26(27-1) = 8128 was the fourth perfect
number.
The Neo-Pythagoreans
Philo Judaeus, The Creation of the
World, (c. 30 A.D.): “It was fitting,
therefore, that the world, being the
most perfect of created things,
should be made according to the
perfect number, namely, six.”
Nicomachus, Introduction to
Arithmetic, (c. 100 A.D.)
“It comes about that even as fair and excellent things are
few and easily enumerated, while ugly and evil ones are
widespread, so also the superabundant and deficient
numbers are found in great multitude and irregularly
placed – for the method of their discovery is irregular –
but the perfect numbers are easily enumerated and
arranged with suitable order; for only one is found
among the units, 6, only one other among the tens, 28,
and a third in the rank of the hundreds, 496 alone, and a
fourth within the limits of the thousands, that is, below
ten thousand, 8128. And it is their accompanying
characteristic to end alternately in 6 or 8, and always to
be even.”
Table of factors of 2n–1, for n to 10
•
•
•
•
•
•
•
•
•
•
21 –1 = 1
22 –1 = 3
prime
23 –1 = 7
prime
24 –1 = 15 = 3 · 5
25 –1 = 31
prime
26 –1 = 63 = 3 · 3 · 7
27 –1 = 127
prime
28 –1 = 3 · 5 · 17
29 –1 = 511 = 7 · 73
210 –1 = 1023 = 3 · 11 · 31
Note: n is prime when 2n –1 is prime!
Arabic mathematicians
• Ibn al-Haytham (Alhazen, 965-1039)
attempted to show that all even perfect
numbers were of Euclid’s form.
• Ibn Fallus (1194-1252) claimed that
Euclid’s formula gave primes for n = 2, 3,
5, 7, 9, 11, 13, 17, 19, and 23.
Italians and Germans
Regiomontanus and anonymous codices
(c. 1458-1461): n = 2, 3, 5, 7, 13, 17 give
the first six perfect numbers according to
Euclid’s formula. Case of 13 was justified.
217–1 = 131,071 would have required 72
divisions to prove it prime. It was also
noted that 211–1 = 2047 was equal to
23·89 and was therefore not prime.
Cataldi (1548-1626)
Proved that n must be prime and
used a table of all primes up to 750 to
prove that n = p = 2, 3, 5, 7, 13, 17,
and 19 generate the first seven
perfect numbers. 219–1 = 524,287
required 128 divisions by all the
primes up to 719 to prove it is prime.
Pierre de Fermat (1601-1665)
• Discovered that all possible factors of
2p –1 for p prime must be of the form
2kp + 1 and found factors for p = 23,
37, and possibly 29, eliminating these
as possible perfect number
generators.
• What about p = 31?
Marin Mersenne (1588-1648)
• Claimed that 2 – 1 was prime for p = 2, 3,
5, 7, 13, 17, 19, 31, 67, 127, 257, and for
no other numbers in this range.
p
• His conjecture resulted in a prime of the
p
form 2 – 1 being named a Mersenne
prime.
Leonhard Euler (1707-1783)
•
Showed that factors of 2 – 1 must leave
a remainder of 1 or 7 upon division by 8,
which reduced the number of possible
factors by roughly half.
•
He then proved that 231 – 1 is prime by
testing all 84 possible prime factors.
p
Euler also proved that all even perfect
numbers were given by Euclid’s formula.
Descartes had said he saw no reason
that an odd perfect number could not
exist, but Euler discovered some strong
constraints on the form of any such
number.
Édouard Lucas (1842-1891)
• Invented a primality testing method for
Mersenne numbers in 1876 that did not
require testing all possible factors.
• Computed that p = 127 resulted in a
Mersenne prime.
• Computed that p = 67 resulted in a
composite, but the composite character of
267 – 1 was not considered settled until
1894.
Between 1883 and 1914, the
Mersenne primes for p = 61, 89,
and 107 were discovered,
resulting in a total of 12 known
Mersenne primes and 12 known
perfect numbers.
Derrick H. Lehmer (1905-1991)
•
Refined Lucas’ test, now known as the
Lucas-Lehmer primality test for
Mersenne numbers.
•
Lehmer and his wife, Emma Trotskaia
Lehmer, proved in 1932 that 2257 – 1, the
last number on Mersenne’s list, was
actually composite.
The Lucas-Lehmer test
•
•
•
•
•
S1 = 4
S2 = 42 – 2 = 14
S3 = 142 – 2 = 194
S4 = 1942 – 2 = 37634, etc.
For p ≥ 3 a prime, 2p – 1 is prime if and
only if Sp-1 is divisible by 2p – 1.
• Example: 25 – 1 = 31 so since S4 = 37634
is divisible by 31, 31 must be prime.
Considerations for efficient
Lucas-Lehmer testing
• The Sn grow extremely rapidly, with
roughly double the number of digits at
each iteration.
• This can be dealt with by dealing only with
the remainders: 194 ÷ 31 = 6, remainder 8,
so 82 – 2 = 62, divisible by 31.
• Multiplying or squaring numbers with
millions of digits can be done efficiently
using Fast Fourier Transforms (FFT).
Dawn of computer age
• All p up to 257 were settled.
• Max Newman and Alan Turing
tested all p up to 509 on the
University of Manchester Mark I
computer in 1951 without finding
any more Mersenne primes.
Raphael Robinson (1912-1995)
• Used the SWAC computer at UCLA
between January and October of
1952.
• Discovered 5 new Mersenne primes
for p = 521, 607, 1279, 2203, and
2281.
• Brought the total number of known
Mersenne primes to 17.
By 1996, there were 34 known
Mersenne primes, with the last
eight discoveries made on
supercomputers.
Great Internet Mersenne Prime
Search (GIMPS)
• Launched in 1996 by George
Woltman.
• Over 100,000 participants.
• Assignments coordinated by the
PrimeNet server.
• Has discovered 12 new Mersenne
primes in 13 years.
Largest known prime: 243,112,609 – 1
•
•
•
•
Discovered August 23, 2008.
Contains 12,978,189 decimal digits.
Verified using multi-processor machines.
The associated perfect number,
243,112,608(243,112,609 – 1), contains
25,956,377 digits!
• Claimed the EFF $100,000 prize for the
first proven prime of over ten million digits.
Known Mersenne prime exponents p, 2^p - 1 is prime
25
log2(p)
20
15
10
5
0
0
5
10
15
20
25
30
Mersenne prime number in order of size
35
40
45
Known Mersenne prime exponents p, 2^p - 1 is prime
25
log2(p)
20
15
10
5
0
0
5
10
15
20
25
30
Mersenne prime number in order of size
35
40
45
Odd perfect numbers?
• The question of their existence has been
called the oldest unsolved math problem.
• Must contain over 300 digits.
• Must contain at least 75 prime factors.
• Must contain at least 9 distinct prime
factors.
• Heuristic arguments suggest that none
exist, but the question is still open.
Fermat primes
• Fermat knew that for 2n +1 to be prime, n must
be a power of 2:
• 21 + 1 = 3
prime
• 22 + 1 = 5
prime
• 24 + 1 = 17
prime
• 28 + 1 = 257
prime
• 216 + 1 = 65537
prime
2m
• Fermat thought that these numbers 2 + 1 were
always prime!
WRONG!
• Euler proved in 1732 that 232 +1, the “fifth”
Fermat number, was composite:
• 232 +1 = 4,294,967,297 = 641 · 6,700,417.
• We now know that the 5th through the 32nd
Fermat numbers are all composite, as well
as over 200 larger Fermat numbers.
• Most of these numbers have been proven
composite through finding factors.
• Euler and Lagrange: Any factor of a
2m
Fermat number 2 + 1 must be of the
form k·2n + 1 where n ≥ m + 2.
• Early researchers noted that some k
n
values gave sequences of k·2 + 1 that
were rich in primes, other k values gave
sequences very sparse in primes.
Waclaw Sierpiński (1882-1969)
Proved in 1960 that there are infinitely
many positive odd integer values of k
such that k·2n + 1 is composite for
any positive integer n.
• John Selfridge proved in 1962 that k =
78557 is an example of such a Sierpiński
number, and raised the question of
whether it was the smallest.
• It can be easily proven that for all n,
n
78557·2 +1 is always divisible by at least
one number in the finite “covering set”
{3,5,7,13,19,37,73}.
Paul Erdős (1913-1996)
• Conjectured that any Sierpiński number
must have a finite covering set.
• Recent evidence indicates that his
conjecture is probably false for certain
values of k which are perfect powers.
• It is still believed that 78557 is the smallest
Sierpiński number.
The Sierpiński Problem
• For each positive odd integer k < 78557,
find a positive integer n such that k·2n+1 is
prime.
• The distributed computing project
Seventeen or Bust was started in 2002 to
work on the remaining 17 k values.
• To date, six k values are still unresolved.
The dual Sierpiński problem
•
•
•
-n
Replace n by a negative integer: k·2 +1
= (k + 2n) / 2n.
Again, 2n +78557 is always composite
with the same covering set
{3,5,7,13,19,37,73}.
Is k = 78557 the smallest positive odd
integer with this property?
Dual Sierpiński investigation:
• For each positive odd k < 78557, find an n
such that k + 2n is prime.
• Of these 39,278 values of k, a prime value
of k + 2n is known for all but 33 of them.
• For 30 of these 33 remaining k values, a
n
probable prime value of k + 2 is known.
• The three remaining sequences are being
searched by “Five or Bust”.
The largest known prime numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
number
digits
year
notes
2^43112609-1
2^37156667-1
2^32582657-1
2^30402457-1
2^25964951-1
2^24036583-1
2^20996011-1
2^13466917-1
19249*2^13018586+1
27653*2^9167433+1
28433*2^7830457+1
3661*2^7031232+1
2^6972593-1
258317*2^5450519+1
3*2^5082306+1
5359*2^5054502+1
265711*2^4858008+1
3*2^4235414-1
24518^262144+1
938237*2^3752950-1
12978189
11185272
9808358
9152052
7816230
7235733
6320430
4053946
3918990
2759677
2357207
2116617
2098960
1640776
1529928
1521561
1462412
1274988
1150678
1129757
2008
2008
2006
2005
2005
2004
2003
2001
2007
2005
2004
2007
1999
2008
2009
2003
2008
2008
2008
2007
Mersenne 46?
Mersenne 45?
Mersenne 44?
Mersenne 43?
Mersenne 42?
Mersenne 41?
Mersenne 40?
Mersenne 39
(Seventeen or Bust)
(Seventeen or Bust)
(Seventeen or Bust)
(Seventeen or Bust)
Mersenne 38
Note: All numbers on this list are of the form N±1.
(Seventeen or Bust)
Proven primes
• Proofs are easier if we know all or at least
many of the factors of N+1 or N-1.
• For large numbers which are not of such a
“special form”, methods of proof are much
more difficult.
• The largest number of general form which
has so far been proven prime has 20,562
digits.
Resolution of the Mixed Sierpiński
Problem
• Paper published by INTEGERS online journal
• Authors: Louis Helm, Phil Moore, Payam
Samidoost, and George Woltman
• Abstract: Recent progress on the Sierpiński
problem has resulted in the following theorem:
78557 is the smallest positive odd integer k such
that both k·2n+1 and k+2n are composite for any
positive integer n. An algorithmic enhancement
to the fast Fourier transform routines used in this
research is described. Prospects for the
eventual resolution of both the original and the
dual Sierpiński problems are estimated.
Probable primes
• Pass tests that all prime numbers will
pass and most composite numbers
will fail.
• Term is usually used for numbers
which are not proven primes.
• Called “industrial grade” primes in
cryptology.
Large probable primes discovered
in this dual Sierpiński investigation:
• 21191375 + 8543, discovered June 2008 at
LCC, at 358,640 digits was the record
holder until October.
• 21518191 + 75353, discovered January 4,
2009 by Five or Bust, at 457,022 digits
held the record for a short time.
• 22249255 + 28433, discovered January 26,
2009 by Five or Bust, at 677,094 digits is
the current record holder.
Fact sheet on 22249255 + 28433
• The probability that this record probable
prime is actually composite is less than
one in 10900.
• To prove that it is actually prime would
take an estimated 3 billion years.
• If the Generalized Riemann Hypothesis is
ever proven, we could prove it is prime in
just one year using 3 billion computers!
Five or Bust
• Begun in October 2008 to search the
remaining 5 sequences 2n + k.
• Sieving removes candidates divisible by a
“small” factor (now up to 150 trillion or so.)
• Each remaining candidate is subjected to
a probable prime test.
• The unsolved sequences correspond to
the values k = 2131, 40291, and 41693.
# of remaining candidates for least Sierpinski number after search of all n < 2^m
(The lower line shows the data for the dual problem.)
18
16
base 2 log(# remaining)
14
12
10
8
6
4
2
0
0
5
10
15
m
20
25
Current search limits on n for given
probabilities of solution
Probability
10%
50%
90%
Sierpiński
problem
4.1 x 109
3.4 x 1012
1.2 x 1019
Dual
problem
4.0 x 107
1.6 x 109
1.5 x 1012
What about k·2 – 1 ?
n
• Hans Riesel (1956): There are infinitely
many values of k such that k·2n – 1 is
always composite.
• One such value is k = 509203, as the
sequence 509203·2n – 1 has the covering
set {3,5,7,13,17,241}. Is 509203 the
smallest such value of k?
• Currently 64 odd values of k < 509203 are
unsettled.
What about 2 – k ?
n
• Replace n by -n again, and see that
k·2-n – 1 = (k – 2n) / 2n.
• k – 2n can be positive or negative, so take
the absolute value.
• If k = 509203, |2n – 509203| has a covering
set and is therefore always composite. Is
k = 509203 the smallest such value of k?
Current status of 2 – k
n
• All n searched up to 262,000.
• 87 values of k < 509203 are still
unresolved. Another distributed search?
• Note: 509203 is about six and a half times
larger than 78557, so the Riesel problem
and the dual Riesel problem are quite a bit
larger than the Sierpiński problem and its
dual. These problems may never be
resolved within our lifetimes!