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

2 questions

Expand Messages
  • Ken Davis
    Hi All, 1) I know this is a moving target, but as people continue to calculate pi (3.14...) to ever increasing number of decimal places surely someone out
    Message 1 of 27 , Sep 24, 2002
    • 0 Attachment
      Hi All,
      1) I know this is a moving target, but as people continue to
      calculate pi (3.14...) to ever increasing number of decimal places
      surely someone out there must be enumerating the function pi (The
      number of primes less than n)
      So my first question is

      What is the largest number n such that pi(n) is known?

      I don't mind that the answer will have changed by the time I read the
      reply
      If no one is willing to be specific an order of magnitude will do
      (e.g 10^16)

      2) The prime community concentrates on finding larger and larger
      primes. I have a question dealing with smallest.

      What is the smallest prp?

      (By which I mean number known to be prp but beyond our current
      skills/effort to prove prime (or composite)).
      For Jon Perry's benefit (if practical) we could treat this as a game.
      Someone supply a prp (whose primality is non-trivial to determine
      (say a week of pII cpu time)) to which someone can answer with either
      a smaller example or with proof of the numbers
      primeness/compositeness thus eliminating it from contention.

      Cheers
      Ken
    • Jud McCranie
      ... I think 10^22 is the current published record. +---------------------------------------------------------+ ...
      Message 2 of 27 , Sep 24, 2002
      • 0 Attachment
        At 03:02 AM 9/25/2002 +0000, Ken Davis wrote:

        >What is the largest number n such that pi(n) is known?

        I think 10^22 is the current published record.


        +---------------------------------------------------------+
        | Jud McCranie |
        | |
        | Programming Achieved with Structure, Clarity, And Logic |
        +---------------------------------------------------------+



        [Non-text portions of this message have been removed]
      • Nathan Russell
        ... The problem with any such contest is that it can take 20 minutes to find a number, and 15 seconds to prove it PRP, that is basically impossible to prove
        Message 3 of 27 , Sep 24, 2002
        • 0 Attachment
          On Wed, 25 Sep 2002 03:02:37 -0000, Ken Davis wrote:

          >(By which I mean number known to be prp but beyond our current
          >skills/effort to prove prime (or composite)).
          >For Jon Perry's benefit (if practical) we could treat this as a game.
          >Someone supply a prp (whose primality is non-trivial to determine
          >(say a week of pII cpu time)) to which someone can answer with either
          >a smaller example or with proof of the numbers
          >primeness/compositeness thus eliminating it from contention.

          The problem with any such "contest" is that it can take 20 minutes to
          find a number, and 15 seconds to prove it PRP, that is basically
          impossible to prove prime in any reasonable length of time. However,
          the vast majority of such numbers *are* prime, and thus cannot be
          proven composite.

          Nathan
        • Ken Davis
          HI Nathan, I realised the vast majority of prp s are prime but proving them prime would also eliminate them as the smallest prp. I would think the conditions
          Message 4 of 27 , Sep 24, 2002
          • 0 Attachment
            HI Nathan,
            I realised the vast majority of prp's are prime but proving them
            prime would also eliminate them as the smallest prp.
            I would think the conditions you state would make the question ripe
            for a contest.
            If prps can be found easily but their proof of primality is beyond
            our current technical ability then stating a given prp to be the
            smallest should be fine. Eventually we should zero in to a number
            where it becomes practical to prove and then the current smallest prp
            could move both ways.
            Perhaps we can keep track of the 10 (100) smallest in the same way we
            keep track of the largest.
            Ken

            --- In primenumbers@y..., Nathan Russell <nrussell@a...> wrote:
            > On Wed, 25 Sep 2002 03:02:37 -0000, Ken Davis wrote:
            >
            > >(By which I mean number known to be prp but beyond our current
            > >skills/effort to prove prime (or composite)).
            > >For Jon Perry's benefit (if practical) we could treat this as a
            game.
            > >Someone supply a prp (whose primality is non-trivial to determine
            > >(say a week of pII cpu time)) to which someone can answer with
            either
            > >a smaller example or with proof of the numbers
            > >primeness/compositeness thus eliminating it from contention.
            >
            > The problem with any such "contest" is that it can take 20 minutes
            to
            > find a number, and 15 seconds to prove it PRP, that is basically
            > impossible to prove prime in any reasonable length of time.
            However,
            > the vast majority of such numbers *are* prime, and thus cannot be
            > proven composite.
            >
            > Nathan
          • Jack Brennen
            ... The problem here is this: you give me a PRP which is not provable within the next year. As has been pointed out, this is possible in under an hour. I
            Message 5 of 27 , Sep 24, 2002
            • 0 Attachment
              Ken Davis wrote:
              > I realised the vast majority of prp's are prime but proving them
              > prime would also eliminate them as the smallest prp.
              > I would think the conditions you state would make the question ripe
              > for a contest.
              > If prps can be found easily but their proof of primality is beyond
              > our current technical ability then stating a given prp to be the
              > smallest should be fine. Eventually we should zero in to a number
              > where it becomes practical to prove and then the current smallest prp
              > could move both ways.

              The problem here is this: you give me a PRP which is not provable
              within the next year. As has been pointed out, this is possible
              in under an hour.

              I notice your "record" (call it N). I search for the first PRP in
              the sequence N-2, N-4, N-6, ... I submit my finding as the new
              "record". This took me under an hour as well.

              And then you better my "record" and find the next smallest PRP.

              Do you see where this is going?

              Any "record smallest PRP" takes days, weeks, or years to prove
              prime, but the same "record smallest PRP" can be bettered in
              minutes.
            • Andrey Kulsha
              ... http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html ... Well, we have a lot of interesting small PRP s which are hard to be proven
              Message 6 of 27 , Sep 25, 2002
              • 0 Attachment
                > So my first question is
                >
                > What is the largest number n such that pi(n) is known?

                http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html


                > What is the smallest prp?
                >
                > (By which I mean number known to be prp but beyond our current
                > skills/effort to prove prime (or composite)).


                Well, we have a lot of interesting small PRP's which are hard to be proven prime.

                floor((pi-3)*10^6205) - would take a year to prove
                http://research.microsoft.com/~pleyland/primes/xyyx.htm - there are some week-provable, but still not proven

                and many others...

                Best,

                Andrey


                [Non-text portions of this message have been removed]
              • Carl Devore
                ... What makes this more interesting than some random 6000 digit number? Is there something especially difficult about it?
                Message 7 of 27 , Sep 25, 2002
                • 0 Attachment
                  On Wed, 25 Sep 2002, Andrey Kulsha wrote:
                  > Well, we have a lot of interesting small PRP's which are hard to be
                  > proven prime.
                  > floor((pi-3)*10^6205) - would take a year to prove

                  What makes this more interesting than some random 6000 digit number? Is
                  there something especially difficult about it?
                • jkand71
                  ... pi(4*10^22) = 783,964,159,847,056,303,858 according to: http://numbers.computation.free.fr/Constants/Primes/Pix/results.html They tried to compute
                  Message 8 of 27 , Sep 25, 2002
                  • 0 Attachment
                    --- In primenumbers@y..., "Ken Davis" <kraden@y...> wrote:
                    > What is the largest number n such that pi(n) is known?

                    pi(4*10^22) = 783,964,159,847,056,303,858 according to:
                    http://numbers.computation.free.fr/Constants/Primes/Pix/results.html
                    They tried to compute pi(10^23) and got around
                    1,925,320,391,606,818,006,727 but the computation failed.
                    Note pi(n) can be computed directly without computing all primes
                    below n.

                    > What is the smallest prp?
                    >
                    > (By which I mean number known to be prp but beyond our current
                    > skills/effort to prove prime (or composite)).

                    The biggest "general" prime is 10^5019+43157099231631693 proved by
                    Giovanni and Marco La Barbera with Primo by Marcel Martin.
                    Here "general" roughly means the prime does not have an easily
                    provable form and a general method is used. It took 13 weeks to
                    prove with ECPP as implemented by Primo.

                    I now claim the "record" for the "smallest prp":
                    10^5019+43157099231631693+1746
                    This is the smallest prp bigger than any prime proved with a general
                    method like ECPP.
                    The search took less than 2 minutes to set up and 5 minutes to run
                    (I got lucky, the expectation was around 33 minutes). The prp-test
                    of the "record" took 5 seconds.
                    With current programs my "record" can apparently only be beaten by
                    running Primo for around 13 weeks to prove a bigger prime and then
                    use an extra 33 minutes or so to find the next prp.
                    Congratulations are in order :-)

                    I agree with other responders: This record is meaningless.
                    I have attempted to put a shread of meaning into it and I think I
                    failed.

                    Would I get the pi(n)-record by finding the next prime after the
                    existing record?
                    Or even by just proving n+1 is composite?
                    This also appears meaningless, the next 1000 primes can probably be
                    found in seconds. A recognized record should be a big improvement
                    over the old, e.g. 10% higher. This should be plenty to ensure that
                    it is not worth-while to build on the old record since a faster
                    method exists to compute pi(n) directly. Actually I think 0.001%
                    improvement is enough to ensure this but I guess nobody would spend
                    a lot of time on such an improvement.
                    --
                    Jens Kruse Andersen
                  • Ken Davis
                    This brings up the crux of why I asked the question in the first place. I wanted to see what size random numbers could be practically proven to be prime.
                    Message 9 of 27 , Sep 25, 2002
                    • 0 Attachment
                      This brings up the crux of why I asked the question in the first
                      place.
                      I wanted to see what size "random" numbers could be "practically"
                      proven to be prime.

                      Nearly all the prime records are N+/-1 because theorems exist that
                      allow primality proofs if you can factorise (to a third of its digits
                      (i think)) the previous or next number.

                      Now you say floor((pi-3)*10^6205) could be proven prime within a year
                      How?

                      4361!11-5581 is is Fermat and Lucas PRP and only has 1273 digits but
                      I wouldn't have a clue how to prove it prime within a year. Can it be
                      done?

                      Plus (and I know the encryption is based on the difficulty of
                      factoring not proving primality) but I read somewhere that primality
                      wasn't actually necessary and that some of the large primes used may
                      in fact only be prps.)

                      So if I was to find a "random" prp (just a string of digits not
                      generated by any formula) up to what size would it be practical to
                      prove it prime?


                      --- In primenumbers@y..., Carl Devore <devore@m...> wrote:
                      >
                      >
                      > On Wed, 25 Sep 2002, Andrey Kulsha wrote:
                      > > Well, we have a lot of interesting small PRP's which are hard to
                      be
                      > > proven prime.
                      > > floor((pi-3)*10^6205) - would take a year to prove
                      >
                      > What makes this more interesting than some random 6000 digit
                      number? Is
                      > there something especially difficult about it?
                    • Jack Brennen
                      ... You should have just asked that then. :-) About 5000 - 6000 digits, very roughly speaking, using Marcel Martin s program Primo. As previous responses in
                      Message 10 of 27 , Sep 25, 2002
                      • 0 Attachment
                        Ken Davis wrote:
                        >
                        > This brings up the crux of why I asked the question in the first
                        > place.
                        > I wanted to see what size "random" numbers could be "practically"
                        > proven to be prime.
                        >

                        You should have just asked that then. :-)

                        About 5000 - 6000 digits, very roughly speaking, using Marcel Martin's
                        program Primo. As previous responses in this thread indicated,
                        Primo has been used to prove the primality of a "random"
                        (non-special-form) number with 5020 digits.

                        See:

                        http://www.znz.freesurf.fr/pages/primo.html

                        Be prepared to spend weeks or months to prove the primality of
                        such a large number...

                        Primo can easily do 1273 digits. Someone who uses Primo on a
                        regular basis can probably tell you how long it would take,
                        certainly it will be far far less than a year.
                      • Carl Devore
                        ... A number of the form a^k+b *IS* more interesting, with interest level increasing with decreasing a and b and increasing with k. So why do you choose Pi-3
                        Message 11 of 27 , Sep 25, 2002
                        • 0 Attachment
                          On Thu, 26 Sep 2002, Marcel Martin wrote:
                          > >What makes this more interesting than some random 6000 digit number? Is
                          > >there something especially difficult about it?
                          >
                          > They are not more interesting but there are at least two reasons to
                          > choose numbers like N = a^k + b or N = some decimals of pi or of e
                          > instead of a true random number.

                          A number of the form a^k+b *IS* more interesting, with interest level
                          increasing with decreasing a and b and increasing with k.

                          So why do you choose Pi-3 rather than just Pi?

                          > 1) A true random number will always look suspicious. I agree, this
                          > is not rational.

                          Seems rational to me. Considering the glory associated with large primes,
                          it is very rational to suspect that the numbers have been cooked up. It
                          is like any other sporting event.
                        • Carl Devore
                          ... Because I did not guess your answer. But now that you mentioned it, it seems like a very rational explanantion. Why does it seem *not* rational to you
                          Message 12 of 27 , Sep 25, 2002
                          • 0 Attachment
                            On Thu, 26 Sep 2002, Marcel Martin wrote:
                            > >> 1) A true random number will always look suspicious. I agree, this
                            > >> is not rational.
                            >
                            > >Seems rational to me. Considering the glory associated with large primes,
                            > >it is very rational to suspect that the numbers have been cooked up.
                            >
                            > Why did you ask this question then?
                            > >What makes this more interesting than some random 6000 digit number?

                            Because I did not guess your answer. But now that you
                            mentioned it, it seems like a very rational explanantion. Why does it
                            seem *not* rational to you that people would cheat?

                            > A 'cooked' number would immediately be detected just by looking at the
                            > certificate.

                            Please explain. By "cooked", I mean cheating by using a number that
                            appears random but actually has some form that makes its primality easier
                            to prove than other random primes of the same length.
                          • Carl Devore
                            ... Isn t that extremely short time a sign that the number has some special structure such that its primality is especially easy to prove? Perhaps that
                            Message 13 of 27 , Sep 25, 2002
                            • 0 Attachment
                              On Wed, 25 Sep 2002, jkand71 wrote:
                              > The biggest "general" prime is 10^5019+43157099231631693 proved by
                              > Giovanni and Marco La Barbera with Primo by Marcel Martin.
                              > Here "general" roughly means the prime does not have an easily
                              > provable form and a general method is used. It took 13 weeks to
                              > prove with ECPP as implemented by Primo.
                              >
                              > I now claim the "record" for the "smallest prp":
                              > 10^5019+43157099231631693+1746
                              > This is the smallest prp bigger than any prime proved with a general
                              > method like ECPP.
                              > The search took less than 2 minutes to set up and 5 minutes to run
                              > (I got lucky, the expectation was around 33 minutes). The prp-test
                              > of the "record" took 5 seconds.

                              Isn't that extremely short time a sign that the number has some special
                              structure such that its primality is especially easy to prove? Perhaps
                              that special structure is not known.



                              > With current programs my "record" can apparently only be beaten by
                              > running Primo for around 13 weeks to prove a bigger prime and then
                              > use an extra 33 minutes or so to find the next prp.
                              > Congratulations are in order :-)
                              >
                              > I agree with other responders: This record is meaningless.
                              > I have attempted to put a shread of meaning into it and I think I
                              > failed.
                              >
                              > Would I get the pi(n)-record by finding the next prime after the
                              > existing record?
                              > Or even by just proving n+1 is composite?
                              > This also appears meaningless, the next 1000 primes can probably be
                              > found in seconds. A recognized record should be a big improvement
                              > over the old, e.g. 10% higher. This should be plenty to ensure that
                              > it is not worth-while to build on the old record since a faster
                              > method exists to compute pi(n) directly. Actually I think 0.001%
                              > improvement is enough to ensure this but I guess nobody would spend
                              > a lot of time on such an improvement.
                              >
                            • Nathan Russell
                              ... I think on any computer you can buy new today, it would be done fairly easily in an overnight run. On my P3-600, 1000 digits takes a few hours. Nathan
                              Message 14 of 27 , Sep 25, 2002
                              • 0 Attachment
                                On Wed, 25 Sep 2002 20:09:26 -0400, Jack Brennen wrote:

                                >Primo can easily do 1273 digits. Someone who uses Primo on a
                                >regular basis can probably tell you how long it would take,
                                >certainly it will be far far less than a year.

                                I think on any computer you can buy new today, it would be done fairly
                                easily in an overnight run.

                                On my P3-600, 1000 digits takes a few hours.

                                Nathan
                              • Nathan Russell
                                On Wed, 25 Sep 2002 22:14:20 -0400 (EDT), Carl Devore ... ECPP takes roughly the same time for all primes of a given length, to the best of my knowledge. The
                                Message 15 of 27 , Sep 25, 2002
                                • 0 Attachment
                                  On Wed, 25 Sep 2002 22:14:20 -0400 (EDT), Carl Devore
                                  <devore@...> wrote:

                                  >Please explain. By "cooked", I mean cheating by using a number that
                                  >appears random but actually has some form that makes its primality easier
                                  >to prove than other random primes of the same length.

                                  ECPP takes roughly the same time for all primes of a given length, to
                                  the best of my knowledge. The numbers that take less time to prove
                                  usually do so because a whole different algorithm can be used, e.g.
                                  the N-1, N+1, or LL tests.

                                  Nathan
                                • Jack Brennen
                                  ... Running a prp-test on any 5020 digit prime will take approximately the same amount of time (5 seconds in this case), regardless of its structure or form.
                                  Message 16 of 27 , Sep 25, 2002
                                  • 0 Attachment
                                    Carl Devore wrote:
                                    > On Wed, 25 Sep 2002, jkand71 wrote:
                                    > > I now claim the "record" for the "smallest prp":
                                    > > 10^5019+43157099231631693+1746
                                    > > This is the smallest prp bigger than any prime proved with a general
                                    > > method like ECPP.
                                    > > The search took less than 2 minutes to set up and 5 minutes to run
                                    > > (I got lucky, the expectation was around 33 minutes). The prp-test
                                    > > of the "record" took 5 seconds.
                                    >
                                    > Isn't that extremely short time a sign that the number has some special
                                    > structure such that its primality is especially easy to prove? Perhaps
                                    > that special structure is not known.
                                    >

                                    Running a prp-test on any 5020 digit prime will take approximately
                                    the same amount of time (5 seconds in this case), regardless of its
                                    structure or form.

                                    The fact that 5 minutes was required rather than 33 minutes simply
                                    indicates that the prime gap of 1746 was short compared to the
                                    average gap near 10^5019, which is about 11557.
                                  • jkand71
                                    ... general ... run ... test ... special ... Perhaps ... I used Primeform/GW for the prp-testing. Any 5020-digit number, prime or composite, will take
                                    Message 17 of 27 , Sep 25, 2002
                                    • 0 Attachment
                                      --- In primenumbers@y..., Carl Devore <devore@m...> wrote:
                                      >
                                      > On Wed, 25 Sep 2002, jkand71 wrote:
                                      > > I now claim the "record" for the "smallest prp":
                                      > > 10^5019+43157099231631693+1746
                                      > > This is the smallest prp bigger than any prime proved with a
                                      general
                                      > > method like ECPP.
                                      > > The search took less than 2 minutes to set up and 5 minutes to
                                      run
                                      > > (I got lucky, the expectation was around 33 minutes). The prp-
                                      test
                                      > > of the "record" took 5 seconds.
                                      >
                                      > Isn't that extremely short time a sign that the number has some
                                      special
                                      > structure such that its primality is especially easy to prove?
                                      Perhaps
                                      > that special structure is not known.

                                      I used Primeform/GW for the prp-testing. Any 5020-digit number,
                                      prime or composite, will take practically the same time to prp-test
                                      (without trial factoring): Around 5 seconds on my PC. The time for
                                      the algorithm is simply a function of the size and independent of
                                      the specific number unlike some primality proving algorithms.
                                      I specifically mentioned the timings to show how meaningless
                                      a "record" for the smallest prp would be.
                                      If some necessarily unfair rule for a record is chosen then my idea
                                      may be the least bad.
                                      I doubt I could convince anyone to recognize me as a record-holder.
                                      I don't even recognize myself.

                                      Ken Davis wrote:
                                      > 4361!11-5581 is is Fermat and Lucas PRP and only has 1273 digits
                                      but
                                      > I wouldn't have a clue how to prove it prime within a year. Can it
                                      be
                                      > done?

                                      Primo should typically take a few hours on 1273 digits with a new
                                      PC. Someone will probably do it once it has been posted here.
                                      The biggest prime I have proven with Primo is actually 3057 pi
                                      decimals, part of pi as a concatenation of the smallest contiguous
                                      different primes:
                                      http://www.primepuzzles.net/problems/prob_018.htm
                                      I then found a 14650-digit prp which would take decades or centuries
                                      to prove with Primo if it even works on this size.
                                      With all due respect to Marcel Martin, something better has probably
                                      been developed before that. Maybe someone has even made a practical
                                      use of AKS - naah, that should have a smiley :-)
                                      --
                                      Jens Kruse Andersen
                                    • Paul Leyland
                                      ... Which is why I commend x^y+y^x as ideal test cases for primality provers. they have very short formulae, are self-evidently not cooked (raw?) and have
                                      Message 18 of 27 , Sep 26, 2002
                                      • 0 Attachment
                                        > 1) A true random number will always look suspicious. I agree, this
                                        > is not rational.
                                        >
                                        > 2) So that a record is known, it must be published. And the fact
                                        > we can compress a number as a small formula makes its publication
                                        > easier, i.e., it gives less work to prime database managers :-)

                                        Which is why I commend x^y+y^x as ideal test cases for primality provers. they have very short formulae, are self-evidently not "cooked" (raw?) and have no useful divisibility properties (known to me anyway) which makes proving them prime any easier than random numbers.

                                        Francois Morain seems to agree with me. He's using them as test cases for his ECPP program.

                                        See http://research.microsoft.com/~pleyland/primes/xyyx.htm for details.


                                        Paul
                                      • Andrey Kulsha
                                        ... This number would be on of the best of Prime Curios: http://primes.utm.edu/curios/page.php?short=14159...07021%20(547-digits) Best, Andrey [Non-text
                                        Message 19 of 27 , Sep 26, 2002
                                        • 0 Attachment
                                          > > Well, we have a lot of interesting small PRP's which are hard to be
                                          > > proven prime.
                                          > > floor((pi-3)*10^6205) - would take a year to prove
                                          >
                                          > What makes this more interesting than some random 6000 digit number? Is
                                          > there something especially difficult about it?

                                          This number would be on of the best of Prime Curios:

                                          http://primes.utm.edu/curios/page.php?short=14159...07021%20(547-digits)

                                          Best,

                                          Andrey


                                          [Non-text portions of this message have been removed]
                                        • plano9
                                          1) Which number do the most primes end in {1, 3, 7, or 9}? I m guessing 7 but does someone know? and a similar one 2) If you input a really long stream of
                                          Message 20 of 27 , Sep 25, 2004
                                          • 0 Attachment
                                            1) Which number do the most primes end in {1, 3, 7, or 9}?
                                            I'm guessing 7 but does someone know?
                                            and a similar one
                                            2) If you input a really long stream of numbers into 6n+1 and 6n-1,
                                            which would yield more prime numbers?

                                            plus my question about what a quadtratic prime sieve does differently
                                            than a normal one...

                                            Plano9
                                          • Jud McCranie
                                            ... As the numbers go to infinity, they approach the same ratio. ... As n goes to infinity, their ratio goes to 1.
                                            Message 21 of 27 , Sep 25, 2004
                                            • 0 Attachment
                                              At 06:30 PM 9/25/2004, plano9 wrote:
                                              >1) Which number do the most primes end in {1, 3, 7, or 9}?

                                              As the numbers go to infinity, they approach the same ratio.

                                              >2) If you input a really long stream of numbers into 6n+1 and 6n-1,
                                              >which would yield more prime numbers?

                                              As n goes to infinity, their ratio goes to 1.
                                            • mikeoakes2@aol.com
                                              In a message dated 25/09/2004 23:33:36 GMT Daylight Time, plano9@yahoo.com ... Counts of the number of primes
                                              Message 22 of 27 , Sep 26, 2004
                                              • 0 Attachment
                                                In a message dated 25/09/2004 23:33:36 GMT Daylight Time, plano9@...
                                                writes:

                                                > 1) Which number do the most primes end in {1, 3, 7, or 9}?
                                                > I'm guessing 7 but does someone know?
                                                > and a similar one
                                                > 2) If you input a really long stream of numbers into 6n+1 and 6n-1,
                                                > which would yield more prime numbers?
                                                >

                                                Counts of the number of primes < 10^13 of your 2 forms can be found in my
                                                NMBRTHRY post:
                                                http://listserv.nodak.edu/scripts/wa.exe?A2=ind0403&L=nmbrthry&P=2486

                                                1)
                                                [10,1]=86516370000
                                                [10,3]=86516427946
                                                [10,5]=1
                                                [10,7]=86516367790
                                                [10,9]=86516371101

                                                2)
                                                [6,1]=173032692013
                                                [6,3]=1
                                                [6,5]=173032844824

                                                -Mike Oakes


                                                [Non-text portions of this message have been removed]
                                              • James Merickel
                                                Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software.    The first
                                                Message 23 of 27 , Apr 6, 2011
                                                • 0 Attachment
                                                  Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software. 
                                                   
                                                  The first question I have is connected with an observation.  It appears that to the level of complete evaluation the numbers for any n that are sums of two disjoint products of the first n primes (such as 2*3*11+5*7 for n=5) are such that if one is randomly selected the probability of primality is consistently about 0.93^n.  I'm wondering if there is such a limiting value close to 0.93, if anyone knows, for reasonably simple heuristic reasons.
                                                   
                                                  The second question concerns PARI/GP's ispseudoprime( ) function.  As far as all I have done experimentally shows, it seems I could possibly run tests using this until 'the cows come home' without getting a false positive. Does anybody have info on the heuristic probability by size of such and know if one has ever been found?  Does anyone know exactly which pseudoprime tests exactly go into the function?  Does it seem reasonable to submit the counts by n for the first question to OEIS with a caveat this function was employed, or should it be considered overly optimistic on the function and simply withheld aside from values that have sustained stronger attack?  
                                                   
                                                  James G. Merickel

                                                  [Non-text portions of this message have been removed]
                                                • Maximilian Hasler
                                                  ad Q2: Did you try ... You should get something equivalent to http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime Maximilian
                                                  Message 24 of 27 , Apr 7, 2011
                                                  • 0 Attachment
                                                    ad Q2:
                                                    Did you try

                                                    > ?? ispseudoprime

                                                    You should get something equivalent to
                                                    http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime

                                                    Maximilian




                                                    On Wed, Apr 6, 2011 at 10:42 PM, James Merickel <merk7777777@...> wrote:
                                                    > Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software.
                                                    >  (...)
                                                    > The second question concerns PARI/GP's ispseudoprime( ) function.  As far as all I have done experimentally shows, it seems I could possibly run tests using this until 'the cows come home' without getting a false positive. Does anybody have info on the heuristic probability by size of such and know if one has ever been found?  Does anyone know exactly which pseudoprime tests exactly go into the function?  Does it seem reasonable to submit the counts by n for the first question to OEIS with a caveat this function was employed, or should it be considered overly optimistic on the function and simply withheld aside from values that have sustained stronger attack?
                                                    >
                                                    > James G. Merickel
                                                    >
                                                  • Aldrich
                                                    ... This is part of the information contained in the above reference: If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime
                                                    Message 25 of 27 , Apr 9, 2011
                                                    • 0 Attachment
                                                      --- In primenumbers@yahoogroups.com, Maximilian Hasler <maximilian.hasler@...> wrote:
                                                      >
                                                      > ad Q2:
                                                      > Did you try
                                                      >
                                                      > > ?? ispseudoprime
                                                      >
                                                      > You should get something equivalent to
                                                      > http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime
                                                      >

                                                      This is part of the information contained in the above reference:

                                                      "If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller pseudo prime for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that P^2 - 4 is not a square mod x)".

                                                      I am curious as to the nuts and bolts of applying these techniques.
                                                      Are there pages of abstract complexities that need to be computed
                                                      to get a result, or does the whole thing boil down to a few lines
                                                      of code?

                                                      Thanks a million, Max.

                                                      Aldrich
                                                    • Phil
                                                      I discussed the Baillie-Wagstaff primality checker at my blog . Here s the latest
                                                      Message 26 of 27 , Apr 12, 2011
                                                      • 0 Attachment
                                                        I discussed the Baillie-Wagstaff primality checker at my blog
                                                        <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
                                                        . Here's the latest version of source code, in Scheme, which differs
                                                        slightly from the original entry; it's more than "a few lines" of code,
                                                        but not too long:
                                                        (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
                                                        (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
                                                        e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
                                                        (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
                                                        '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
                                                        ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
                                                        1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
                                                        y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
                                                        n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
                                                        (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
                                                        ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
                                                        2) n))) ((< n a) (loop (modulo a n) n)) ((and
                                                        (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
                                                        (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
                                                        0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
                                                        (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
                                                        v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
                                                        loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
                                                        (if (= (expm a s n) 1) #t (let loop ((r r) (s s))
                                                        (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
                                                        (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
                                                        loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
                                                        v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
                                                        (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
                                                        (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
                                                        (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
                                                        n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
                                                        ((x1 (modulo (- (* a a (inverse b n)) 2) n))
                                                        (m (quotient (- n (jacobi d n)) 2)) (f
                                                        (lambda (u) (modulo (- (* u u) 2) n))) (g
                                                        (lambda (u v) (modulo (- (* u v) x1) n))))
                                                        (let-values (((xm xm1) (chain m f g 2 x1)))
                                                        (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
                                                        (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
                                                        (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
                                                        (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
                                                        (lucas-pseudo-prime? n))))))))

                                                        --- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@...> wrote:
                                                        >
                                                        >
                                                        >
                                                        >
                                                        >
                                                        >
                                                        >
                                                        >
                                                        > --- In primenumbers@yahoogroups.com, Maximilian Hasler
                                                        maximilian.hasler@ wrote:
                                                        > >
                                                        > > ad Q2:
                                                        > > Did you try
                                                        > >
                                                        > > > ?? ispseudoprime
                                                        > >
                                                        > > You should get something equivalent to
                                                        > >
                                                        http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#is\
                                                        pseudoprime
                                                        > >
                                                        >
                                                        > This is part of the information contained in the above reference:
                                                        >
                                                        > "If flag = 0, checks whether x is a
                                                        Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller
                                                        pseudo prime for base 2, followed by strong Lucas test for the sequence
                                                        (P,-1), P smallest positive integer such that P^2 - 4 is not a square
                                                        mod x)".
                                                        >
                                                        > I am curious as to the nuts and bolts of applying these techniques.
                                                        > Are there pages of abstract complexities that need to be computed
                                                        > to get a result, or does the whole thing boil down to a few lines
                                                        > of code?
                                                        >
                                                        > Thanks a million, Max.
                                                        >
                                                        > Aldrich
                                                        >



                                                        [Non-text portions of this message have been removed]
                                                      • Aldrich
                                                        ... Well, its certainly a lot more calculation than simply recording a 1 or 2 as each prime candidate in a long chain appears. PARI can check primality of
                                                        Message 27 of 27 , Apr 22, 2011
                                                        • 0 Attachment
                                                          --- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
                                                          >
                                                          > I discussed the Baillie-Wagstaff primality checker at my blog
                                                          > <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
                                                          > . Here's the latest version of source code, in Scheme, which differs
                                                          > slightly from the original entry; it's more than "a few lines" of code,
                                                          > but not too long:
                                                          > (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
                                                          > (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
                                                          > e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
                                                          > (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
                                                          > '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
                                                          > ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
                                                          > 1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
                                                          > y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
                                                          > n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
                                                          > (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
                                                          > ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
                                                          > 2) n))) ((< n a) (loop (modulo a n) n)) ((and
                                                          > (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
                                                          > (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
                                                          > 0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
                                                          > (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
                                                          > v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
                                                          > loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
                                                          > (if (= (expm a s n) 1) #t (let loop ((r r) (s s))
                                                          > (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
                                                          > (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
                                                          > loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
                                                          > v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
                                                          > (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
                                                          > (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
                                                          > (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
                                                          > n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
                                                          > ((x1 (modulo (- (* a a (inverse b n)) 2) n))
                                                          > (m (quotient (- n (jacobi d n)) 2)) (f
                                                          > (lambda (u) (modulo (- (* u u) 2) n))) (g
                                                          > (lambda (u v) (modulo (- (* u v) x1) n))))
                                                          > (let-values (((xm xm1) (chain m f g 2 x1)))
                                                          > (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
                                                          > (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
                                                          > (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
                                                          > (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
                                                          > (lucas-pseudo-prime? n))))))))
                                                          >
                                                          >

                                                          Well, its certainly a lot more calculation than simply recording
                                                          a '1' or '2' as each prime candidate in a long chain appears.
                                                          PARI can check primality of 19-20 digit integers at a rate of
                                                          about 8000/sec, according to Maximillian, so I would expect
                                                          Praxis to be a bit slower. My primitive pm2 hit 11500/sec when
                                                          I put it into a Lazarus FreePascal compiler on a Pentium4, so I
                                                          feel it has potential. I would have to seriously upgrade my
                                                          programming skills to see how far the idea can really go
                                                          however. Somebody please shoot it down - my brain hurts!
                                                          Its pretty easy to check out even if Pascal is not your bag.
                                                          Just download Lazarus and put the program from my Primemine2
                                                          posting in the source editor starting at the line 'type ='.
                                                          Piece of cake.

                                                          Aldrich
                                                        Your message has been successfully submitted and would be delivered to recipients shortly.