Loading ...
Sorry, an error occurred while loading the content.

16144an interesting mersenne property i just found...

Expand Messages
  • Joseph Moore
    Mar 1, 2005
    • 0 Attachment
      So 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
      M_p".

      I got this result by taking the proof of the
      sufficiency of the Lucas-Lehmer test (see
      http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html)
      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
      condition.

      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...

      Joseph.



      __________________________________
      Do you Yahoo!?
      Yahoo! Sports - Sign up for Fantasy Baseball.
      http://baseball.fantasysports.yahoo.com/
    • Show all 6 messages in this topic