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

2*a^a+-1 primes

Expand Messages
  • eharsh82
    HI, I am starting a new distributed computing project which is available at http://groups.yahoo.com/groups/primenumbers/files/2*a^a+-1 prime search/index.htm
    Message 1 of 11 , Sep 1 1:59 PM
    • 0 Attachment
      HI,
      I am starting a new distributed computing project which is available
      at

      http://groups.yahoo.com/groups/primenumbers/files/2*a^a+-1 prime
      search/index.htm


      Please join in!
      Thanks!
      Harsh Aggarwal
    • Paul Underwood
      ... available ... The look of your pages look familiar; lol. I got my colours from mersenneforum.org I use a yahoo database to store my table; then export it;
      Message 2 of 11 , Sep 1 2:18 PM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
        > HI,
        > I am starting a new distributed computing project which is
        available
        > at
        >
        > http://groups.yahoo.com/groups/primenumbers/files/2*a^a+-1 prime
        > search/index.htm
        >

        The look of your pages look familiar; lol.

        I got my colours from mersenneforum.org

        I use a yahoo database to store my table; then export it; run a perl
        script over the export to produce the html -- this is not very smart!
        Hopefully you won't have to do much editing of your status table html.

        Good luck with the distributed search

        Paul
      • mikeoakes2@aol.com
        ... The how long does it take heading on that page says:- ... Remember: this is not true for the larger values of a , as each test takes time proportional
        Message 3 of 11 , Sep 2 1:25 AM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, harsh@... (eharsh82) wrote:
          > I am starting a new distributed computing project which is available
          > at
          >
          > http://groups.yahoo.com/groups/primenumbers/files/2*a^a+-1 prime
          > search/index.htm
          >

          The "how long does it take" heading on that page says:-
          > About 10000 candidates can be tested on a P900 every week.

          Remember: this is not true for the larger values of "a", as each test takes
          time proportional to approximately (a*log(a))^2, and so increases quite
          rapidly with increasing a.

          So people should not reserve /too/ large ranges!

          Mike



          [Non-text portions of this message have been removed]
        • mikeoakes2@aol.com
          ... As part of my investigation of the factor structure of these numbers, I have run PFGW with -d -f200 on all values of a
          Message 4 of 11 , Sep 3 1:06 AM
          • 0 Attachment
            In a message dated 31/08/03 17:28:26 GMT Daylight Time, harsh@... writes:


            > all the known primes of this type
            >
            > 2*(1^1)+1
            > 2*(12^12)+1
            > 2*(18^18)+1
            > 2*(251^251)+1
            >
            >
            > 2*(2^2)-1
            > 2*(3^3)-1
            > 2*(357^357)-1
            > 2*(1400^1400)-1
            >
            > all these were found by me
            >
            > Harsh Aggarwal
            >

            As part of my investigation of the factor structure of these numbers, I have
            run PFGW with "-d -f200" on all values of a <= 5000, for both forms, which
            finds all factors up to about 1000000, and took about 4 Athlon-GHz-days.

            This confirmed Harsh's results above.
            And it also uncovered quite a few big PRPs.
            The following 3, only, are larger than 10000 digits and so eligible for Henri
            Lifchitz's "Top 5000 PRP" database:-

            (2*2959^2959+1)/(3*14753*148711)
            (2*3214^3214+1)/(3*11*6427)
            (2*4701^4701+1)/(17*29^2*4703*18803*122869)

            Mike


            [Non-text portions of this message have been removed]
          • mikeoakes2@aol.com
            How many primes N=2*a^a+-1 can we expect for X_0
            Message 5 of 11 , Sep 3 1:45 PM
            • 0 Attachment
              How many primes N=2*a^a+-1 can we expect for X_0 <= a <= X?

              If N was a "typical" integer of that size, the probability of its being prime
              would be 1/log(N), by the PNT.

              But N is clearly not divisible by 2, so we must multiply by 2.

              So, ignoring the complicated story of which primes can divide which of these
              numbers (see another of my posts), which can be expected to add only an
              overall multiplying factor O(1), a first guess would be:-
              count = integral{X_0 to X}dx/log(N) = integral{X_0 to X}dx/(x*log(x)+log(2))
              ~ integral{X_0 to X}d(log(x))/log(x) ~ [log(log(X))] as X => infinity.

              So first of all: this heuristic argument indicates that there are indeed
              infinitely many primes of each type.

              Putting in the numbers gives the following table:-
              X log(X) count=log(log(X))
              10 2.3026 0.834
              10^2 4.6052 1.527
              10^3 6.9078 1.933
              10^4 9.2103 2.220
              10^5 11.5129 2.443
              10^6 13.8155 2.626
              10^7 16.1181 2.780
              10^8 18.4207 2.913
              10^9 20.7233 3.031
              10^10 23.0259 3.137

              The good news: for both the "+" and "-" formulae, the number of known primes
              (a <= 5*10^3) is actually 4, which gives some confidence that the heuristics
              are on the right track, given that PNT is only very approximate for these small
              values of X, etc :-)

              The bad news: the probability for finding a new prime increases _extremely_
              slowly with X :-(

              Mike Oakes


              [Non-text portions of this message have been removed]
            • eharsh82
              I expect a prime for the + series under 35000 and for the - series under 30000 Harsh Aggarwal ... being prime ... of these ... only an ... +log(2)) ...
              Message 6 of 11 , Sep 3 6:00 PM
              • 0 Attachment
                I expect a prime for the + series under 35000
                and for the - series under 30000

                Harsh Aggarwal

                --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:
                > How many primes N=2*a^a+-1 can we expect for X_0 <= a <= X?
                >
                > If N was a "typical" integer of that size, the probability of its
                being prime
                > would be 1/log(N), by the PNT.
                >
                > But N is clearly not divisible by 2, so we must multiply by 2.
                >
                > So, ignoring the complicated story of which primes can divide which
                of these
                > numbers (see another of my posts), which can be expected to add
                only an
                > overall multiplying factor O(1), a first guess would be:-
                > count = integral{X_0 to X}dx/log(N) = integral{X_0 to X}dx/(x*log(x)
                +log(2))
                > ~ integral{X_0 to X}d(log(x))/log(x) ~ [log(log(X))] as X =>
                infinity.
                >
                > So first of all: this heuristic argument indicates that there are
                indeed
                > infinitely many primes of each type.
                >
                > Putting in the numbers gives the following table:-
                > X log(X) count=log(log(X))
                > 10 2.3026 0.834
                > 10^2 4.6052 1.527
                > 10^3 6.9078 1.933
                > 10^4 9.2103 2.220
                > 10^5 11.5129 2.443
                > 10^6 13.8155 2.626
                > 10^7 16.1181 2.780
                > 10^8 18.4207 2.913
                > 10^9 20.7233 3.031
                > 10^10 23.0259 3.137
                >
                > The good news: for both the "+" and "-" formulae, the number of
                known primes
                > (a <= 5*10^3) is actually 4, which gives some confidence that the
                heuristics
                > are on the right track, given that PNT is only very approximate for
                these small
                > values of X, etc :-)
                >
                > The bad news: the probability for finding a new prime increases
                _extremely_
                > slowly with X :-(
                >
                > Mike Oakes
                >
                >
                > [Non-text portions of this message have been removed]
              • mikeoakes2@aol.com
                ... On what grounds? (please enlighten us;-) Mike [Non-text portions of this message have been removed]
                Message 7 of 11 , Sep 4 12:59 AM
                • 0 Attachment
                  In a message dated 04/09/03 02:03:15 GMT Daylight Time, harsh@... writes:


                  > I expect a prime for the + series under 35000
                  > and for the - series under 30000
                  >

                  On what grounds?
                  (please enlighten us;-)

                  Mike


                  [Non-text portions of this message have been removed]
                • Paul Jobling
                  Mike, You said a while back that you had a proof regarding the divisiblity of properties of the primes=1 mod 4 with these numbers. Could you post it here for
                  Message 8 of 11 , Sep 4 1:16 AM
                  • 0 Attachment
                    Mike,

                    You said a while back that you had a proof regarding the divisiblity of
                    properties of the primes=1 mod 4 with these numbers. Could you post it here
                    for us at all? I for one would certainly be interested.

                    Regards,

                    Paul.



                    __________________________________________________
                    Virus checked by MessageLabs Virus Control Centre.
                  • mikeoakes2@aol.com
                    In a message dated 04/09/03 09:17:45 GMT Daylight Time, ... So there is one reader out there who is interested, after all! Let p be a prime = +1 mod 4, and N =
                    Message 9 of 11 , Sep 4 2:03 AM
                    • 0 Attachment
                      In a message dated 04/09/03 09:17:45 GMT Daylight Time,
                      Paul.Jobling@... writes:


                      > You said a while back that you had a proof regarding the divisiblity of
                      > properties of the primes=1 mod 4 with these numbers. Could you post it here
                      > for us at all? I for one would certainly be interested.
                      >

                      So there is one reader out there who is interested, after all!

                      Let p be a prime = +1 mod 4, and N = 2*a^a+1.
                      Let a = s mod p, 0 <= s <= p-1,
                      and a = t mod (p-1), 0 <= t <= p-2.

                      N = 0 mod p iff
                      2*a^a = -1 mod p,
                      i.e. a^a = (p-1)/2 mod p,
                      i.e. s^a = (p-1)/2 mod p,
                      i.e. s^t = (p-1)/2 mod p, since s^(p-1) = 1 mod p (Fermat).

                      So, for each t in [0,p-2] we are looking for solutions s in [0,p-1] of
                      s^t = (p-1)/2 mod p (1)

                      Repeating the above for the "-" case, we are looking for solutions of
                      s^t = -(p-1)/2 mod p (2)

                      If t is odd, each solution of (1) gives a solution of (2) (just change the
                      sign of s), and vice versa.
                      If t is even, s^2 = -1 has a solution (-1 is a quadratic residue for primes p
                      = +1 mod 4), so again, each solution of (1) gives a solution of (2), and vice
                      versa.

                      QED

                      Mike


                      [Non-text portions of this message have been removed]
                    • mikeoakes2@aol.com
                      As Harsh announced here a while back, there is a small coordinated search going on for primes of this form - see:
                      Message 10 of 11 , Sep 16 3:45 PM
                      • 0 Attachment
                        As Harsh announced here a while back, there is a small coordinated search
                        going on for primes of this form - see:
                        http://groups.yahoo.com/group/primenumbers/files/2%2Aa%5Ea%2B-1%20prime%20sear
                        ch/index.htm

                        so it is instructive to see how much more or less likely such numbers are to
                        be prime than "random" integers of the same size.

                        Here are the results of removing all prime factors < p_max for both the "-"
                        and "+" forms, compared with the same exercise for a set of numbers of the form
                        2*a^a+r, where the "r" values are selected randomly from the range 1<=r<=10^9.

                        A range of 20000 <= a <= 25000 was used, for all 3 cases, and the columns in
                        the following table record how many of the 5000 starting numbers remain after
                        sieving to the depth p_max:-

                        p_max "-" form "+" form "random" form
                        2*10 2734 1650 1698
                        55 2286 1367 1365
                        2*10^2 1856 1167 1198
                        2*10^3 1395 861 829
                        2*10^4 1020 675 642
                        2*10^5 592 318 479
                        2*10^6 501 247 420
                        2*10^7 431 205 ??
                        2*10^8 381 178 ??
                        2*10^9 351 156 ??

                        Phil Carmody's excellent "aagenm.exe" was used to obtain the results in the
                        2nd and 3rd columns, in about 0.8GHz-days.
                        For the final column PFGW was used, but its trial division is about 100 times
                        slower than Phil's program's, and so would have taken months to find all the
                        ?? figures.

                        It is clear that more primes are to be expected from the "-" form than either
                        from the "+" form or from a collection of "ordinary" (odd) numbers of the
                        same size.

                        The p_max=55 row is included to enable a comparison to be made with the
                        theoretical prediction from my earlier posts giving the probabilities of the "-"
                        and "+" forms being divisible by each of the primes <= 53:-

                        p_max "-" form "+" form "random" form
                        55 2221.8 1419.8 1360.9

                        where the last column is of course just 5000*(1-1/3)*(1-1/5)*...*(1-1/53).

                        Mike


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