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

Re: Two large consecutive smooth numbers

Expand Messages
  • 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 1 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 2 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 3 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 4 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 5 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 6 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 7 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.