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

Factorization of 6 consecutive integers > 10^1100

Expand Messages
  • David Broadhurst
    Let m=67440294559676054016000 y=(m*(10^71+145589)+22)^2 N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5 then N+k is factorized for k in [0,5].
    Message 1 of 15 , Aug 14, 2007
      Let

      m=67440294559676054016000
      y=(m*(10^71+145589)+22)^2
      N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5

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

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

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

      Neighbouring composites:
      c1094=(N-1)/(5*1948359547)
      c1090=(N+6)/(2*11969*4471247659)
      subjected to 300 ECM curves at B1=100000

      David Broadhurst
      14 August 2007
    • Jens Kruse Andersen
      ... Congratulations! Very neat. I was wondering whether you would go for 6 record numbers with a construction inspired by Jaroslaw s P(X). Thanks for showing
      Message 2 of 15 , Aug 14, 2007
        David Broadhurst wrote:
        > m=67440294559676054016000
        > y=(m*(10^71+145589)+22)^2
        > N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5
        >
        > then N+k is factorized for k in [0,5].

        Congratulations!
        Very neat. I was wondering whether you would go for 6 record
        numbers with a construction inspired by Jaroslaw's P(X).
        Thanks for showing such an interest in my record page.
        http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm is updated.
        I assume you don't object to 94-digit factorizations being
        "relatively easy".

        --
        Jens Kruse Andersen
      • David Broadhurst
        ... No objection at all: I took a lazy route for k=6, staying well within the comfort zone of Msieve. Update on the wings: N = -6 mod
        Message 3 of 15 , Aug 14, 2007
          --- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
          wrote:

          > I assume you don't object to 94-digit factorizations being
          > "relatively easy".

          No objection at all: I took a lazy route for k=6,
          staying well within the comfort zone of Msieve.

          Update on the wings:

          N = -6 mod 460041067299095322777708682147

          with p35 still running.

          David
        • N.L.
          Hello ! I have a collection about 210 6k twins. for n+2 and n-2 I have scan all primfactors up to 1.6E9, without success. Perhaps find one of you the 4th
          Message 4 of 15 , Aug 16, 2007
            Hello !

            I have a collection about 210 6k twins.
            for n+2 and n-2 I have scan all primfactors up to
            1.6E9,
            without success.

            Perhaps find one of you the 4th candidate. Any ideas
            or interests ?

            regards

            Norman





            Wissenswertes für Bastler und Hobby Handwerker. BE A BETTER HEIMWERKER! www.yahoo.de/clever
          • David Broadhurst
            ... If you run ECM up to p20 level you have a good chance: mu = 2*210*exp(Euler)*20/6200 = 2.4 and then you may well end up with a long haul, usin ECPP at 6.2k
            Message 5 of 15 , Aug 16, 2007
              --- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:

              > I have a collection about 210 6k twins.
              > for n+2 and n-2 I have scan all primfactors up to
              > 1.6E9, without success.

              If you run ECM up to p20 level you have a good chance:

              mu = 2*210*exp(Euler)*20/6200 = 2.4

              and then you may well end up with a long haul,
              usin ECPP at 6.2k digits, for a /genuine/ record.
              [Note that, uncharacteristically, Jens allowed himself
              to cheat, by not waiting for Primo at 4178 digits.]

              David
            • Jens Kruse Andersen
              ... Around half would find no factor from 1.6E9 to p20 level ECM, so that half doesn t contribute to the chance. And p20 ECM on 420 6k numbers is not easy:
              Message 6 of 15 , Aug 16, 2007
                David Broadhurst wrote:
                > --- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:
                >
                >> I have a collection about 210 6k twins.
                >> for n+2 and n-2 I have scan all primfactors up to
                >> 1.6E9, without success.
                >
                > If you run ECM up to p20 level you have a good chance:
                >
                > mu = 2*210*exp(Euler)*20/6200 = 2.4

                Around half would find no factor from 1.6E9 to p20 level ECM,
                so that half doesn't contribute to the chance.
                And p20 ECM on 420 6k numbers is not easy:
                420*74 curves taking 5 GHz minutes on one of my cpu cores
                gives 108 GHz days.
                With one (dual core) computer and lots of projects, I would
                only give it p15 ECM if I got the twins.

                > and then you may well end up with a long haul,
                > usin ECPP at 6.2k digits, for a /genuine/ record.
                > [Note that, uncharacteristically, Jens allowed himself
                > to cheat, by not waiting for Primo at 4178 digits.]

                I don't know if anybody would do 6k ECPP for my novel record page.
                I wouldn't do 4178 digits, so it's up for grabs for a record share:
                (240819405*2^13879+3)/(3*13*43*358877)
                I may have cheated a little by allowing a prp factor but I also list the
                proven 4-number record which I also have.

                By the way, 6k with Primo would make the Primo top-20:
                http://www.ellipsa.net/public/primo/top20.html
                There are no certifications since 2005.
                The Prime Pages ECPP top-20 at http://primes.utm.edu/top20/page.php?id=27
                has a Primo submission from July 12 2007:
                http://primes.utm.edu/primes/page.php?id=81647
                It's 17443#/2-2^17443 with 7508 digits by Markus Hiltbrunner
                who has no other primes. It would be third on the Primo top-20.
                Is there a published certificate? It appears Marcel requires it but not
                Chris.

                --
                Jens Kruse Andersen
              • N.L.
                Hello ! That is the problem ! A ECM test for a single number ( I have 420!) takes to many time. Better is a Pollard Test for 6k numbers but I don t have a
                Message 7 of 15 , Aug 16, 2007
                  Hello !

                  That is the problem !
                  A ECM test for a single number ( I have 420!) takes to
                  many time. Better is a Pollard Test for 6k numbers but
                  I don't have a programm that handle this type.
                  I can test factors up to 10^11..if I have luck,okay ,I
                  don't have luck ->pitch!

                  --
                  Norman




                  --- Jens Kruse Andersen <jens.k.a@...> schrieb:

                  > David Broadhurst wrote:
                  > > --- In primeform@yahoogroups.com, "N.L."
                  > <nluhn@...> wrote:
                  > >
                  > >> I have a collection about 210 6k twins.
                  > >> for n+2 and n-2 I have scan all primfactors up to
                  > >> 1.6E9, without success.
                  > >
                  > > If you run ECM up to p20 level you have a good
                  > chance:
                  > >
                  > > mu = 2*210*exp(Euler)*20/6200 = 2.4
                  >
                  > Around half would find no factor from 1.6E9 to p20
                  > level ECM,
                  > so that half doesn't contribute to the chance.
                  > And p20 ECM on 420 6k numbers is not easy:
                  > 420*74 curves taking 5 GHz minutes on one of my cpu
                  > cores
                  > gives 108 GHz days.
                  > With one (dual core) computer and lots of projects,
                  > I would
                  > only give it p15 ECM if I got the twins.
                  >
                  > > and then you may well end up with a long haul,
                  > > usin ECPP at 6.2k digits, for a /genuine/ record.
                  > > [Note that, uncharacteristically, Jens allowed
                  > himself
                  > > to cheat, by not waiting for Primo at 4178
                  > digits.]
                  >
                  > I don't know if anybody would do 6k ECPP for my
                  > novel record page.
                  > I wouldn't do 4178 digits, so it's up for grabs for
                  > a record share:
                  > (240819405*2^13879+3)/(3*13*43*358877)
                  > I may have cheated a little by allowing a prp factor
                  > but I also list the
                  > proven 4-number record which I also have.
                  >
                  > By the way, 6k with Primo would make the Primo
                  > top-20:
                  > http://www.ellipsa.net/public/primo/top20.html
                  > There are no certifications since 2005.
                  > The Prime Pages ECPP top-20 at
                  > http://primes.utm.edu/top20/page.php?id=27
                  > has a Primo submission from July 12 2007:
                  > http://primes.utm.edu/primes/page.php?id=81647
                  > It's 17443#/2-2^17443 with 7508 digits by Markus
                  > Hiltbrunner
                  > who has no other primes. It would be third on the
                  > Primo top-20.
                  > Is there a published certificate? It appears Marcel
                  > requires it but not
                  > Chris.
                  >
                  > --
                  > Jens Kruse Andersen
                  >
                  >



                  __________________________________
                  Yahoo! Clever - Der einfachste Weg, Fragen zu stellen und Wissenswertes mit Anderen zu teilen. www.yahoo.de/clever
                • Jens Kruse Andersen
                  ... I don t know why GMP-ECM stopped giving recommended p15 parameters. ... This is the README file of gmp-ecm-5.0, a new version of gmp-ecm, replacing version
                  Message 8 of 15 , Aug 16, 2007
                    Norman wrote:
                    > A ECM test for a single number ( I have 420!) takes to
                    > many time. Better is a Pollard Test for 6k numbers but
                    > I don't have a programm that handle this type.
                    > I can test factors up to 10^11..if I have luck,okay ,I
                    > don't have luck ->pitch!

                    I don't know why GMP-ECM stopped giving recommended p15 parameters.
                    Here is some of the documentation for a former version:
                    ------------------------------------
                    This is the README file of gmp-ecm-5.0, a new version of gmp-ecm,
                    replacing version 4c.

                    The ECM method is a probabilistic method, and can be viewed in some sense
                    as a generalization of the P-1 and P+1 method, where we only require that
                    P+t is smooth, with t random of order P^(1/2). The optimal B1 and B2 bounds
                    have to be chosen according to the (usually unknown) size of P. The
                    following
                    table gives a set of near-to-optimal B1 and B2 pairs, with the corresponding
                    expected number of curves to find a factor of given size (this table does
                    not
                    take into account the "extra factors" found by Brent-Suyama's extension, see
                    below).

                    digits D optimal B1 B2 expected curves N(B1,B2,D)
                    15 2e3 1.2e5 30
                    20 11e3 1.4e6 90
                    25 5e4 1.2e7 240
                    30 25e4 1.1e8 500
                    35 1e6 8.4e8 1100
                    40 3e6 4.0e9 2900
                    45 11e6 2.6e10 5500
                    50 43e6 1.8e11 9000
                    55 11e7 6.8e11 22000
                    60 26e7 2.3e12 52000
                    65 85e7 1.3e13 83000
                    70 29e8 7.2e13 120000

                    Table 1: optimal B1 and expected number of curves to find a
                    factor of D digits.

                    Important note: the expected number of curves is significantly smaller
                    than the "classical" one we get with B2=100*B1. This is due to the
                    fact that this new version of gmp-ecm uses a default B2 which is much
                    larger than 100*B1 (for large B1), thanks to the improvements in step 2.

                    After performing the expected number of curves from Table 1, the
                    probability that a number of D digits was missed is exp(-1), i.e.
                    about 37%. After twice the expected number of curves, it is exp(-2),
                    i.e. about 14%, and so on.

                    Example: after performing 9000 curves with B1=43e6 and B2=1.8e11,
                    the probability to miss a 50-digit factor is about 37%.

                    In summary, we advise the following method:

                    0 - choose a target factor size of D digits
                    1 - choose "optimal" B1 and B2 values to find factors of D digits
                    2 - run once P-1 with those B1 and B2
                    3 - run 3 times P+1 with those B1 and B2
                    4 - run N(B1,B2,D) times ECM with those B1 and B2, where N(B1,B2,D) is the
                    expected number of ECM curves with step 1 bound B1, step 2 bound B2,
                    to find a factor of D digits (cf above table)
                    5 - if no factor is found, either increase D and go to 0, or use another
                    factorization method (MPQS, GNFS)
                    ------------------------------------

                    Some things have changed in later versions. I'm not sure how
                    they affect p15 work.
                    This is a guess at reasonable p15 parameters with GMP-ECM 6.1.2:

                    P-1 with B1=20000 and default B2: ecm -pm1 20000
                    3 times P+1 with B1=10000 and default B2: ecm -c 3 -pp1 10000
                    26 curves with B1=2000 and default B2: ecm -c 26 2000

                    This may take around 2 GHz weeks for 420 6k numbers.

                    Suppose you have saved far more primes n-1 where n is trivially
                    factored and n+1 was composite.
                    Then n-1, n, 2n-2, 2n, 3n-3,3n are factored. You could then
                    try trial factoring and prp (no ecm) on
                    n-3, n-2, 2n-3, 2n-1, 2n+1, 3n-2, 3n-1.
                    If one of these gives a prp cofactor then you have 3 of 4 and
                    could do p15 ecm on the last (the last two if 2n-1 split).
                    If successful, you would probably have two 6k prp's that
                    require ECPP, but I accept them as prp records.

                    --
                    Jens Kruse Andersen
                  • David Broadhurst
                    ... Marcel missed this one, from July 2007: http://primes.utm.edu/primes/page.php?id=81647 David
                    Message 9 of 15 , Aug 16, 2007
                      --- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
                      wrote:

                      > http://www.ellipsa.net/public/primo/top20.html
                      > There are no certifications since 2005.

                      Marcel missed this one, from July 2007:

                      http://primes.utm.edu/primes/page.php?id=81647

                      David
                    • David Broadhurst
                      ... That sounds like less than a week s work, for Sean Irvine. Best advice to Norman: share your finds with Sean! David
                      Message 10 of 15 , Aug 16, 2007
                        --- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
                        wrote:

                        > 420*74 curves taking 5 GHz minutes on one of my cpu cores
                        > gives 108 GHz days.

                        That sounds like less than a week's work, for Sean Irvine.

                        Best advice to Norman: share your finds with Sean!

                        David
                      • David Broadhurst
                        ... I see that p15 was enough: http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm ... Congrats to Norman and Christophe. David
                        Message 11 of 15 , Aug 28, 2007
                          --- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:

                          > A ECM test for a single number ( I have 420!) takes to
                          > many time.

                          I see that p15 was enough:

                          http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
                          > n+3 = 2^3*943127*5020192965913*prp6203

                          Congrats to Norman and Christophe.

                          David
                        • Jens Kruse Andersen
                          ... Yes, congratulations. They found two cases with p12 and p13 as penultimate factors. There is no plan to prove prp6203. After 3 weeks with the page, my 4
                          Message 12 of 15 , Aug 28, 2007
                            David Broadhurst wrote:
                            > I see that p15 was enough:
                            >
                            > http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
                            >> n+3 = 2^3*943127*5020192965913*prp6203
                            >
                            > Congrats to Norman and Christophe.

                            Yes, congratulations.
                            They found two cases with p12 and p13 as penultimate factors.
                            There is no plan to prove prp6203.

                            After 3 weeks with the page, my 4 records are already beaten, and 3 further
                            lengths have been found. I'm surprised by so many great results so quickly.
                            Thanks to everybody. I expect things to cool down now but what do I know?

                            --
                            Jens Kruse Andersen
                          • David Broadhurst
                            ... That s easy to explain: your idea for a record page was so clearly and cleanly executed that anyone who had anything up their sleeve was almost bound to
                            Message 13 of 15 , Aug 29, 2007
                              --- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
                              wrote:

                              > I'm surprised by so many great results so quickly.

                              That's easy to explain: your idea for a record page was
                              so clearly and cleanly executed that anyone who had
                              anything up their sleeve was almost bound to respond.

                              > I expect things to cool down now but what do I know?

                              Well, at least the k=6 and k=8 records are soft targets
                              for Phil's GNFS ==> SNFS improvement. (k=7 and k=10
                              may be harder to improve since there I had beginner's
                              luck, with the PFGW + GMP-ECM parts of the problem.)

                              David
                            • David Broadhurst
                              ... Well, it may be that k=3 is also under threat: http://www.primegrid.com/all_news.php#11 ... But maybe that message is about a Woodall/Cullen find? David
                              Message 14 of 15 , Aug 29, 2007
                                --- In primeform@yahoogroups.com, "Jens Kruse Andersen"
                                <jens.k.a@...> wrote:

                                > I expect things to cool down now but what do I know?

                                Well, it may be that k=3 is also under threat:

                                http://www.primegrid.com/all_news.php#11
                                > Your computer has made a significant discovery,
                                > and we want to know your details before we publicize it.

                                But maybe that message is about a Woodall/Cullen find?

                                David
                              • djbroadhurst
                                ... This apparently unvalidated claim is still on list. Perhaps Chris might ask the submitter for evidence? David
                                Message 15 of 15 , Jul 12, 2010
                                  --- In primeform@yahoogroups.com,
                                  "Jens Kruse Andersen" <jens.k.a@...> wrote:

                                  > The Prime Pages has a Primo submission from July 12 2007:
                                  > http://primes.utm.edu/primes/page.php?id=81647
                                  ...
                                  > Is there a published certificate?
                                  > It appears Marcel requires it but not Chris.

                                  This apparently unvalidated claim is still on list.
                                  Perhaps Chris might ask the submitter for evidence?

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