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

Re: [PrimeNumbers] Re: How to (trivially) tell what Mersenne a given number divides

Expand Messages
  • Kevin Acres
    Hi, Actually you need to study the numbers around that area so that you can see that the division is anomalous to what you would expect to find. It s visually
    Message 1 of 5 , Jul 1, 2004
    • 0 Attachment
      Hi,

      Actually you need to study the numbers around that area so that you can see
      that the division is anomalous to what you would expect to find. It's
      visually obvious but I don't think that I can derive a rule for it yet.

      Regards,

      Kevin.


      At 11:35 PM 1/07/2004, sambit nayak wrote:
      >Hi Kevin,
      >
      >I was testing your algorithm for the primality test. I
      >have some doubts.
      >
      >The number I tested was
      >N =
      >556158012756522140970101270050308458769458529626977.
      >
      >(Actually this is a composite number I was using so
      >that I could factor it if possible.)
      >
      >This number generated (2^1332 - 1).
      >So, by your primality test, if 1332 divides (N-1),
      >then N is prime. In this case, 1332 actually divides
      >(N-1), but the number N is not prime. (In fact,
      >N = 449818591141 *
      >1236405128000120870775846228354119184397.)
      >
      >Further, I could not factorise N using your method.
      >Here, 1332 is even, so what to do now?
      >
      >I might have erred somewhere.. Kindly check this.
      >
      >Besides, do you have a proof of why all this is
      >happening? I mean, why should any number lead to a
      >Mersenne number, and how is the number of steps
      >required to reach there related to the input number?
      >Why should the input factor the Mersenne generated?
      >Kindly bear with my curiosity (that might be
      >irritating).
      >
      >Thanks,
      >Sambit
      >
      >
      >
      >--- Kevin Acres <research@...> wrote:
      > > Hi David,
      > >
      > > First, in answer to your questions:
      > >
      > > I don't print the iteration number when I'm not
      > > doing the addition,
      > > this is why the number jumps the way that it does.
      > >
      > > The shifting of a number continues until its LSB is
      > > over a zero in the
      > > current result. Once this occurs then the addition
      > > takes place again.
      > >
      > > The method is just a form of muliplication, you just
      > > don't know what
      > > you are multiplying by when you start the process.
      > > It's a process of
      > > finding the natural periodicity of the number
      > > concerned.
      > >
      > > It also proves, in a visual way, why any given prime
      > > divides at most
      > > one mersenne. And, by extension, why any given
      > > pseudo prime divides
      > > at most one mersenne.
      > >
      > > The interesting thing is that there is an implied
      > > rule as to which
      > > numbers divide which mersennes. This rule has to do
      > > with the
      > > distribution of 1's and 0's in the binary
      > > representation of the
      > > number.
      > >
      > > I noticed that in my earlier post I had something
      > > that wasn't clear.
      > >
      > > I actually count the bits in a generated number
      > > before the division.
      > >
      > > Taking the example of 23.
      > >
      > > 23 generates a string of 11 binary 1's or 2^11 - 1.
      > >
      > > This means that 23 divides 2^11 - 1.
      > >
      > > Now the primality test (??) requires dividing the
      > > power-1 (22) by
      > > number of bits in the generated mersenne. So we have
      > > 22/11 which is a
      > > whole number. Now it is this division that
      > > instantly shows you the
      > > difference between primes and pseudoprimes. Try it
      > > on a range of
      > > numbers and you will see what I mean.
      > >
      > >
      > > Kevin.
      > >
      > >
      >
      >
      >
      >
      >
      >__________________________________
      >Do you Yahoo!?
      >New and Improved Yahoo! Mail - 100MB free storage!
      >http://promotions.yahoo.com/new_mail
      >
      >
      >
      >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      >The Prime Pages : http://www.primepages.org/
      >
      >
      >Yahoo! Groups Links
      >
      >
      >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.