ghgonnet@watdaisy.UUCP (Gaston H Gonnet) (12/03/83)
Recently someone posted a list of all the known Mersenne primes, which I did not record. Could someone mail me a copy of these? thanks in advance, Gaston.
jsgray@watrose.UUCP (Jan Gray) (09/27/85)
Someone posted that 2^216091 - 1 is a Mersenne prime. Could you also post
a list of the others?
Also, how was this Mersenne prime found? Did the discoverers try 2^p - 1
for every prime between the last Mersenne prime (M130,000 or so) and
216091? How do you prove that a 65,050 digit number is a prime?
(Answers may end up in mathNEWS, the University of Waterloo Math student
newspaper.)
Thanks very much,
Jan Gray
p.s. I have a program which will print a Mersenne prime (given p), using a
naive method (i.e. it takes 10 minutes to print M216091), if anyone
wants a fourteen page long prime number on their wall...bs@faron.UUCP (Robert D. Silverman) (10/01/85)
The exponents for the thirty known Mersenne primes are:
1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941,11213,
19937,21701,23209,44497,86243,132049,216091
A number of the form 2^p - 1 is prime iff its rank of apparition in the
sequence:
2 2
x = x - 2
n+1 n
Is p-2 where x = 4.
0
That is to say 2^p -1 is prime iff the p-2 term in the above sequence is
divisible by 2^p-1. Thus, to do the prime test one need only compute
the sequence mod 2^p - 1 and see if the p-2 term is zero. One can
compute the sequence with just multiplication and addition by noting that:
n n n
2 A + B = (2 - 1)A + B + A = B + A mod (2 - 1)
One 'merely' needs a very fast routine which will multiply 65,000 digit
numbers. I believe that Mr. Slowinski, who found the prime, uses some
sort of fast fourier transform multiplication routine.
Bob Silverman (they call me Mr.9)bs@linus.UUCP (Robert D. Silverman) (10/02/85)
> The exponents for the thirty known Mersenne primes are: > > 1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941,11213, > 19937,21701,23209,44497,86243,132049,216091 > > A number of the form 2^p - 1 is prime iff its rank of apparition in the > sequence: > > > 2 2 > x = x - 2 > n+1 n > > Is p-2 where x = 4. > 0 > > That is to say 2^p -1 is prime iff the p-2 term in the above sequence is > divisible by 2^p-1. Thus, to do the prime test one need only compute > the sequence mod 2^p - 1 and see if the p-2 term is zero. One can > compute the sequence with just multiplication and addition by noting that: > > n n n > 2 A + B = (2 - 1)A + B + A = B + A mod (2 - 1) > > One 'merely' needs a very fast routine which will multiply 65,000 digit > numbers. I believe that Mr. Slowinski, who found the prime, uses some > sort of fast fourier transform multiplication routine. > > Bob Silverman (they call me Mr.9) Sorry about the typo in the last posting: The proper prime testing sequence should be: 2 x = x - 2 n+1 n My previous posting mistakenly had an exponent 2 on the left hand side. Bob Silverman (they call me Mr. 9)
andrew@grkermi.UUCP (Andrew W. Rogers) (10/03/85)
In article <359@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >The exponents for the thirty known Mersenne primes are: > >1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941, >11213,19937,21701,23209,44497,86243,132049,216091 I count only 29. Is one missing from the above list, or is 29 the correct number? Where is this list available?
rjnoe@riccb.UUCP (Roger J. Noe) (10/04/85)
> The exponents for the thirty known Mersenne primes are: > > 1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941,11213, > 19937,21701,23209,44497,86243,132049,216091 > Bob Silverman (they call me Mr.9) I think you left out 4423 and 9689. -- Roger Noe ihnp4!riccb!rjnoe
bs@linus.UUCP (Robert D. Silverman) (10/04/85)
> In article <359@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: > >The exponents for the thirty known Mersenne primes are: > > > >1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941, > >11213,19937,21701,23209,44497,86243,132049,216091 > > I count only 29. Is one missing from the above list, or is 29 the correct > number? Where is this list available? Sorry about that: 4423 was left out Bob Silverman (they call me Mr. 9)
andrew@grkermi.UUCP (Andrew W. Rogers) (10/06/85)
In article <582@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: >> >The exponents for the thirty known Mersenne primes are: >> > >> >1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941, >> >11213,19937,21701,23209,44497,86243,132049,216091 >> >> I count only 29. Is one missing from the above list...? > >Sorry about that: 4423 was left out Knuth's _Seminumerical Algorithms_ lists 9689 2 - 1 as a Mersenne prime, too.
mtf@ark.UUCP (Mark Scheffer) (10/07/85)
In article <582@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: >> In article <359@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >> >The exponents for the thirty known Mersenne primes are: >> > >> >1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941, >> >11213,19937,21701,23209,44497,86243,132049,216091 >> >> I count only 29. Is one missing from the above list, or is 29 the correct >> number? Where is this list available? > >Sorry about that: 4423 was left out 1. I still count 29, 2^2 -1 = 1 is certainly not a prime, 1 is a unit. 2. There are 30 known Mersenne primes (85-10-07, 2:15 p.m): M9689 is also prime. 3. A list of Mersenne primes is available in almost every book on elementary number theory. Mark Scheffer. (mtf@ark.UUCP) {seismo|decvax|philabs}!mcvax!vu44!ark!mtf