Alex,
The group you seek always has 2^n elements. All bit combinations are
possible.
(P = 2^p-1 is "minus one" in n-bit words. 2*P is minus two, etc. up to
2^n*P which is 0. All bit patterns occur.)
Todd Sauke
>Now, I'm going to toss out an idea. I thought about this a few minutes
>after reading the previous message and I want to see if you all think its
>worthwhile or not, or whether its even correct or not.
>Here goes:
>1) If we know the last n bits of a number x, then we can (easily) determine
>the last n bits of x^2.
>2) If we know the last n bits of x^2 we can easily determine the last n bits
>of x^2 - 2.
>3) It follows by repeating this (I hope) that we can (realatively easily)
>determine the last n bits of the last number in the Lucas-Lehmer series.
>Now the slightly sketchy part (provided that was all right) . . .
>4) There are fewer than, or equal to, 2^n possible combinations of n
>terminating bits when we examine the multiples of P = 2^p - 1, i.e. the
>group {n_terminating_bits(P), n_terminating_bits(2P),
>n_terminating_bits(3P), . . . }. It is my hope that this group has fewer
>(ideally significantly fewer) than 2^n elements. That way if the last n
>bits of the last term of the Lucas-Lehmer test is a combination of bits
>which could not possibly be the final n bits of a product of P, then we know
>that the residue cannot be 0.
>Layman's example:
>any number that ends in ...34587 cannot be divisible by 25. Why? (apart
>from the obvious). Because any number that's a multiple of 25 ends in (now
>I'm looking at the group {25, 50, 75, 100, 125, 150 . . .}), 00, 25, 50, or
>75. ...34587 doesn't end with any of these.
>
>I hope I've explained myself enough that you can either take from this any
>worth which it might have, or correct the mistakes I've made. :)
>
>Alex Healy
>[EMAIL PROTECTED]
>http://www.alexhealy.net
>
><snip>
>> *) Somebody finds a way to verify the output of the LL test
>> without a complete rerun (cf. verification of digital
>signatures).
>> If this eliminates the need for double-checks, does it qualify?
>
>That sounds interesting! Of course, if we could find a _quick_ way of
>computing a few bits of the residual, we could use this as a filter
>which would remove a large proportion of the contenders - never mind
>about being a quick check on a result. I think this really _should_
>qualify for an award!
>
>Regards
>Brian Beesley
>
></snip>
>
>_________________________________________________________________
>Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
>Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
