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

Two large consecutive smooth numbers

Expand Messages
  • WarrenS
    N=43623575184339996059537425773119366447006380455838 696504055889999185302903791148393125043181272726633463298672436846034128 and N+1, both are smooth , i.e
    Message 1 of 17 , Mar 3, 2012
    • 0 Attachment
      N=43623575184339996059537425773119366447006380455838\
      696504055889999185302903791148393125043181272726633463298672436846034128

      and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.

      Can you do better (i.e. make N larger, and the max prime smaller)?
    • Andrey Kulsha
      ... Heuristically, log(max_N) is nearly proportional to sqrt(max_prime). So, with p
      Message 2 of 17 , Mar 3, 2012
      • 0 Attachment
        > N=43623575184339996059537425773119366447006380455838\
        > 696504055889999185302903791148393125043181272726633463298672436846034128
        >
        > and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.
        >
        > Can you do better (i.e. make N larger, and the max prime smaller)?

        Heuristically, log(max_N) is nearly proportional to sqrt(max_prime).

        So, with p < 9168769, one can find N with more than 5000 digits.

        But that's a hard puzzle, really. An easier puzzle is still to be solved:

        http://tech.groups.yahoo.com/group/primenumbers/message/23659
        > Puzzle: find a chain of 13 consecutive p-smooth integers,
        > starting at N, with log(N)/log(p) greater than
        >
        > log(8559986129664)/log(58393) = 2.71328

        Best regards,

        Andrey
      • Phil Carmody
        ... Calling Doctor Broadhurst for suggestion of the best metric by which to evaluate such records. A simple log doesn t necessarily tell the whole tale at all.
        Message 3 of 17 , Mar 3, 2012
        • 0 Attachment
          --- On Sat, 3/3/12, WarrenS <warren.wds@...> wrote:
          > N=43623575184339996059537425773119366447006380455838\
          > 696504055889999185302903791148393125043181272726633463298672436846034128
          >
          > and N+1, both are "smooth", i.e both factor entirely into
          > primes<=9168769.

          Calling Doctor Broadhurst for suggestion of the best metric by which to evaluate such records. A simple log doesn't necessarily tell the whole tale at all.

          Be warned, Warren - Dr. B is sitting on a corpus of algebraic formulae such that p(x) and p(x)+1 have algebraic factorisations, which makes smoothness measurably (I was going to say immeasurably, and then realised the stupidity of such a word choice) more likely.

          I'll not play this game, as I have an appointment with 21 farmers in Lithuania (otherwise known as the biggest brewery crawl yet...)

          Phil
        • djbroadhurst
          ... Those don t seem to be of immediate help, Phil. Warren knows about Prouhet-Tarry-Escott and has set a puzzle that goes deeper than that. I pass. David
          Message 4 of 17 , Mar 3, 2012
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            Phil Carmody <thefatphil@...> wrote:

            > B is sitting on a corpus of algebraic formulae such that p(x)
            > and p(x)+1 have algebraic factorisations

            Those don't seem to be of immediate help, Phil.
            Warren knows about Prouhet-Tarry-Escott and
            has set a puzzle that goes deeper than that.

            I pass.

            David
          • djbroadhurst
            ... Oh well, I guess that, having been set up by Phil, I ought not to pass. A quick coding of my favourite PTE identity seemed to leave a significant
            Message 5 of 17 , Mar 3, 2012
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "djbroadhurst" <d.broadhurst@...> wrote:

              > Warren knows about Prouhet-Tarry-Escott and
              > has set a puzzle that goes deeper than that.
              >
              > I pass.

              Oh well, I guess that, having been set up by Phil,
              I ought not to pass. A quick coding of my favourite
              PTE identity seemed to leave a significant computational
              load for Pari-GP. I am willing to let that code run
              for a few hours, without taking the effort to tune it.

              David
            • djbroadhurst
              ... but might, less coyly and more helpfully, have written {m=67440294559676054016000;y=1094090867210^2;
              Message 6 of 17 , Mar 3, 2012
              • 0 Attachment
                --- In primenumbers@yahoogroups.com,
                "WarrenS" <warren.wds@...> wrote:

                > N=43623575184339996059537425773119366447006380455838\
                > 696504055889999185302903791148393125043181272726633463298672436846034128

                but might, less coyly and more helpfully, have written

                {m=67440294559676054016000;y=1094090867210^2;
                N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-1;}

                in the more explicit manner of
                http://physics.open.ac.uk/~dbroadhu/cpte.pdf

                David
              • Kermit Rose
                ... e = limit(n-- infinity) (1+1/n)^n ln((n+1)/n) = ln(1 + 1/n) ln( (1+1/n)^n) is, for large n, approximately equal to 1. ln((1+1/n)^n) = n ln(1+1/n)
                Message 7 of 17 , Mar 4, 2012
                • 0 Attachment
                  On 3/4/2012 7:59 AM, primenumbers@yahoogroups.com wrote:
                  > 1a. Two large consecutive smooth numbers
                  > Posted by: "WarrenS"warren.wds@... warren_d_smith31
                  > Date: Sat Mar 3, 2012 9:19 am ((PST))
                  >
                  > N=43623575184339996059537425773119366447006380455838\
                  > 696504055889999185302903791148393125043181272726633463298672436846034128
                  >
                  > and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.
                  >
                  > Can you do better (i.e. make N larger, and the max prime smaller)?
                  >

                  e = limit(n--> infinity) (1+1/n)^n


                  ln((n+1)/n) = ln(1 + 1/n)

                  ln( (1+1/n)^n) is, for large n, approximately equal to 1.


                  ln((1+1/n)^n) = n ln(1+1/n)

                  ln(1+1/n) = approximately (1/n) for large n.


                  Find solutions to k1 ln(2) + k2 ln(3) + k3 ln(5) + .... < 1/n for
                  target large values of n.


                  Minimize k1 ln(2) + k2 ln(3) + k3 ln(5) + .... where some of the k's
                  are required to be positive, and some negative.


                  k1 ln(2) + k2 ln(3) is approximately 0

                  k1 ln(2) = approximately - k2 ln(3)

                  -k1/k2 = approximately ln(3)/ln(2)

                  One of k1, k2 is positive. The other is negative.

                  It seems straight forward to calculate the coefficients k1, k2, ,k3, etc
                  which minimizes this sum for given sets of primes,
                  2,3,5,etc.

                  From that minimum value of the sum for given sets of primes,
                  calculate n = int(1/minimum) as an upper bound for the n which applies.



                  Kermit Rose
                • Kermit Rose
                  ... To construct quadratics, x^2 - b x + c and x^2 - b x + c + 1 which are both factorisable, we look for integers b, k1, k2 such that c = k1 * (b-k1) and c+1
                  Message 8 of 17 , Mar 4, 2012
                  • 0 Attachment
                    On 3/4/2012 7:59 AM, primenumbers@yahoogroups.com wrote:
                    > 1c. Re: Two large consecutive smooth numbers
                    > Posted by: "Phil Carmody"thefatphil@... thefatphil
                    > Date: Sat Mar 3, 2012 3:03 pm ((PST))
                    >
                    > Calling Doctor Broadhurst for suggestion of the best metric by which to evaluate such records. A simple log doesn't necessarily tell the whole tale at all.
                    >
                    > Be warned, Warren - Dr. B is sitting on a corpus of algebraic formulae such that p(x) and p(x)+1 have algebraic factorisations, which makes smoothness measurably (I was going to say immeasurably, and then realised the stupidity of such a word choice) more likely.
                    >
                    > I'll not play this game, as I have an appointment with 21 farmers in Lithuania (otherwise known as the biggest brewery crawl yet...)
                    >
                    > Phil

                    To construct quadratics,

                    x^2 - b x + c and x^2 - b x + c + 1 which are both factorisable,

                    we look for integers b, k1, k2 such that

                    c = k1 * (b-k1)
                    and
                    c+1 = k2 * (b-k2)

                    1*3 = 3; 2 * 2 = 4

                    x^2 - 4 x + 3 = (x-1)*(x-3)
                    x^2 - 4 x + 4 = (x-2)^2

                    2 * 4 = 8; 3 * 3 = 9

                    x^2 - 6 x + 8 = (x-2)*(x-4)
                    x^2 - 6 x + 9 = (x-3)^2 which is really the same as the first example
                    translated by 1.

                    I will guess that maybe the only quadratic polynomial solutions are
                    translations of the first example.

                    Cubic polynomial solutions should be more prolific.

                    Kermit
                  • Jim White
                      Hi kermit,   The quadratic case simply corresponds to a 3-tuple of smooth {Q, Q+1, Q+2} inferring a pair at {(Q+1)^2 - 1, (Q+1)^2}   We are aiming for
                    Message 9 of 17 , Mar 4, 2012
                    • 0 Attachment
                       
                      Hi kermit,
                       
                      The quadratic case simply corresponds to a 3-tuple
                      of smooth {Q, Q+1, Q+2} inferring a pair at
                      {(Q+1)^2 - 1, (Q+1)^2}
                       
                      We are aiming for more massive "power boosting".
                       
                      cf: Prouhet-Tarry-Escott problem.
                       
                      Warrens SMODA II document has a good list of
                      known cases for polynomials to orders up to 10,
                      and I believe he has found pairs using a 12-th degree
                      poly.
                       
                      Cheers!


                      ________________________________
                      From: Kermit Rose <kermit@...>
                      To: primenumbers@yahoogroups.com
                      Sent: Monday, 5 March 2012, 1:59
                      Subject: [PrimeNumbers] Re: Two large consecutive smooth numbers

                      > I will guess that maybe the only quadratic polynomial solutions are
                      > translations of the first example.

                      Cubic polynomial solutions should be more prolific.

                      Kermit




                      [Non-text portions of this message have been removed]
                    • WarrenS
                      Jim White & I have been trying to construct these things because they are grist for my new factoring algorithm SMODA. That was one example of our output.
                      Message 10 of 17 , Mar 4, 2012
                      • 0 Attachment
                        Jim White & I have been trying to construct these things because they are grist for my
                        new factoring algorithm SMODA. That was one example of our output. Although we can break (and have broken) that record, I could only make N have about 30% more digits before
                        my current program would get very slow or self destruct.

                        If you have new approaches, and can break that record using them, great.
                        The PTE approach Broadhurst & Carmody were hinting at, is what I am using now for the
                        largest ones, so that's not a new idea unless you know something I do not about it.

                        If you are interested in donating computer time to this effort, intel last 10 years,
                        unix variant, ok to run weeks at a time in background, then
                        email warren.wds AT gmail.com.

                        Thank you.
                      • djbroadhurst
                        ... Yes. Let {f(y)= (y^2-11^4)*(y^2-35^2)*(y^2-47^2)* (y^2-94^2)*(y^2-146^2)*(y^2-148^2)/ 67440294559676054016000 - 1;} With N = f(1210851834572), we find that
                        Message 11 of 17 , Mar 4, 2012
                        • 0 Attachment
                          --- In primenumbers@yahoogroups.com,
                          "WarrenS" <warren.wds@...> wrote:

                          > N=43623575184339996059537425773119366447006380455838\
                          > 696504055889999185302903791148393125043181272726633463298672436846034128
                          > and N+1, both are "smooth", i.e both factor entirely into
                          > primes <= 9168769.
                          > Can you do better (i.e. make N larger, and the max prime smaller)?

                          Yes. Let
                          {f(y)=
                          (y^2-11^4)*(y^2-35^2)*(y^2-47^2)*
                          (y^2-94^2)*(y^2-146^2)*(y^2-148^2)/
                          67440294559676054016000 - 1;}

                          With N = f(1210851834572),
                          we find that N*(N+1) is 5205793-smooth.

                          With N = f(1606741747790),
                          we find that N*(N+1) is 8686687-smooth.

                          David
                        • djbroadhurst
                          ... I have not been following this in detail, but I gained the impression that Warren s original advert was far too optimistic and that now his heuristic for
                          Message 12 of 17 , Mar 4, 2012
                          • 0 Attachment
                            --- In primenumbers@yahoogroups.com,
                            "WarrenS" <warren.wds@...> wrote:

                            > Jim White & I have been trying to construct these things
                            > because they are grist for my new factoring algorithm SMODA.

                            I have not been following this in detail, but I gained the impression
                            that Warren's original advert was far too optimistic and that now
                            his heuristic for oracular factorization has escalated from
                            exp(log(N)^(1/3+o(1))) to the far less encouraging
                            exp(log(N)^(2/3+o(1))) as the time to construct a database.

                            Is this a fair summary of the setback?

                            David
                          • WarrenS
                            ... --well, yes and no. (And it wasn t a setback since I knew it all along.) (1) My factorization algorithm SMODA as far as I know still works and still
                            Message 13 of 17 , Mar 4, 2012
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                              >
                              >
                              >
                              > --- In primenumbers@yahoogroups.com,
                              > "WarrenS" <warren.wds@> wrote:
                              >
                              > > Jim White & I have been trying to construct these things
                              > > because they are grist for my new factoring algorithm SMODA.
                              >
                              > I have not been following this in detail, but I gained the impression
                              > that Warren's original advert was far too optimistic and that now
                              > his heuristic for oracular factorization has escalated from
                              > exp(log(N)^(1/3+o(1))) to the far less encouraging
                              > exp(log(N)^(2/3+o(1))) as the time to construct a database.
                              >
                              > Is this a fair summary of the setback?

                              --well, yes and no. (And it wasn't a "setback" since I knew it all along.)

                              (1) My factorization algorithm SMODA as far as I know still works and still runs in
                              exp(log(N)^(1/3+-o(1))) time PROVIDED database ("oracle") is available for its use.
                              It is plausibly better under this proviso than quadratic sieve and number field sieve,
                              but that at present is unconfirmed.

                              (2) For the problem of computing the database, however, I only have
                              exp(log(N)^(2/3+-o(1))) time algorithms for. However as we just saw, the o(1)
                              is fairly beneficial, since we can reach at least 400-bit-long database entries on a single computer, indeed Broadhurst just found some database entries of that size
                              in a matter of a few hours -- pretty fast turnaround! (His weren't as large as my
                              best records, but obviously Broadhurst has already built a search code comparable to or better than mine.) In fact I hope to release a preliminary database by me & Jim White, going up to 400-bits, in a few more days to interested parties.

                              (3) You might say that (2) sort of demolishes (1), but that is debatable. The thing is,
                              the database-build is something that all factorers worldwide can do collaboratively and do only once. Therefore, it is not fair to judge this runtime on the same footing as the other runtime. I admit I'm not quite sure how to judge it, because it has been a fairly rare thing
                              in the world so far, to have oracle-algorithms that actually are useful.

                              It is conceivable that (2)'s theoretical runtime can be sped up, but at present, I haven't been able to. Furthermore, few or no experts have carefully examined either (1) or (2) yet so it remains possible I'm crazy and the whole thing is broken. I doubt that -- I think any remaining errors are minor -- I'm just giving you fair warning.

                              --Warren D Smith
                            • Jim White
                              Hard puzzle, really hard puzzle   We know also that, while max N might exist with ~5000 digits, his nearest p-smooth neighbour pair might well be hundreds of
                              Message 14 of 17 , Mar 5, 2012
                              • 0 Attachment
                                Hard puzzle, really hard puzzle
                                 
                                We know also that, while max N might exist with ~5000
                                digits, his nearest p-smooth neighbour pair might
                                well be hundreds of digits smaller.  
                                 
                                What we don't know is which pairs N are "PTE-compatible",
                                ie can be found via some factoring
                                polynomial whose roots are all p-smooth.
                                 
                                Any ideas on that issue would be useful
                                 
                                Jim White
                                 

                                ________________________________
                                From: Andrey Kulsha <Andrey_601@...>
                                To: PrimeNumbers@...
                                Sent: Sunday, 4 March 2012, 9:53
                                Subject: Re: [PrimeNumbers] Two large consecutive smooth numbers


                                 

                                Heuristically, log(max_N) is nearly proportional to sqrt(max_prime).

                                So, with p < 9168769, one can find N with more than 5000 digits.

                                But that's a hard puzzle, really.

                                [Non-text portions of this message have been removed]
                              • Jim White
                                Andrey s chain puzzle is interesting.  Could it be he already has found the maximum possible result for chain length 13?   It s hard to see how that result
                                Message 15 of 17 , Mar 5, 2012
                                • 0 Attachment
                                  Andrey's chain puzzle is interesting.  Could it be
                                  he already has found the maximum possible result
                                  for chain length 13?
                                   
                                  It's hard to see how that result can be beaten.
                                   
                                  Some results with weights of 2.2 or more:
                                   
                                      28246112570058, weight = 2.2053 (P =  1257251)
                                      18911412089528, weight = 2.2077 (P =  1032307)
                                     218381019281507, weight = 2.2410 (P =  2504167)
                                       9288363679368, weight = 2.2480 (P =   587149)
                                    3393509932556102, weight = 2.2536 (P =  7788997)
                                    4532039198639948, weight = 2.2536 (P =  8856259)
                                    4532039198639949, weight = 2.2536 (P =  8856259)
                                   12469670986534198, weight = 2.2547 (P = 13762769)
                                   10160468895884110, weight = 2.2592 (P = 12163843)
                                     461881571558141, weight = 2.2615 (P =  3050603)
                                    7909529450841510, weight = 2.2621 (P = 10669823)
                                     211814723372355, weight = 2.2918 (P =  1782043)
                                     430753934627814, weight = 2.4217 (P =  1103933)

                                  Perhaps the 14-chain at N = 4532039198639948 might
                                  be a good result? What are the best known results
                                  for 14 or longer chains?


                                  ________________________________
                                  From: Andrey Kulsha <Andrey_601@...>
                                  To: PrimeNumbers@...
                                  Sent: Sunday, 4 March 2012, 9:53
                                  Subject: Re: [PrimeNumbers] Two large consecutive smooth numbers


                                   

                                  > Puzzle: find a chain of 13 consecutive p-smooth integers,
                                  > starting at N, with log(N)/log(p) greater than
                                  >
                                  > log(8559986129664)/log(58393) = 2.71328

                                  Best regards,

                                  Andrey




                                  [Non-text portions of this message have been removed]
                                • Andrey Kulsha
                                  ... No, I think that log/log ratio has no limit. ... Brute force search yielded: N = 505756884840 for 14-chain N = 285377140980 for 15-chain N = 32290958458
                                  Message 16 of 17 , Mar 5, 2012
                                  • 0 Attachment
                                    > Andrey's chain puzzle is interesting. Could it
                                    > be he already has found the maximum possible
                                    > result for chain length 13?

                                    No, I think that log/log ratio has no limit.

                                    > Perhaps the 14-chain at N = 4532039198639948
                                    > might be a good result? What are the best known
                                    > results for 14 or longer chains?

                                    Brute force search yielded:
                                    N = 505756884840 for 14-chain
                                    N = 285377140980 for 15-chain
                                    N = 32290958458 for 16-chain
                                    as listed in http://www.primefan.ru/stuff/math/maxs.xls
                                    (there k+1 is chain length)

                                    Best regards,

                                    Andrey
                                  • Jim White
                                    Andrey,   I can t use that file, I don t have XL.  Any chance of a text export? eg comma-separated fields     ________________________________ From:
                                    Message 17 of 17 , Mar 5, 2012
                                    • 0 Attachment
                                      Andrey,
                                       
                                      I can't use that file, I don't have XL.  Any chance
                                      of a text export? eg comma-separated fields
                                       
                                       

                                      ________________________________
                                      From: Andrey Kulsha <Andrey_601@...>
                                      To: PrimeNumbers@...
                                      Sent: Tuesday, 6 March 2012, 6:28
                                      Subject: [PrimeNumbers] Re: 13-chains of consecutive smooth numbers



                                       

                                      > Andrey's chain puzzle is interesting. Could it
                                      > be he already has found the maximum possible
                                      > result for chain length 13?

                                      No, I think that log/log ratio has no limit.

                                      > Perhaps the 14-chain at N = 4532039198639948
                                      > might be a good result? What are the best known
                                      > results for 14 or longer chains?

                                      Brute force search yielded:
                                      N = 505756884840 for 14-chain
                                      N = 285377140980 for 15-chain
                                      N = 32290958458 for 16-chain
                                      as listed in http://www.primefan.ru/stuff/math/maxs.xls
                                      (there k+1 is chain length)

                                      Best regards,

                                      Andrey



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