[... snip ...] (Interesting, but requires no comment)
> M(p) is usually the pth Mersenne number and Mp is 2^p-1 in the
> literature. Though occasionally M(p) is used as 2^p-1 on the list. It
> could cause confusion only for small p. Is M(3) 2^3-1 or 2^5-1?
>
Sorry, I'm guilty of this confusion, (though I don't think I'm alone in
this)... Properly, we should be using subscripts (M sub p for 2^p-1)
but this is a text based list.
Also there is a problem in using M(p) for the pth Mersenne prime.
Do we mean the pth numerically or the pth to be discovered?
Several of the known Mersenne primes were discovered out of
numeric sequence. Also, given that double-checking has passed
M(35) but is still quite incomplete in the gap up to 2^2976221-1, I
would consider it makes sense to use provisional names "Spence's
Number" and "Clarkson's Number" for the two known Mersenne
primes bigger than M(35) = 2^1398269-1, until double checking is
complete.
I'm also guilty of confusion between "Mersenne number" meaning a
number of the form 2^p-1 for some prime p and a prime number of
the form 2^p-1. I prefer the former definition, on the basis that (a)
"Mersenne prime" is an obvious replacement for "prime number of
the form 2^p-1", (b) some of the numbers 2^p-1 Mersenne was
interested in (surely "Mersenne numbers" if the term has _any_
meaning) turned out to be composite, despite p being prime.
> > did Lucas use his test by hand? I know he did it by
> > hand, at the very least.
>
> I don't know about Lucas. Read some of the articles in Luke's
> bibliography, it is a wonderful history. Lehmer and Uhler used desk
> calculators. Uhler made many calculations of logarithms and powers,
> see for example http://www.scruznet.com/~luke/lit/lit_019.htm
> Though poor Uhler had been doing LL-tests in the gap between M127 and
> M521.
I deliberately tested 2^31-1 using decimal hand calculation as an
exercise in arithmetic. I can see that using a board with p columns
would be a way of taking advantage of the binary nature of the
problem - in particular, it makes reducing modulo 2^p-1 easy - but
testing 2^127-1 would still take a time on account of the sheer
number of marks to be made (or beans counted, or whatever). If
you have an aptitude for doing arithmetic in octal or hexadecimal,
that would probably be most efficient.
The major problem with hand calculation is that mistakes happen.
(Imagine a computer that makes a random error with a probability
of 1% each time an instruction is executed...) I avoided wasting
time by checking each stage by "casting out nines", this detects
single digit errors, but not neccessarily multiple errors in a
calculation, or transposition errors.
>
> STL137 asks in his post if there is a test similiar to the LL test for
> numbers of the form 2^N-k where k=3,5,7,.... A primality test of the
> Lucasian type depends on the factorization of N+1, so I guess not.
> However, for some k*2^N-1 there is a primality test that uses the familiar
> S{n} = S{n-1}^2-2 differing only in the starting value S{0}. See
> Riesel, "Prime Numbers and Computer Methods of Factorization" for example.
In Knuth vol 2 (3rd ed) one of the worked examples refers to this.
(My copy is not to hand at present, so I can't give a detailed
pointer, but it's obvious enough if you follow the references to
"Lucas, Edouard" in the index)
I guess that the problem in practical implementation is that you
don't felicitously get calculation mod k*2^N-1 from the FFT unless k
happens to be 1.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
