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

Re: [PrimeNumbers] RE: Estimating log (B^pi(B))

Expand Messages
  • Phil Carmody
    ... Spot on. I like it. That s a completely sideways way of looking at things! I like it! ... Speak for yourself. I used {1,2,12} and {1,4,6} /precisely/ for
    Message 1 of 19 , Jan 31, 2003
    • 0 Attachment
      --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
      > > Woh! I can't see Dickman in that at all.
      > > What am I missing?
      >
      > Let me backtrack a bit, to Aurifeuille.
      ...
      > (more or less) T1 and T2 digits then Dickman suggests
      > (don't eek me, I only said sugests) that we will
      > get them twice as fast, compared with when there
      > isn't such a factorization.

      Spot on. I like it. That's a completely sideways way of looking at things!
      I like it!

      > Now what's special about those 3 buttons?
      >
      > ? print(factor((1+x)*(1+2*x)*(1+12*x)-1))
      > [x, 1; 4*x + 3, 1; 6*x + 5, 1]
      >
      > ? print(factor((1+x)*(1+2*x)*(1+15*x)-1))
      > [x, 1; 3*x + 2, 1; 10*x + 9, 1]
      >
      > ? print(factor((1+x)*(1+4*x)*(1+6*x)-1))
      > [x, 1; 2*x + 1, 1; 12*x + 11, 1]
      >
      > Of course you and I did not bother about this when we used CRT.

      Speak for yourself. I used {1,2,12} and {1,4,6} /precisely/ for that reason.
      I think one of my results was a {1,4,6} wasn't it?

      > But Markus is stuck with his NewPgen output and so
      > can't use CRT. So I thought it would be useful
      > to give {1,2,12} a proof in principle by beating the
      > 4-Carmichael 4th factor record.
      >
      > In fact I did it twice over:
      >
      > 2763260532*((1591638066432*3061#+19)^2-1)*3061#/
      > 286610757607008951353515277095+1 3909 p44 03
      > 4-Carmichael factor (4)
      >
      > 757849549*((72753556704*3061#+19)^2-1)*3061#/
      > 56731664597567983567442428202862519351615138+1 3891 p44 03
      > 4-Carmichael factor (4)
      >
      > finding ECM factors at about twice
      > the rate for this seed as compared with
      > the other seeds in my plantpot.
      >
      > OK, it's a trivial [and suspect] use of Dickman.

      Indeed it is.
      It's a great idea for trying to squeeze out factors quicker, certainly.

      I'm surprised it works, because the factors need to be of a particular
      residue in order to make the thing carmichael (like your lucky 2s in the
      3-carmichael).

      There's the Saarinen DLOG trick one can use. However, he's not published
      that yet. (It's one of the tricks that helped him generate the multi-
      billion-digit Carmichael so easily last month.)

      You seem to have claimed a *2 speedup over the naive technique? I think I
      claimed either a *4 or *6 speedup. However, as you have noted elsewhere I
      become constipated with CRT. (Not every element in my speedup contributed a
      linear factorisation, and therefore caused doping-bloat.)

      Phil


      =====
      Is that free as in Willy or as in bird?

      __________________________________________________
      Do you Yahoo!?
      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
      http://mailplus.yahoo.com
    • David Broadhurst <d.broadhurst@open.ac.u
      ... Thank ye, kind sir. ... Yep. I said you didn t need to bother, not that you didn t bother. ... begin{explanation} lcm{1,2,12}=3*4 We get the 3 from 4*x+3,
      Message 2 of 19 , Feb 1 1:36 AM
      • 0 Attachment
        Phil:

        > That's a completely sideways way of looking at things!
        > I like it!

        Thank ye, kind sir.

        > I think one of my results was a {1,4,6} wasn't it?

        Yep. I said you didn't need to bother, not that you
        didn't bother.

        > I'm surprised it works, because the factors need to
        > be of a particular residue in order to make the thing
        > carmichael

        \begin{explanation}

        lcm{1,2,12}=3*4

        We get the 3 from 4*x+3, since
        x=0 mod 3, because of the primorial.

        We get the 4 from (1+1/d).
        All possible d's are odd.
        So half of the combinations of ECM primes work.
        But we double these using the 5 from 6*x+5,
        since x=0 mod 5, because of the primorial.

        So {1,2,12} is as rich as {1,2,3}.
        Except that it's twice as fast
        as {1,2,3} for ECMing.

        \end{explanation}
      • Markus Frind
        Given the 1,2,15 seed, or 1,2,12 seed etc Couldn t we check for a 4th element using ECM, and a 5th element (e) such that we can form a 5-carm of the form N
        Message 3 of 19 , Feb 1 8:07 AM
        • 0 Attachment
          Given the 1,2,15 seed, or 1,2,12 seed etc
          Couldn't we check for a 4th element using ECM, and a 5th element (e) such
          that we can form a 5-carm of the form N = e*1*2*15*ECMFactor

          Carms of that form

          5,7,13,193,439,9637697
          5,7,13,193,499,2657,42829
          5,19,37,547,1009,3211937
          7,19,37,541,601,58741
          7,79,157,2341,3541,9181
          13,19,37,541,631,2689
          13,19,37,541,739,811,1231
          13,19,37,541,1009,2311
          17,37,73,1093,2081,65521
          17,37,73,1093,93809

          With my dataset i will have 4 billion possible e values and 350 titanic
          seeds of whatever 3 part seed that is picked. Is it possible to create a
          carm by extending a "seed" at both ends. IE creating a custom formula for
          each e*1*2*15 which is then ecm'd. to get a prime that
          makes e*1*2*15*ECMFactor PRP


          Markus



          >But Markus is stuck with his NewPgen output and so
          >can't use CRT. So I thought it would be useful
          >to give {1,2,12} a proof in principle by beating the
          >4-Carmichael 4th factor record.
          >
          >In fact I did it twice over:
          >
          >2763260532*((1591638066432*3061#+19)^2-1)*3061#/
          >286610757607008951353515277095+1 3909 p44 03
          >4-Carmichael factor (4)
          >
          >757849549*((72753556704*3061#+19)^2-1)*3061#/
          >56731664597567983567442428202862519351615138+1 3891 p44 03
          >4-Carmichael factor (4)
          >
          >finding ECM factors at about twice
          >the rate for this seed as compared with
          >the other seeds in my plantpot.
          >
          >OK, it's a trivial [and suspect] use of Dickman.
          >
          >But it was funny that you should mention him
          >just after I had commented on another such seed
          >{1,2,15}. But Markus can't use that
          >Dickman-enhanced seed, since he
          >can't get x=1 mod 5 in
          >
          >? print(factor((1+x)*(1+2*x)*(1+15*x)-1))
          >[x, 1; 3*x + 2, 1; 10*x + 9, 1]
          >
          >because he used primorial mode in NewPgen.
          >
          >David
          >
          >
          >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          >The Prime Pages : http://www.primepages.org/
          >
          >
          >
          >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
        • David Cleaver
          ... Phil, I have been keeping such a list and was going to offer up all my findings once I have found my next brilliant number. The program I used to do the
          Message 4 of 19 , Feb 1 11:26 AM
          • 0 Attachment
            Phil Carmody wrote:
            >
            > ... brilliant numbers. If someone has kept a full record of all the numbers
            > that were in the range they tested for brilliantness, then that would be a
            > fair corpus, surely? I'm assuming they weren't sieved terribly deeply, and
            > therefore only the medium sized factors would need to have been recorded, as
            > the small ones can be reproduced easily (hey, I'll offer to find all the
            > small factors to test my new factoring algorithm!). Sure they're smaller
            > than 200 digits by a factor of 2, but they're about as unbiased as you can
            > get, and there's a fair number of them.
            >
            > Anyone with such a collection?
            >
            > Phil
            >
            > =====
            > Is that free as in Willy or as in bird?

            Phil,

            I have been keeping such a list and was going to offer up all my
            findings once I have found my next brilliant number. The program I used
            to do the "sieving" was Miracl's factor.exe (slightly modified by me)
            and it does some ecm to remove up to 25 digit factors. So, would my
            list be too sparse to be useful? I didn't keep any of the sieved
            numbers, but everything that fell through that I have nfsx or ppsiqs
            factorings of.

            I was also thinking of giving the timings for the work thus far, and
            maybe also giving a list of the primes that were found in this range.
            Would either of the last two pieces of information be useful to anyone?
            I'm still compiling the information and still waiting for the next
            brilliant, but as soon as both are ready I'll e-mail the list.

            -David C.
          • David Broadhurst <d.broadhurst@open.ac.u
            ... I think that what you have so far cleaved/cleft/cloven is rather impressive and that the more you document it the better. Since the files are presumably
            Message 5 of 19 , Feb 1 11:59 AM
            • 0 Attachment
              David Cleaver asked:
              > So, would my list be too sparse to be useful?
              I think that what you have so far cleaved/cleft/cloven
              is rather impressive and that the more you document it
              the better. Since the files are presumably not huge,
              I can't see that Phil is going to fret if you
              create a "brilliant" folder in
              http://groups.yahoo.com/group/primenumbers/files/
              and add whatever you think might be informative therein.
              David
            Your message has been successfully submitted and would be delivered to recipients shortly.