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

15004-digit AP4

Expand Messages
  • mikeoakes2
    Here is a new AP4 record at 15004 digits:- (1000362700+2571033*n)*34687#+1 is prime for n=0..3 All confirmed prime with PFGW -tc Input/output statistics:-
    Message 1 of 11 , Jul 28, 2010
      Here is a new AP4 record at 15004 digits:-

      (1000362700+2571033*n)*34687#+1 is prime for n=0..3

      All confirmed prime with PFGW -tc

      Input/output statistics:-
      Numbers tested by NewPGen: 10^7
      NewPGen reduced these (by sieving to 1.8T) to: 3.7*10^6
      Numbers tested by PFGW: 1.3*10^6
      PRP's found by PFGW: 2051
      AP3's found: 661
      AP4's found: 0

      One AP4 was found by extending all the AP3's upwards.

      Run-time statistics:-
      NewPGen: 56.5 GHz-days
      PFGW: 457 GHz-days
      Pascal program to find AP's: < 1 sec

      Since the main bottleneck is the PFGW run, the Pascal program was run periodically to see what AP3's turned up, these being then extended upwards to look for an AP4.

      A week ago, I tried a new trick (influenced by some of Ken's reported procedures):-
      as about 1/3 of the NewPGen range had been PFGW'd, with 1805 PRPs found, I wrote a program to look through the 0.5*1805^2 AP2's and output the succeding AP3 term provided that both it and the following (AP4) term were in the not-yet processed region of the NewPGen-filtered candidates (and so each was about 3 times more likely than usual to be a PRP).

      This gave 105,612 candidates, which took PFGW only about a week to process, yielding 162 new PRPs, each of which was guaranteed, by construction, to produce at least one new AP3. When these PRPs were added to those already found, the number of AP3's jumped from 429 to 661, a relatively huge increase for just one week's processing.

      The trick (which could have been periodically repeated of course) paid off first time.
      I offer it FOC to my competitors!

      -Mike Oakes
    • djbroadhurst
      ... Congratulations on your heavy hash consumption :-) David (looking for a bigger AP4 in a hash-free zone)
      Message 2 of 11 , Jul 28, 2010
        --- In primeform@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > Here is a new AP4 record at 15004 digits:-
        > (1000362700+2571033*n)*34687#+1 is prime for n=0..3

        Congratulations on your heavy hash consumption :-)

        David (looking for a bigger AP4 in a hash-free zone)
      • Jens Kruse Andersen
        ... Congratulations! http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated. -- Jens Kruse Andersen
        Message 3 of 11 , Jul 28, 2010
          Mike Oakes wrote:
          > Here is a new AP4 record at 15004 digits:-
          >
          > (1000362700+2571033*n)*34687#+1 is prime for n=0..3

          Congratulations!
          http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated.

          --
          Jens Kruse Andersen
        • kraDen
          Congratulations Mike ... I assume you extended them downwards as well ... your welcome ... Where pfgw is the limiting factor I ve been known to perform some
          Message 4 of 11 , Jul 28, 2010
            Congratulations Mike
            --- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
            >
            > Here is a new AP4 record at 15004 digits:-
            >
            > (1000362700+2571033*n)*34687#+1 is prime for n=0..3
            >
            > All confirmed prime with PFGW -tc
            >
            > Input/output statistics:-
            > Numbers tested by NewPGen: 10^7
            > NewPGen reduced these (by sieving to 1.8T) to: 3.7*10^6
            > Numbers tested by PFGW: 1.3*10^6
            > PRP's found by PFGW: 2051
            > AP3's found: 661
            > AP4's found: 0
            >
            > One AP4 was found by extending all the AP3's upwards.
            I assume you extended them downwards as well
            >
            > Run-time statistics:-
            > NewPGen: 56.5 GHz-days
            > PFGW: 457 GHz-days
            > Pascal program to find AP's: < 1 sec
            >
            > Since the main bottleneck is the PFGW run, the Pascal program was run periodically to see what AP3's turned up, these being then extended upwards to look for an AP4.
            >
            > A week ago, I tried a new trick (influenced by some of Ken's reported procedures):-
            your welcome
            > as about 1/3 of the NewPGen range had been PFGW'd, with 1805 PRPs found, I wrote a program to look through the 0.5*1805^2 AP2's and output the succeeding AP3 term provided that both it and the following (AP4) term were in the not-yet processed region of the NewPGen-filtered candidates (and so each was about 3 times more likely than usual to be a PRP).
            Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
            Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
            I then run newpgen against these numbers
            Next I run an ap search again across the range of whatever prps I have but including the sieved values below and above
            This time I only look for (potential) aps of the desired length.
            I then pfgw those values which have not yet been done hoping to get a real ap.
            >
            > This gave 105,612 candidates, which took PFGW only about a week to process, yielding 162 new PRPs, each of which was guaranteed, by construction, to produce at least one new AP3. When these PRPs were added to those already found, the number of AP3's jumped from 429 to 661, a relatively huge increase for just one week's processing.
            >
            > The trick (which could have been periodically repeated of course) paid off first time.
            > I offer it FOC to my competitors!
            I tend to think of us more as collaborators in extending human knowledge ;-)
            >
            > -Mike Oakes
          • mikeoakes2
            ... How do you organise this, Ken? As I see it, NewPGen is only useful for ranges, not individual candidates. Mike
            Message 5 of 11 , Jul 29, 2010
              --- In primeform@yahoogroups.com, "kraDen" <kradenken@...> wrote:
              >
              > Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
              > Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
              > I then run newpgen against these numbers

              How do you organise this, Ken?
              As I see it, NewPGen is only useful for ranges, not individual candidates.

              Mike
            • kraDen
              ... Its fiddley involving multiple steps. Roughly In this case I would proceed as follows Output the candidates and differences of the potential ap3s in a
              Message 6 of 11 , Jul 29, 2010
                --- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
                >
                >
                >
                > --- In primeform@yahoogroups.com, "kraDen" <kradenken@> wrote:
                > >
                > > Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
                > > Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
                > > I then run newpgen against these numbers
                >
                > How do you organise this, Ken?
                > As I see it, NewPGen is only useful for ranges, not individual candidates.
                Its fiddley involving multiple steps.
                Roughly In this case I would proceed as follows
                Output the candidates and differences of the potential ap3s in a format suitable for newpgen
                After a suitable level of newpgenning I take the output, match it against the original file (with differences) to produce a second newpgen file which will now contain the potential candidates that would give the ap4s (repeat if you are after ap5s)
                After newpgenning I'd end up with a file containing lots of potential ap4s (where 2 are known prps).
                I then run a pfgw script which tests one of the potential prps (testing the second if the first is a prp)
                The multiple newpgenning greatly reduces the candidates.
                unfortunately my current (main) search is limited by my c programs ability to find aps
                cheers
                Ken
                >
                > Mike
                >
              • kraDen
                Hi Mike (and anyone else who may be interested), For your consideration. Also note that for the AP4 case each Ap2 gives you 3 chances at an Ap4. My original
                Message 7 of 11 , Jul 31, 2010
                  Hi Mike (and anyone else who may be interested),
                  For your consideration.
                  Also note that for the AP4 case each Ap2 gives you 3 chances at an Ap4.
                  My original post only deals with the up and down ap4s.
                  The 'spanned' chances can be got at via newpgen also.
                  Extend all ap2s up and down
                  output 2 files
                  one containing data suitable for newpgen
                  the other a csv containing the n value and the difference
                  run newpgen against the candidates
                  match the remaining candidates against the csv file.
                  sort the result via difference then n value (ascending)
                  extract first n values, of pairs of equal difference where second n value = first n value + 3*difference
                  output a file containing
                  first nvalue
                  difference
                  run pfgw script against file
                  if nvalue is prp then test n value +3*difference
                  if this is a prp then you have an ap4 of prps to prime test.
                  cheers
                  Ken

                  --- In primeform@yahoogroups.com, "kraDen" <kradenken@...> wrote:
                  >
                  >
                  >
                  > --- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@> wrote:
                  > >
                  > >
                  > >
                  > > --- In primeform@yahoogroups.com, "kraDen" <kradenken@> wrote:
                  > > >
                  > > > Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
                  > > > Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
                  > > > I then run newpgen against these numbers
                  > >
                  > > How do you organise this, Ken?
                  > > As I see it, NewPGen is only useful for ranges, not individual candidates.
                  > Its fiddley involving multiple steps.
                  > Roughly In this case I would proceed as follows
                  > Output the candidates and differences of the potential ap3s in a format suitable for newpgen
                  > After a suitable level of newpgenning I take the output, match it against the original file (with differences) to produce a second newpgen file which will now contain the potential candidates that would give the ap4s (repeat if you are after ap5s)
                  > After newpgenning I'd end up with a file containing lots of potential ap4s (where 2 are known prps).
                  > I then run a pfgw script which tests one of the potential prps (testing the second if the first is a prp)
                  > The multiple newpgenning greatly reduces the candidates.
                  > unfortunately my current (main) search is limited by my c programs ability to find aps
                  > cheers
                  > Ken
                  > >
                  > > Mike
                  > >
                  >
                • djbroadhurst
                  ... Here, eventually, is my reply: Calling Brillhart-Lehmer-Selfridge with factored part 31.24% 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP!
                  Message 8 of 11 , Oct 24, 2010
                    --- In primeform@yahoogroups.com,
                    "mikeoakes2" <mikeoakes2@...> wrote:

                    > Here is a new AP4 record at 15004 digits:-
                    > (1000362700+2571033*n)*34687#+1 is prime for n=0..3

                    Here, eventually, is my reply:

                    Calling Brillhart-Lehmer-Selfridge with factored part 31.24%
                    3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP! (103.0930s+0.0038s)

                    Calling Brillhart-Lehmer-Selfridge with factored part 31.40%
                    164196977*2^80001-1631979959*2^25000-1 is Lucas PRP! (99.0570s+0.0044s)

                    Calling Brillhart-Lehmer-Selfridge with factored part 99.97%
                    164196977*2^80000-1 is prime! (30.1911s+0.0057s)

                    Calling Brillhart-Lehmer-Selfridge with factored part 99.88%
                    1631979959*2^25000-1 is prime! (2.4893s+0.0047s)

                    The two largest elements of this AP4, with 24092 and 24091 digits,
                    were proven prime using the method of Konyagin and Pomerance.

                    David Broadhurst, 24 October 2010
                  • Jens Kruse Andersen
                    ... Congratulations on a large record improvement. http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated. -- Jens Kruse Andersen
                    Message 9 of 11 , Oct 25, 2010
                      David Broadhurst wrote:
                      > 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP!
                      > 164196977*2^80001-1631979959*2^25000-1 is Lucas PRP!
                      > 164196977*2^80000-1 is prime!
                      > 1631979959*2^25000-1 is prime!
                      >
                      > The two largest elements of this AP4, with 24092 and 24091 digits,
                      > were proven prime using the method of Konyagin and Pomerance.

                      Congratulations on a large record improvement.
                      http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated.

                      --
                      Jens Kruse Andersen
                    • mikeoakes2
                      ... David Many congratulations on your big new record. You don t say what effort was involved. For comparison, I ve checked what numbers my hash technology
                      Message 10 of 11 , Oct 30, 2010
                        --- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                        >
                        > --- In primeform@yahoogroups.com,
                        > "mikeoakes2" <mikeoakes2@> wrote:
                        >
                        > > Here is a new AP4 record at 15004 digits:-
                        > > (1000362700+2571033*n)*34687#+1 is prime for n=0..3
                        >
                        > Here, eventually, is my reply:
                        >
                        > Calling Brillhart-Lehmer-Selfridge with factored part 31.24%
                        > 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP! (103.0930s+0.0038s)
                        >
                        > Calling Brillhart-Lehmer-Selfridge with factored part 31.40%
                        > 164196977*2^80001-1631979959*2^25000-1 is Lucas PRP! (99.0570s+0.0044s)
                        >
                        > Calling Brillhart-Lehmer-Selfridge with factored part 99.97%
                        > 164196977*2^80000-1 is prime! (30.1911s+0.0057s)
                        >
                        > Calling Brillhart-Lehmer-Selfridge with factored part 99.88%
                        > 1631979959*2^25000-1 is prime! (2.4893s+0.0047s)
                        >
                        > The two largest elements of this AP4, with 24092 and 24091 digits,
                        > were proven prime using the method of Konyagin and Pomerance.

                        David
                        Many congratulations on your big new record.

                        You don't say what effort was involved.
                        For comparison, I've checked what numbers my "hash" technology would require for a record of this size, for a "vanilla" detection algorithm, i.e. without any Ken-type extension tricks.

                        k=4 q=55793
                        M1=19890161. M2=39780323.
                        digits: 24094.885
                        score=80.718039
                        PRP'ing: 15.818496 GHz-yrs (100.00000%)
                        APk-detection: 0.000000012682880 GHz-yrs (0.000000080177533%)
                        Total: 15.818496 GHz-yrs
                        APk counts:-
                        k=1 c=6980.6133
                        k=2 c=24364481.
                        k=3 c=4275.4493
                        k=4 c=1.0003326
                        k=5 c=0.00026330492

                        Here is the output from the same program for your AP3 record:-

                        k=3 q=367453
                        M1=4077056.1 M2=8154112.1 c=1.0000511
                        digits: 159381.72
                        score=83.853401
                        PRP'ing: 163.82127 GHz-yrs (100.00000%)
                        APk-detection: 2.2318013 E-11 GHz-yrs (1.3623391 E-11%)
                        Total: 163.82127 GHz-yrs
                        APk counts:-
                        k=1 c=253.59636
                        k=2 c=32155.557
                        k=3 c=1.0000511
                        k=4 c=0.000041469329

                        I wonder how those PRP'ing estimates compare with your actual figures, and in particular, whether the AP3 record was about 10 times as burdensome? (It has a considerably higher "score".)

                        Mike
                      • djbroadhurst
                        ... I estimated the time for a Poisson mean of 1.0 at about half of that, but I m not telling just how unlucky I was, in fact :-( Please note that the cost of
                        Message 11 of 11 , Oct 30, 2010
                          --- In primeform@yahoogroups.com,
                          "mikeoakes2" <mikeoakes2@...> wrote:

                          > For comparison, I've checked what numbers my "hash"
                          > technology would require for a record of this size,
                          > for a "vanilla" detection algorithm
                          > Total: 15.818496 GHz-yrs

                          I estimated the time for a Poisson mean of 1.0
                          at about half of that, but I'm not telling
                          just how unlucky I was, in fact :-(

                          Please note that the cost of my big database of 25000-bit
                          primes is not included, since this had already been amortized
                          over several previous records, one going back to 2005:
                          http://primes.utm.edu/primes/page.php?id=73546
                          The key to my method was to recycle primes with only
                          31% of the digits of the largest member of the new AP4.
                          You can work out, from past CHG performance, how much
                          higher this recycling might take one :-)

                          > whether the AP3 record was about 10 times as burdensome?

                          Not for me, since here I merely stole the all the AP2s from
                          the public database :-)

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