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

Factorization of 8 consecutive integers > 10^500

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

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

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

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

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

      David Broadhurst
      9 August 2007
    • Jens Kruse Andersen
      ... Congratulations! That was amazingly fast. I wondered whether anybody would even try 8 for years with the limit set at 500 digits. I guess you are also
      Message 2 of 7 , Aug 9, 2007
        David Broadhurst wrote:
        > x=13860*(10^60+720251)
        > N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440
        >
        > then N+k is factorized for k in [0,7].

        Congratulations!
        That was amazingly fast. I wondered whether anybody would
        even try 8 for years with the limit set at 500 digits.
        I guess you are also trying your ecm luck on N-1 and N+8.
        http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm is updated.

        --
        Jens Kruse Andersen
      • David Broadhurst
        ... Mainly thanks to Jarek, for his nice quartic Ansatz, which was easy to adapt, to give only 8 c125 factors, in 3 of the 8 targets, instead of the 11 that
        Message 3 of 7 , Aug 9, 2007
          --- In primeform@yahoogroups.com, "Jens Kruse Andersen"
          <jens.k.a@...> wrote:

          > That was amazingly fast. I wondered whether anybody would
          > even try 8 for years with the limit set at 500 digits.

          Mainly thanks to Jarek, for his nice quartic Ansatz,
          which was easy to adapt, to give only 8 c125 factors,
          in 3 of the 8 targets, instead of the 11 that you spotted.

          I had a nasty moment, at the very end, with a c115 that
          looked as if it might need GGNFS, or MPQS, but finally it
          cracked with ECM, which is /embarrassingly/ parallel.

          David
        • Sean A. Irvine
          Nice! That was a very quick response to the challenge. S.
          Message 4 of 7 , Aug 9, 2007
            Nice! That was a very quick response to the challenge.

            S.

            David Broadhurst wrote:
            > --- In primeform@yahoogroups.com, "Jens Kruse Andersen"
            > <jens.k.a@...> wrote:
            >
            >
            >>That was amazingly fast. I wondered whether anybody would
            >>even try 8 for years with the limit set at 500 digits.
            >
            >
            > Mainly thanks to Jarek, for his nice quartic Ansatz,
            > which was easy to adapt, to give only 8 c125 factors,
            > in 3 of the 8 targets, instead of the 11 that you spotted.
            >
            > I had a nasty moment, at the very end, with a c115 that
            > looked as if it might need GGNFS, or MPQS, but finally it
            > cracked with ECM, which is /embarrassingly/ parallel.
            >
            > David
          • David Broadhurst
            ... Jarek s construction involves this Diophantine problem: Find a pair of positive coprime integers [a,b], with a
            Message 5 of 7 , Aug 10, 2007
              --- In primeform@yahoogroups.com,
              "Sean A. Irvine" <sairvin@...> wrote:

              > Nice! That was a very quick response to the challenge.

              Jarek's construction involves this Diophantine problem:

              Find a pair of positive coprime integers [a,b], with a<b,
              such that there exist two pairs of positive integers,
              [c,d] and [e,f], with c < d, c < e < f,
              2*a^2 + 2*b^2 = c^2 + d^2 = e^2 + f^2
              and distinct positive integers
              g = |(4*a*b)^2 -(d^2-c^2)^2|
              h = |(4*a*b)^2 -(f^2-e^2)^2|
              satisfying max(g,h) < 6*gcd(g,h).

              There are (at least) 6 solutions:

              [ a, b] [ c, d] [ e, f] g/h

              [ 1,47] [18,64] [24,62] 4/3
              [ 9,32] [ 1,47] [19,43] 4
              [12,31] [ 1,47] [23,41] 3
              [19,43] [18,64] [46,48] 1/3
              [23,24] [19,43] [23,41] 3/4
              [23,41] [24,62] [46,48] 1/4

              of which Jarek chose the last.

              The other 5 solutions may be obtained from Jarek's,
              by noting that

              [18,64]/2 = [ 9,32]
              [24,62]/2 = [12,31]
              [46,48]/2 = [23,24]

              and then permuting pairs of coprime integers.

              Question: Are there any more solutions?
              If not, then Jarek's construction is essentially unique.

              Here is a test with b running up to 500:

              {jarek(a,b)=local(s,t,C,G,c,d,g,h);
              s=2*(a^2+b^2);t=sqrtint(s/2);C=[];G=[];
              for(c=1,t,if(issquare(s-c^2,&d),g=abs((4*a*b)^2-(d^2-c^2)^2);
              if(d>c&&g,G=concat(G,g);C=concat(C,[[c,d]]))));
              for(i=2,length(G),h=G[i];for(j=1,i-1,g=G[j];
              if(max(g,h)<6*gcd(g,h),print([[a,b],C[j],C[i],g/h]))))}

              for(a=1,500,for(b=a+1,500,if(gcd(a,b)==1,jarek(a,b))))

              [[1, 47], [18, 64], [24, 62], 4/3]
              [[9, 32], [1, 47], [19, 43], 4]
              [[12, 31], [1, 47], [23, 41], 3]
              [[19, 43], [18, 64], [46, 48], 1/3]
              [[23, 24], [19, 43], [23, 41], 3/4]
              [[23, 41], [24, 62], [46, 48], 1/4]
              Goodbye!

              David
            • Andrey Kulsha
              That reminded me... http://tech.groups.yahoo.com/group/primenumbers/message/9901
              Message 6 of 7 , Aug 11, 2007
              • David Broadhurst
                ... Andrey s suggested method for 11 consecutive factorizations at 200 digits was to find factorizations of x^6-a, in the 5 hardest cases: a=2,3,5,6,7, and
                Message 7 of 7 , Aug 11, 2007
                  --- In primeform@yahoogroups.com, "Andrey Kulsha"
                  <Andrey_601@...> wrote:

                  > That reminded me...
                  > http://tech.groups.yahoo.com/group/primenumbers/message/9901

                  Andrey's suggested method for 11 consecutive factorizations
                  at 200 digits was to find factorizations of x^6-a, in the
                  5 hardest cases:

                  a=2,3,5,6,7,

                  and then tackle the 6 easier cases:

                  a=-1,0,1,4,8,9,

                  where there are obvious algebraic factorizations,
                  to split the burden.

                  This looks rather tough at 500 digits.

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