- David Broadhurst wrote January 23:
> Thanks for the history, Jens.

And the amazing twin record by Daniel Papp is 33218925*2^169690+/-1 with 51090

>

> > 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.

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 - 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 - 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. - --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
> Congrats, Jens, on your semi-primes.

...

> I guess that your slowdown

In the world of sieving, Jens is one of the people to whom I doff my hat.

> was that your trial factoring was merely the -f option of Pfgw,

> whereas I handcrafted a sieve for the BLS-provable triplets.

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 - 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

"Not exactly" was a deliberate understatement. I know there is a huge

> digits was avoiding ECPP. But this was still an O(digits^5) problem,

> whereas yours was O(digits^4).

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.

Yes, I trial factored one pair at a time. My candidates were on the form

> 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.

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.

Thanks. However alt.math.recreational is not hard competition, at least before

> He stood out on alt.math.recreational because of his sieving ability.

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