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

Re: [PrimeNumbers] Re: Consecutive semi-primes

Expand Messages
  • Phil Carmody
    ... In the world of sieving, Jens is one of the people to whom I doff my hat. He stood out on alt.math.recreational because of his sieving ability. Phil =====
    Message 1 of 5 , Feb 2, 2003
    • 0 Attachment
      --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
      > Congrats, Jens, on your semi-primes.
      ...
      > I guess that your slowdown
      > was that your trial factoring was merely the -f option of Pfgw,
      > whereas I handcrafted a sieve for the BLS-provable triplets.

      In the world of sieving, Jens is one of the people to whom I doff my hat.
      He stood out on alt.math.recreational because of his sieving ability.

      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
    • Jens Kruse Andersen
      ... Not exactly was a deliberate understatement. I know there is a huge difference and it makes little sense to compare sizes, except for fun. The wrong
      Message 2 of 5 , Feb 2, 2003
      • 0 Attachment
        About prime and semi-prime tuples I wrote:
        > Not exactly the same complexity with the right algorithm

        David Broadhurst wrote:
        > Incidentally the real breakthrough for the prime triplet record is 4135
        > digits was avoiding ECPP. But this was still an O(digits^5) problem,
        > whereas yours was O(digits^4).

        "Not exactly" was a deliberate understatement. I know there is a huge
        difference and it makes little sense to compare sizes, except for fun. The
        "wrong" algorithm for k consecutive numbers with the same number of prime
        factors (used for a 7-tuple with 3 prime factors by Phil, who admitted to
        being sloppy) is: Search k simultaneous prime cofactors, e.g. x/5, (x+1)/2,
        (x+2)/3. This was also the suggestion of others in alt.math.recreational and
        would give the normal prime tuple complexity O(k+2).

        David Broadhurst wrote:
        > PS: I re-read saw that you did your own trial factoring, sorry.
        > But I guess that it was not truly a sieve, but just for
        > one pair at a time? Mind you it's not easy to see a way
        > round that. If anyone could sieve this two-parameter
        > input problem, it would be Phil.

        Yes, I trial factored one pair at a time. My candidates were on the form
        p*q = (c*6*4691#+1) * (d*6*4691#+1)
        This (including the 6) prevents factors below 4691 in both (pq+1)/2 and
        (pq+2)/3.
        I precomputed an array of 6*4691# mod (primes<10^8).
        Then I could quickly trial factor each pair from 4691 to 10^8 (a high limit
        for individual trial on 4k-digits with a 2.7s prp test) using only 32-bit
        inline assembler instructions on c and d.
        I thought about sieve possibilities but it seemed hard and with a few days
        expectation, I dropped it. I would have given the 10k-digit problem more
        thought.

        I should also admit that I was a lot more lazy for p = (c*6*4691#+1). This is
        a good sieve form and it turned out I needed 1314 primes (bad luck), but I
        used pfgw's trial factoring for this. Later I discovered the NewPGen check box
        "use primorial mode" in plain sight. I had only looked through the type
        selection box... When it opens it actually covers the primorial box and I
        thought there was only k*b^n something available. Why didn't Paul Jobling put
        a hint in the type box for people like me with tunnel vision :-)
        Never underestimate the potential for stupidity among software users.

        Phil Carmody wrote:
        > In the world of sieving, Jens is one of the people to whom I doff my hat.
        > He stood out on alt.math.recreational because of his sieving ability.

        Thanks. However alt.math.recreational is not hard competition, at least before
        you joined it. You are the better siever and I have only beaten your speed a
        couple of times (including the prime puzzles) by spending much more time on
        special-purpose programs. GenSv seems impressive for such a generic sieve.

        --
        Jens Kruse Andersen
      Your message has been successfully submitted and would be delivered to recipients shortly.