Carol / Kynea Coordinated Search - Reservations

[rogue]

Originally Posted by Batalov

I noticed a kludge to get numbers > 30,000 digits (ostensibly, the default limit) proven:

Step 1. We can submit e.g. (40^40778+1)^2-2 -- as (40^40778+2)*40^40778-1
Step 2. Submit for PRP test. Because it has a ...-1 form, N+1 test is also run (or at least I thin this is how it happens).

Then we can query for (40^40778+1)^2-2 and because this is a shorter form it sticks. And it shows as a P.

Carol and Kynea forms can be proven with pfgw using -tp.

[axn]

Originally Posted by rogue

Carol and Kynea forms can be proven with pfgw using -tp.

Yes, of course. I (we?) are doing it ourselves to prove it.

But we want factordb to also record it and mark it as prime, and apparently factordb refuses to do N+1 proof for larger numbers. The only exception (and the basis for Serge's workaround) is if the number can be written in the literal form N+/-1 (presumably N should also be easily factorable to 33%), in which case factordb will automatically do the appropriate proof.

At least, that's how understood it from Serge's description.

[science_man_88]

Originally Posted by axn

Yes, of course. I (we?) are doing it ourselves to prove it.

But we want factordb to also record it and mark it as prime, and apparently factordb refuses to do N+1 proof for larger numbers. The only exception (and the basis for Serge's workaround) is if the number can be written in the literal form N+/-1 (presumably N should also be easily factorable to 33%), in which case factordb will automatically do the appropriate proof.

At least, that's how understood it from Serge's description.

and both the carol and kynea forms can be expressed as k*b^n+/-1 with k=b^n-2 and k=b^n+2 respectively.

[Batalov]

Yes, the kludge was to "convince" FactorDB to run N+1 test, --
or else it reports "Too large to test at the moment" when asked to 'Run N+1 proof' (even after helping it by factoring N+1 by throwing some "2 3 5 7 11" at it because otherwise it does not proceed to factor it even to its 'level 0').

[axn]

Status update:

b=12: searched till n <= 41k. no new primes.

b=18: searched till n <= 37k. no new primes.

continuing both.

[rogue]

I have updated the sieving code in the first post of the thread for two items. First, a "hack" to identify small primes. Instead of just removing them, it will warn you that it is possibly prime. Second, I found an issue with certain bases where it would fail immediately, such as base 42 and other bases divisible by 7. This does not impact any current sieving that you might be doing.

Thanks to everyone who has participated so far. I appreciate the support. I would challenge the group to see who finds the first Top 5000 prime of this form, but I think Serge would be the first. Since I'm stuck on base 2 for a while and as that base has a ways to go before finding a prime that fits into the Top 5000, it likely won't be me as I estimate it will take about 20 weeks to reach Top 5000 sizes for base 2. The larger the base, the fewer tests to get to to Top 5000. Although I did find the first mega-bit prime (2^520363-1)^2-2, maybe one of you will find the first mega-digit prime.

[rogue]

Completed to 550,000. No new primes and continuing.

[NorbSchneider]

Base 38 searched till n <= 25,000, no new PRPs,
continuing to n=70,000.

[rogue]

I'm updated the program so that it only works for p < 2^51 (for now). You can use with higher p (and it will work) but need use the x86_64 ARCH instead of the sse ARCH. This build should be about 30 to 35 percent faster. I'll get around to fixing it so that you can have the best of both worlds (faster for p < 2^51) and still support p > 2^51. Since nobody needs to sieve to 2^51 yet, this shouldn't cause any heartburn. Even with base 2 I'll finished before I reach 1e14, which is well below 2^51.

If I take the time to learn, I could write AVX assembler instructions and that should give an even better performance boost, but I still think that porting to a GPU would be the fastest.

Just changed 1.1.4 after realizing that some of the assembler routines weren't being called. It only adds about 3% to the speed, but every little bit counts.

[henryzz]

At first glance the asm was from sr2sieve. I have been mulling over making an avx version of some of that for a while. I think I should be able to do it when I have some decent time to put into it. Part of my problem is my PC isn't avx.
I am not certain how much speedup we will get as a fair few instructions are used setting up the vector multiplies. Avx might be better at that so there might be more speedup.
How is sr2sieve normally done? Some people will use above 51 bits occasionally for that.

[rogue]

Originally Posted by henryzz

At first glance the asm was from sr2sieve. I have been mulling over making an avx version of some of that for a while. I think I should be able to do it when I have some decent time to put into it. Part of my problem is my PC isn't avx.
I am not certain how much speedup we will get as a fair few instructions are used setting up the vector multiplies. Avx might be better at that so there might be more speedup.
How is sr2sieve normally done? Some people will use above 51 bits occasionally for that.

In sr1sieve/sr2sieve it is done in a very convoluted way. I don't intend to do it that way.