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

Consecutive semi-primes

Expand Messages
  • Jens Kruse Andersen
    ... And the amazing twin record by Daniel Papp is 33218925*2^169690+/-1 with 51090 digits. This alone seems equivalent to 5.1^4=677 10k-digit solutions. The
    Message 1 of 5 , Feb 1, 2003
    • 0 Attachment
      David Broadhurst wrote January 23:
      > Thanks for the history, Jens.
      >
      > > Now I don't have to worry about proofs,
      > > I will search for a larger case of 3 consecutive semi-primes.
      >
      > Combining pairs of 5k-digit primes in x
      > a double-sieved attack on (x+2)/2 and (x+3)/3
      > at 10k digits looks feasible. After all,
      > it's only a time=O(digits^4) problem,
      > and there are already nearly 20 pairs of
      > gigantic twins.

      And the amazing twin record by Daniel Papp is 33218925*2^169690+/-1 with 51090
      digits. This alone seems equivalent to 5.1^4=677 10k-digit solutions. The
      multiplier is small and I only see 7 top 5000 primes with that exponent, so I
      guess he got very lucky.
      However, I enjoy to use my single PC for a lot of varying computational
      problems. I rarely let anything run for more than 2 weeks and I want a good
      success chance - I know this is not the way to fame and glory but I just like
      the satisfaction of reaching my target size, as long as it is not trivial.
      A 10k-digit semi-prime triplet looked like an expected 6 months with the
      generic prp in PrimeForm and the likely requirement for thousands of 5k-digit
      primes on a suitable primorial form. I settled for a modest 4k digits and just
      succeeded after a little bad luck.
      p=672066*4691#+1 and q=2329500*4691#+1 are primes.
      p * q, 2 * (pq+1)/2, 3 * (pq+2)/3 are 4021-digit semi-primes.
      I trial factored with my own program. All prp's and proofs were found with
      PrimeForm/GW.
      As David noted, the form gives 50% N-1 factorization of (pq+1)/2 and (pq+2)/3

      Hmm, I just noticed the prime triplet record is 4135 digits. Not exactly the
      same complexity with the right algorithm, but the target size should have been
      set to "beat" that. I will try to "beat" the twin record instead. I can
      combine primes from an old top 5000 for that. The heuristics for this problem
      do not require a primorial factor if there are hundreds of primes available.

      --
      Jens Kruse Andersen
    • David Broadhurst <d.broadhurst@open.ac.u
      Congrats, Jens, on your semi-primes. My taste is much as as yours: big enough to be a challenge, small enough to give a result in O(week). Incidentally the
      Message 2 of 5 , Feb 1, 2003
      • 0 Attachment
        Congrats, Jens, on your semi-primes. My taste is much as
        as yours: big enough to be a challenge, small enough to give
        a result in O(week). 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). 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.
        Best regards
        David
      • David Broadhurst <d.broadhurst@open.ac.u
        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
        Message 3 of 5 , Feb 1, 2003
        • 0 Attachment
          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.
        • 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 4 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 5 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.