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

Checking Large "Prime Numbers"?

Expand Messages
  • Bob Gilson
    A colleague of mine claimed the other day that 5, followed by one billion 9 s, and 6, followed by 999,999,999 zeroes, with a further last digit being 1, are
    Message 1 of 9 , May 8, 2006
    • 0 Attachment
      A colleague of mine claimed the other day that

      5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes, with a further last digit being 1, are in fact twin primes.

      How does anyone go about refuting or confirming such allegations?


      [Non-text portions of this message have been removed]
    • Andrey Kulsha
      ... Larger is divisible by 31*293*2861, smaller - by 12547*36030697 ... [Non-text portions of this message have been removed]
      Message 2 of 9 , May 8, 2006
      • 0 Attachment
        > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes, with a further last digit being 1, are in fact twin primes.
        >
        > How does anyone go about refuting or confirming such allegations?

        Larger is divisible by 31*293*2861, smaller - by 12547*36030697

        :)

        [Non-text portions of this message have been removed]
      • jbrennen
        ... Use a math package which supports modular arithmetic directly; PARI/GP is one freely available package: Then show that the first number of that pair is
        Message 3 of 9 , May 8, 2006
        • 0 Attachment
          --- Bob Gilson wrote:
          >
          > A colleague of mine claimed the other day that
          >
          > 5, followed by one billion 9's, and 6, followed by 999,999,999
          > zeroes, with a further last digit being 1, are in fact twin
          > primes.
          >
          > How does anyone go about refuting or confirming such allegations?
          >

          Use a math package which supports modular arithmetic directly;
          PARI/GP is one freely available package:

          Then show that the first number of that pair is divisible by 12547:

          (13:33) gp > 6*Mod(10,12547)^(10^9)-1
          %133 = Mod(0, 12547)

          And that the second number of the pair is divisible by 31:

          (13:36) gp > 6*Mod(10,31)^(10^9)+1
          %136 = Mod(0, 31)


          So neither number is a prime.


          In fact, any number of the form 6*10^(10^n)+1 is divisible by 31,
          for any n >= 1.
        • Richard FitzHugh
          The latter number is divisible by 31. Richard
          Message 4 of 9 , May 8, 2006
          • 0 Attachment
            The latter number is divisible by 31.

            Richard

            >From: Bob Gilson <bobgillson@...>
            >To: "primenumbers@yahoogroups.com" <primenumbers@yahoogroups.com>
            >Subject: [PrimeNumbers] Checking Large "Prime Numbers"?
            >Date: Mon, 8 May 2006 13:09:25 -0700 (PDT)
            >
            >A colleague of mine claimed the other day that
            >
            > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes,
            >with a further last digit being 1, are in fact twin primes.
            >
            > How does anyone go about refuting or confirming such allegations?
            >
            >
            >[Non-text portions of this message have been removed]
            >
          • Phil Carmody
            ... With Pari/GP in a fraction of a second: ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2 ? forprime(p=2,100000,if(test(p)==1,print(p))) 31 293 2861 12547
            Message 5 of 9 , May 8, 2006
            • 0 Attachment
              --- Bob Gilson <bobgillson@...> wrote:
              > A colleague of mine claimed the other day that
              >
              > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes, with
              > a further last digit being 1, are in fact twin primes.
              >
              > How does anyone go about refuting or confirming such allegations?

              With Pari/GP in a fraction of a second:
              ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2
              ? forprime(p=2,100000,if(test(p)==1,print(p)))
              31
              293
              2861
              12547
              time = 60 ms.

              Your colleague is a rank amateur at such claims.

              I suspect that there are as we speak only three people in the world
              (Peter Montgomery, Dave Rusin, myself) that have ever seen a proof
              of the truth or falsity of the following statement:

              3^(3^20)+4 is prime.

              Feel free to simply turn the tables on your colleague and recycle
              my example back at him. (It's not my claim, an anonymous 4th person
              made the claim but I don't believe he had any proof either way.)

              A Usenet archive should contain some clues as to the real solution.

              Phil

              () ASCII ribbon campaign () Hopeless ribbon campaign
              /\ against HTML mail /\ against gratuitous bloodshed

              [stolen with permission from Daniel B. Cristofani]

              __________________________________________________
              Do You Yahoo!?
              Tired of spam? Yahoo! Mail has the best spam protection around
              http://mail.yahoo.com
            • Alan Eliasen
              ... with ... Impressive timings! This is the only response that actually seemed to answer the original question, *how does one go about it* rather than just
              Message 6 of 9 , May 8, 2006
              • 0 Attachment
                Phil Carmody wrote:
                > --- Bob Gilson <bobgillson@...> wrote:
                > > A colleague of mine claimed the other day that
                > > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes,
                with
                > > a further last digit being 1, are in fact twin primes.
                > > How does anyone go about refuting or confirming such allegations?
                >
                > With Pari/GP in a fraction of a second:
                > ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2
                > ? forprime(p=2,100000,if(test(p)==1,print(p)))

                Impressive timings! This is the only response that actually seemed to
                answer the original question, *how does one go about it* rather than just
                enigmatically listing factors, which does not help the original poster, nor
                answer the question posed. Could you explain the mathematics behind this one
                (especially why you use the centerlift function and what it does) for those
                not familiar with Pari/GP?

                I would also be interested if the others who posted results would answer
                the original question--how one goes about testing claims like this
                (efficiently, I hope. I know how to do it several brute-force ways.) Thanks!

                --
                Alan Eliasen
                eliasen@...
                http://futureboy.us/
              • Phil Carmody
                ... Woo-woo! Brownie-points for Phil! I was thinking of answering by evaluating the expressions for the two numbers modulo 31 , which could have been a
                Message 7 of 9 , May 8, 2006
                • 0 Attachment
                  --- Alan Eliasen <eliasen@...> wrote:
                  > Phil Carmody wrote:
                  > > --- Bob Gilson <bobgillson@...> wrote:
                  > > > A colleague of mine claimed the other day that
                  > > > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes,
                  > with
                  > > > a further last digit being 1, are in fact twin primes.
                  > > > How does anyone go about refuting or confirming such allegations?
                  > >
                  > > With Pari/GP in a fraction of a second:
                  > > ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2
                  > > ? forprime(p=2,100000,if(test(p)==1,print(p)))
                  >
                  > Impressive timings! This is the only response that actually seemed to
                  > answer the original question, *how does one go about it* rather than just
                  > enigmatically listing factors, which does not help the original poster, nor
                  > answer the question posed.

                  Woo-woo! Brownie-points for Phil!

                  I was thinking of answering "by evaluating the expressions for the two numbers
                  modulo 31", which could have been a middle-ground between my useful :-) and
                  everyone else's useless :-P answers.

                  > Could you explain the mathematics behind this one
                  > (especially why you use the centerlift function and what it does) for those
                  > not familiar with Pari/GP?

                  It simply picks a distinguished member of the set of numbers == a (mod b) in
                  the range (-b/2, b/2] rather than [0,b). So rather than +1 and p-1 you'll have
                  -1 and +1. Hence the square to subsequently turn both of those into 1.

                  > I would also be interested if the others who posted results would answer
                  > the original question--how one goes about testing claims like this
                  > (efficiently, I hope. I know how to do it several brute-force ways.)
                  > Thanks!

                  Essentially, the same way as the above, I'd bet.

                  If you've been given a large number that is claimed to be prime, and it's not
                  obviously a product of hand-crafted secret numbers, then the best way to
                  counter the claim of primality is almost always to find a small factor. The
                  best way to find a small factor is to evaluate the expression for it modulo the
                  small primes in turn.

                  Phil

                  () ASCII ribbon campaign () Hopeless ribbon campaign
                  /\ against HTML mail /\ against gratuitous bloodshed

                  [stolen with permission from Daniel B. Cristofani]

                  __________________________________________________
                  Do You Yahoo!?
                  Tired of spam? Yahoo! Mail has the best spam protection around
                  http://mail.yahoo.com
                • Bob Gilson
                  Thanks to everyone for the great response - now for the joys of PARI/GP Regards Bob ... Woo-woo! Brownie-points for Phil! I was thinking of answering by
                  Message 8 of 9 , May 9, 2006
                  • 0 Attachment
                    Thanks to everyone for the great response - now for the joys of PARI/GP

                    Regards

                    Bob

                    Phil Carmody <thefatphil@...> wrote:
                    --- Alan Eliasen <eliasen@...> wrote:
                    > Phil Carmody wrote:
                    > > --- Bob Gilson <bobgillson@...> wrote:
                    > > > A colleague of mine claimed the other day that
                    > > > 5, followed by one billion 9's, and 6, followed by 999,999,999 zeroes,
                    > with
                    > > > a further last digit being 1, are in fact twin primes.
                    > > > How does anyone go about refuting or confirming such allegations?
                    > >
                    > > With Pari/GP in a fraction of a second:
                    > > ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2
                    > > ? forprime(p=2,100000,if(test(p)==1,print(p)))
                    >
                    > Impressive timings! This is the only response that actually seemed to
                    > answer the original question, *how does one go about it* rather than just
                    > enigmatically listing factors, which does not help the original poster, nor
                    > answer the question posed.

                    Woo-woo! Brownie-points for Phil!

                    I was thinking of answering "by evaluating the expressions for the two numbers
                    modulo 31", which could have been a middle-ground between my useful :-) and
                    everyone else's useless :-P answers.

                    > Could you explain the mathematics behind this one
                    > (especially why you use the centerlift function and what it does) for those
                    > not familiar with Pari/GP?

                    It simply picks a distinguished member of the set of numbers == a (mod b) in
                    the range (-b/2, b/2] rather than [0,b). So rather than +1 and p-1 you'll have
                    -1 and +1. Hence the square to subsequently turn both of those into 1.

                    > I would also be interested if the others who posted results would answer
                    > the original question--how one goes about testing claims like this
                    > (efficiently, I hope. I know how to do it several brute-force ways.)
                    > Thanks!

                    Essentially, the same way as the above, I'd bet.

                    If you've been given a large number that is claimed to be prime, and it's not
                    obviously a product of hand-crafted secret numbers, then the best way to
                    counter the claim of primality is almost always to find a small factor. The
                    best way to find a small factor is to evaluate the expression for it modulo the
                    small primes in turn.

                    Phil

                    () ASCII ribbon campaign () Hopeless ribbon campaign
                    /\ against HTML mail /\ against gratuitous bloodshed

                    [stolen with permission from Daniel B. Cristofani]

                    __________________________________________________
                    Do You Yahoo!?
                    Tired of spam? Yahoo! Mail has the best spam protection around
                    http://mail.yahoo.com


                    Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                    The Prime Pages : http://www.primepages.org/





                    SPONSORED LINKS
                    Mathematics education Mathematics and computer science Number theory

                    ---------------------------------
                    YAHOO! GROUPS LINKS


                    Visit your group "primenumbers" on the web.

                    To unsubscribe from this group, send an email to:
                    primenumbers-unsubscribe@yahoogroups.com

                    Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


                    ---------------------------------





                    [Non-text portions of this message have been removed]
                  • Thomas Hadley
                    May I add a little more explanation to Phil s Pari script for us who are still novices? We re trying to find factors of n +/- 1 where n=6*10^1000000000.
                    Message 9 of 9 , May 10, 2006
                    • 0 Attachment
                      May I add a little more explanation to Phil's Pari script for us who are
                      still novices?
                      We're trying to find factors of n +/- 1 where n=6*10^1000000000. Phil's
                      script calculates
                      n (mod p) for primes p from 2 to 100000 and then squares it. If the
                      result is 1, then n (mod p)
                      is either -1 or +1. If it is -1, p is a factor of n+1 and if n(mod p) is
                      +1, then p is a
                      factor of n-1. Squaring combined these two tests into one.

                      Here was Phil's script:

                      test(p)=centerlift(6*Mod(10,p)^1000000000)^2
                      forprime(p=2,100000,if(test(p)==1,print(p)))

                      For Pari novices, like myself, this is a good example of how to use IntMod
                      types, which
                      is what you get with the Mod(x,p) function. When you do arithmetic
                      functions on an IntMod, the
                      result is always calculated modulo p, so it never gets too big. Now,
                      10^1000000000 is too big
                      for Pari to handle, but Mod(10,p)^100000000 does not get too big. Pari
                      will do this
                      exponentiation without overflowing anything. Same with the multiply by 6.

                      An IntMod type is always in the range of 0 to p-1 (mod p), and lift()
                      converts that type to
                      an integer in that range. But centerlift( ) converts it to an integer in
                      the
                      range (-b/2, b/2], as Phil explained. p-1 is now -1, p-2 would be -2,
                      etc.

                      Phil could have made his test use lift() and then compare test(p) to 1 OR
                      p-1 which would
                      require a temp variable but eliminate needing to square. Only Phil would
                      know which
                      would be faster. Here's how that could be implemented.

                      test(p)=lift(6*Mod(10,p)^1000000000)
                      forprime(p=2,100000,temp=test(p);\
                      if(temp==1,print(p," is a factor of n-1"));\
                      if(temp==(p-1),print(p," is a factor of n+1")))

                      I had to put \ at the end of some lines -- I still don't know the rules
                      about when
                      they are necessary.

                      Hope this helps.

                      Tom Hadley

                      primenumbers@yahoogroups.com wrote on 05/09/2006 10:01:04 AM:

                      > Thanks to everyone for the great response - now for the joys of PARI/GP
                      >
                      > Regards
                      >
                      > Bob
                      >
                      > Phil Carmody <thefatphil@...> wrote:
                      > --- Alan Eliasen <eliasen@...> wrote:
                      > > Phil Carmody wrote:
                      > > > --- Bob Gilson <bobgillson@...> wrote:
                      > > > > A colleague of mine claimed the other day that
                      > > > > 5, followed by one billion 9's, and 6, followed by 999,999,999
                      zeroes,
                      > > with
                      > > > > a further last digit being 1, are in fact twin primes.
                      > > > > How does anyone go about refuting or confirming such
                      allegations?
                      > > >
                      > > > With Pari/GP in a fraction of a second:
                      > > > ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2
                      > > > ? forprime(p=2,100000,if(test(p)==1,print(p)))
                      > >
                      > > Impressive timings! This is the only response that actually seemed
                      to
                      > > answer the original question, *how does one go about it* rather than
                      just
                      > > enigmatically listing factors, which does not help the original
                      poster, nor
                      > > answer the question posed.
                      >
                      > Woo-woo! Brownie-points for Phil!
                      >
                      > I was thinking of answering "by evaluating the expressions for the two
                      numbers
                      > modulo 31", which could have been a middle-ground between my useful :-)
                      and
                      > everyone else's useless :-P answers.
                      >
                      > > Could you explain the mathematics behind this one
                      > > (especially why you use the centerlift function and what it does) for
                      those
                      > > not familiar with Pari/GP?
                      >
                      > It simply picks a distinguished member of the set of numbers == a (mod
                      b) in
                      > the range (-b/2, b/2] rather than [0,b). So rather than +1 and p-1
                      you'll have
                      > -1 and +1. Hence the square to subsequently turn both of those into 1.
                      >
                      > > I would also be interested if the others who posted results would
                      answer
                      > > the original question--how one goes about testing claims like this
                      > > (efficiently, I hope. I know how to do it several brute-force ways.)
                      > > Thanks!
                      >
                      > Essentially, the same way as the above, I'd bet.
                      >
                      > If you've been given a large number that is claimed to be prime, and
                      it's not
                      > obviously a product of hand-crafted secret numbers, then the best way to
                      > counter the claim of primality is almost always to find a small factor.
                      The
                      > best way to find a small factor is to evaluate the expression for
                      itmodulo the
                      > small primes in turn.
                      >
                      > Phil
                      >


                      [Non-text portions of this message have been removed]
                    Your message has been successfully submitted and would be delivered to recipients shortly.