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

Factorization of 10 consecutive integers > 10^500

Expand Messages
  • David Broadhurst
    Let x=13860*(10^60+1898683) N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4 then N+k is factorized for k in [0,9]. Proof:
    Message 1 of 8 , Aug 11, 2007
      Let

      x=13860*(10^60+1898683)
      N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4

      then N+k is factorized for k in [0,9].

      Proof:
      http://physics.open.ac.uk/~dbroadhu/cert/ifac10.zip

      Software used:
      GGNFS
      GMP-ECM
      Msieve
      OpenPFGW
      Pari-GP
      Primo

      Neighbouring composites:
      c470=(N-1)/(5^2*41*23689760674499*20201699120271441240691)
      c449=(N+10)/(2*3*23*449*304781745193811\
      *47370240325563932561*432893534978100829771)

      David Broadhurst
      11 August 2007
    • Jens Kruse Andersen
      ... Wow! Big congratulations on an astonishing record. ... After 5 days of the page, there are already more numbers above the 500-digit limit than I expected
      Message 2 of 8 , Aug 11, 2007
        David Broadhurst wrote:
        > x=13860*(10^60+1898683)
        > N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4
        >
        > then N+k is factorized for k in [0,9].

        Wow!
        Big congratulations on an astonishing record.
        Earlier I wrote:
        > I maintain many prime record pages manually and want a limit
        > that is unlikely to give many large submissions within a few years.

        After 5 days of the page, there are already more numbers
        above the 500-digit limit than I expected to see for years.
        http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm is updated.

        --
        Jens Kruse Andersen
      • David Broadhurst
        ... I was also astounded. I had been doing some p25 work on a sample of 1158 (potential) factorizations of 5 consecutive integers at 500 digits, based on PFGW
        Message 3 of 8 , Aug 11, 2007
          --- In primeform@yahoogroups.com, "Jens Kruse Andersen"
          <jens.k.a@...> wrote:

          > Big congratulations on an astonishing record.

          I was also astounded. I had been doing some p25 work on a
          sample of 1158 (potential) factorizations of 5 consecutive
          integers at 500 digits, based on PFGW doublets, obtained by
          running with the switches -f5000 -d for the two inner
          members of Jarek's (essentially unique?) quartic
          construction.

          I estimated the Poisson mean, mu(k), for k>8 successive
          factorizations, as

          mu(k)=(40/25)^2*1158*(k-4)*(25*exp(Euler)/500)^(k-5)

          where the first factor signified a willingness to step up to
          p40 work if 2 out of k>8 slots had not yet cracked. This
          heuristic gave mu(9)=0.93, which suggested that k=9 was
          worth trying, without increasing the size of the PFGW
          sample. (GMP-ECM is preferable to PFGW, on AMD64s running
          linux.)

          In the event, my second case with k=8 immediately gave
          k=10, with no need for p40, thanks to /two/ flukes

          N+0 = 2^2*97*p506
          N+1 = 3*19*443*p504

          at the lowly p7 level that Pari-GP was using to monitor
          possible extensions of sequences, before handing over to
          /serious/ GMP-ECM work.

          At this point I strongly suspected that there was a
          programming bug, since the chance of two free lunches at
          p7 level was merely

          (7*exp(Euler)/500)^2 = 0.06%

          But it was a case of fortune favouring the brave: morally,
          I deserved a result at k=9, eventually; happily, I got a
          result at k=10, much faster than I expected to crack k=9.

          Then there was the residual matter of factorizing 8
          algebraic cofactors with 128 digits. (Jens says that this is
          "relatively easy", but I do not know how many c128's he has
          cracked with MPQS or GNFS. My score is precisely 0, with one
          notable disaster trying to parallelize GGNFS on a c124.)

          In the event, I did not need Sean Irvines's help: the
          hardest factorization in a 128-digit cofactor was merely

          c118 = ((13860*(10^60+1898683))^2/8-1)/9106676377 = p45*p73

          with

          p45 = 612167007455266691724205830229887098156127313

          found by Chris Monico's GGNFS, which allows for parallel
          sieving and seems reasonably stable below 120 digits.

          That factorization took half a day:

          > Total sieving time: 61.39 hours. [Shared by 10 processors]
          > Total relation processing time: 0.36 hours.
          > Matrix solve time: 3.92 hours.
          > Time per square root: 0.34 hours.

          and was achieved just before the moors become dangerous:

          http://en.wikipedia.org/wiki/Glorious_Twelfth

          David
        • Jens Kruse Andersen
          ... I know the feeling of finding more than was searched. It s nice! ... Well, I didn t say what it was relative to ;-) But I have changed relatively easy to
          Message 4 of 8 , Aug 12, 2007
            David Broadhurst wrote:
            > But it was a case of fortune favouring the brave: morally,
            > I deserved a result at k=9, eventually; happily, I got a
            > result at k=10, much faster than I expected to crack k=9.

            I know the feeling of finding more than was searched. It's nice!

            > Then there was the residual matter of factorizing 8
            > algebraic cofactors with 128 digits. (Jens says that this is
            > "relatively easy", but I do not know how many c128's he has
            > cracked with MPQS or GNFS. My score is precisely 0, with one
            > notable disaster trying to parallelize GGNFS on a c124.)

            Well, I didn't say what it was relative to ;-)
            But I have changed "relatively easy" to "possible" on the record page.

            --
            Jens Kruse Andersen
          • Phil Carmody
            Posted by: Jens Kruse Andersen jens.k.a@get2net.dk jkand71 ... Wait a sec. You re constructing the composites. Why aren t you constructing them so that
            Message 5 of 8 , Aug 13, 2007
              Posted by: "Jens Kruse Andersen" jens.k.a@... jkand71
              > > Then there was the residual matter of factorizing 8
              > > algebraic cofactors with 128 digits. (Jens says that this is
              > > "relatively easy", but I do not know how many c128's he has
              > > cracked with MPQS or GNFS. My score is precisely 0, with one
              > > notable disaster trying to parallelize GGNFS on a c124.)
              >
              > Well, I didn't say what it was relative to ;-)
              > But I have changed "relatively easy" to "possible" on the record page.

              Wait a sec. You're constructing the composites. Why aren't you
              constructing them so that they'd be SNFS rather than GNFS?
              Forget stripping out the tiddlers with ECM, just use the 30%
              leverage that SNFS gives you instead.

              Phil

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

              [stolen with permission from Daniel B. Cristofani]



              ____________________________________________________________________________________
              Got a little couch potato?
              Check out fun summer activities for kids.
              http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&cs=bz
            • David Broadhurst
              ... Yes, that s eminently possible: it is easy to make the cofactors with digits/4 into simple quintics or sextics. The local problem is that with my GGNFS
              Message 6 of 8 , Aug 13, 2007
                --- In primeform@yahoogroups.com, Phil Carmody
                <thefatphil@...> wrote:

                > Wait a sec. You're constructing the composites. Why aren't you
                > constructing them so that they'd be SNFS rather than GNFS?
                > Forget stripping out the tiddlers with ECM, just use the 30%
                > leverage that SNFS gives you instead.

                Yes, that's eminently possible: it is easy to make the
                cofactors with digits/4 into simple quintics or sextics.

                The local problem is that with my GGNFS set-up the SNFS
                option is broken, as Bouk well knows :-(

                One fine day I might squeeze that extra 30%, with the
                understanding that I might need to subcontract SNFS.

                It's a good job Phil did not make his excellent suggestion
                before my latest record effort, else I might have acted on
                it and then missed the fluke that the second case with k=8
                gave k=10 for free.

                David
              • David Broadhurst
                ... I fixed it, at last. So now I guess that I am morally obliged to squeeze at least 25% extra digits. I ll try k=6 first, since there I have found a pair of
                Message 7 of 8 , Aug 29, 2007
                  --- In primeform@yahoogroups.com, "David Broadhurst"
                  <d.broadhurst@...> wrote:

                  > The local problem is that with my GGNFS set-up the SNFS
                  > option is broken, as Bouk well knows :-(

                  I fixed it, at last. So now I guess that I am morally
                  obliged to squeeze at least 25% extra digits.

                  I'll try k=6 first, since there I have found a pair of
                  rather neat 72nd [sic] order polynomials, that factorize
                  8/24 of the algebraic sextics into 16 cubics and leave the
                  remaining 16 sextics in a tidy form for SNFS, if they don't
                  fall below the MPQS or GNFS thresholds, after GMP-ECM.

                  But it may take a while to realize this 72nd order idea...

                  David (with thanks to Bouk and Phil)
                • David Broadhurst
                  ... ? m=67440294559676054016000; ? y=(2*x^6+3*x^3-148)^2; ? N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m; ? factor(N*(N-1)) %4 = [x 3] [x^3 - 11
                  Message 8 of 8 , Sep 7, 2007
                    --- In primeform@yahoogroups.com, "David Broadhurst"
                    <d.broadhurst@...> wrote:

                    > But it may take a while to realize this 72nd order idea...

                    ? m=67440294559676054016000;
                    ? y=(2*x^6+3*x^3-148)^2;
                    ? N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m;
                    ? factor(N*(N-1))
                    %4 =
                    [x 3]

                    [x^3 - 11 1]

                    [x^3 - 3 1]

                    [x^3 + 2 1]

                    [x^3 + 6 1]

                    [x^3 + 10 1]

                    [x^3 + 11 1]

                    [x^3 + 13 1]

                    [2*x^3 - 23 1]

                    [2*x^3 - 19 1]

                    [2*x^3 - 17 1]

                    [2*x^3 - 9 1]

                    [2*x^3 - 1 1]

                    [2*x^3 + 3 1]

                    [2*x^3 + 9 1]

                    [2*x^3 + 25 1]

                    [2*x^6 + 3*x^3 - 296 1]

                    [2*x^6 + 3*x^3 - 294 1]

                    [2*x^6 + 3*x^3 - 288 1]

                    [2*x^6 + 3*x^3 - 269 1]

                    [2*x^6 + 3*x^3 - 242 1]

                    [2*x^6 + 3*x^3 - 234 1]

                    [2*x^6 + 3*x^3 - 195 1]

                    [2*x^6 + 3*x^3 - 183 1]

                    [2*x^6 + 3*x^3 - 126 1]

                    [2*x^6 + 3*x^3 - 113 1]

                    [2*x^6 + 3*x^3 - 101 1]

                    [2*x^6 + 3*x^3 - 87 1]

                    [2*x^6 + 3*x^3 - 62 1]

                    [2*x^6 + 3*x^3 - 21 1]

                    [2*x^6 + 3*x^3 - 8 1]

                    [2*x^6 + 3*x^3 + 3 1]

                    A k=6 record, using SNFS, is expected, shortly.

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