Ernst
>Because this issue is likely of interest to Mersenne searchers, as well,
>I'm sending a copy of this to [EMAIL PROTECTED]
Much appreciated... I didn't want to do that at first because the problem I
was looking at (hunting for similar criteria for Proth numbers as for
Mersenne numbers for quick eliminations) was getting a little hairy. I
didn't want to muddy the waters on the Mersenne list with something
off-topic, but the flipside of 'why are Proths so much harder?' is 'why are
Mersennes much easier than anything else?'. The top 10 list I think is well
worth stressing!
>(these are a bit longer, but hopefully less vapid than those on the
>David Letterman show).
*grins*
>10. Mersennes have a simpler form, hence are "sexier";
I don't think you can get much sexier than 2^n-1... somehow other forms like
(b^n-1)/(b-1) or k.b^n +/- 1 lack a little something.
>9. There are less Mersenne candidates in a given size range than Proths
A *very* big one, this. Trivial exponent tests, test of 2 quadratic residue,
trial factoring limited forms to a reasonable limit quickly really do thin
out the field. (It's very hard to thin out the two-dimensional field with
Proths, three-dimensional if you generalize the 2^n to b^n).
>8. there are enough candidates in a given size range that one can easily
> recruit many volunteers to run tests, and tell them honestly that
> one of them has a very good chance of finding the next record prime.
No arguments there. Fermat numbers are for the birds. I even note that
George's program estimates my chances with my two current primes under test
at this machine at '1 in 23089'. Not bad odds at all for a shot at the first
megaprime. From some analysis I've done, the odds of a Proth number N being
prime aren't much better than 1/log N, about 1/f log N with f, dependent on
k, and about .6 for most k values. Not great.
>7. Even a child can understand the mechanics of the Lucas-Lehmer test,
> which makes participation in something like the Great Internet Mersenne
> Prime Search (GIMPS) attractive to a parent/teacher who want to foster
> their children's interest in mathematics.
Certainly something that can't be stressed enough. Encouragement of the next
generation, and non-mathematicians in the current generation, has got to be
something worthwhile. Though the Proth test has a few subtleties (such as
choosing a good candidate for a primitive root so a pseudoprimality test is
valid), the mechanics are almost as simple, but you can't get any better
than LL.
>6. Because the current world record prime is a Mersenne, one has a
> positive feedback mechanism
That's a nice one, and not one I'd given much thought. While you can't
dismiss the number of people out there who are trying to find non-Mersenne
primes (the Amdahl Six's effort springs to mind along with the other k.b^n
+-1 searchers), it has to be the case that non-Mersenne primes are currently
the playground of the few, not the many, although Yves Gallot's proth.exe is
having incredible impact.
>5. All other things being equal (which they're not), three words:
> Discrete Weighted Transform
*grin* Three words which make sure that Mersenne prime candidates are
definitely more equal than others! As I've commented on the
primes-L list, the nth roots of unity are so tightly bound into the Mersenne
testing process that the DWT is very slick indeed. Somehow, 'the nth roots
of -1/k' just doesn't have the same ring to it, and I'm pretty certain would
take the first F out of FFT...
My own suggestions for one of the next 4 has to be
4. PrimeNet, and more generally the personalities involved... a monumental
undertaking that makes all the difference.
I'm sure other list readers will come up with three more.
>None of this is meant to imply that the search for Proth primes is not
>as (or more) interesting than that for Mersennes. It's mainly my take
>on why Mersenne searching seems to have more mass appeal.
A fair point. My personal opinion is the Mersenne testing has reached the
highest watermarks very quickly, far and away dwarfing the other record
primes, being tested at (with current knowledge) has to be optimal
efficiency, so much mathematical study on them there's difficulty in finding
something new. Proth, Woodall, Cullen, Riesel, Sierpinski et al have a long
way to go to get to that stage, and they're more the domain of the
mathematician rather than the enthusiastic amateur. I work on Proth mainly
with pencil and paper. Mersennes though are a great place to spend those
idle cycles.
Chris
