16144an interesting mersenne property i just found...
- Mar 1, 2005So I was looking at the Mersenne numbers yesterday and
found a curious property: 3^(2^(p-1)) = -3 (mod 2^p -
1) if (2^p - 1) divides S(p-1).
For the sake of reference, I'm using S(1) = 4, S(n+1)
= S(n)^2 - 2. Also, by 'Mersenne number' I mean "let
p be prime, then 2^p - 1 is a Mersenne number, namely
I got this result by taking the proof of the
sufficiency of the Lucas-Lehmer test (see
and doing some squaring and modding. I haven't been
able to show (yet?) whether the property I found is a
sufficient condition for primality, but so far it
hasn't found any false positives or missed any actual
primes (tested up through 521 at the time of this
writing). It does seem to be (at least) a necessary
Of course... now that I look more closely at my code,
this test appears to be one cycle longer than the
Lucas-Lehmer test, so maybe it isn't really worth
pursuing. Hard numbers: it was 6 seconds less time to
check M_11213 (94 seconds for Lucas-Lehmer, 88 for my
method, both using algorithms written in Lisp, run
under SBCL 0.8.19 on a 566MHz Celeron), and a little
less memory too...
Do you Yahoo!?
Yahoo! Sports - Sign up for Fantasy Baseball.
- << Previous post in topic