Carol / Kynea Coordinated Search - Reservations/Status
 

I've decided to start a new thread for a coordinated Carol / Kynea search. Carol and Kynea primes are a subset of what is known as [URL="http://mathworld.wolfram.com/Near-SquarePrime.html"]Near Square Primes[/URL]. These primes have the form of (b^n-1)^2-2 (Carol) and (b^n+1)^2-2 (Kynea). Steven Harvey has coordinated the search in the past and still coordinates the base 2 search [URL="http://harvey563.tripod.com/Carol_Kynea.txt"]here[/URL]. This thread is for those who want to search other bases. Although his page has some other bases on it, the page is incomplete and it is unknown to me if there are any gaps or if bugs might have causes previous searches to miss some primes.

I am already working on base 2 in another thread of the sub-forum and am coordinating that effort with Steven directly.

Odd bases can be skipped because the Carol/Kynea number is always even. I could modify the sieve to test (b^n+/-2)^2+/-1 for odd b, but that is for a different project somewhere down the road.

pfgw (for base 2) is about 15% faster than llr, so pfgw is recommended for testing this form at this time.
This form is supported by PRPNet, so you can find that elsewhere if you want to use it to distribute PRP testing.

Please post primes in [URL="http://www.mersenneforum.org/showthread.php?t=21251"]this thread[/URL].

[B]Please go to the Wiki [URL="https://www.rieselprime.de/ziki/Carol-Kynea_table"]here[/URL] to see a list of bases, primes, and current reservations. Karsten (kar_bon) is doing most of the updates. You may also create an account at the Wiki and make updates yourself.[/B]

Please continue to use this thread to submit and complete your reservations.

Attached are some sieving files available for testing. You may want to verify that they have been sufficiently sieved before beginning testing.

[STRIKE]Definitely interested in helping, but can't at the moment. I'll keep watching this space for updates so I can jump in later.[/STRIKE]

Screw it, I'll work on base 26 up to n=100,000

[QUOTE=wombatman;431684][STRIKE]Definitely interested in helping, but can't at the moment. I'll keep watching this space for updates so I can jump in later.[/STRIKE]

Screw it, I'll work on base 26 up to n=100,000[/QUOTE]

Thanks for joining.

Would you mind starting from n=1? I doubt it would take long to catch up to the range that was searched.

Is there any mathematical reason why smaller bases (12, 18, 20, 24, etc..) have not been searched?

[QUOTE=axn;431692]Is there any mathematical reason why smaller bases (12, 18, 20, 24, etc..) have not been searched?[/QUOTE]

None that I know of. You can search any even base. I would expect even base 4 to have some primes.

[QUOTE=rogue;431718]None that I know of. You can search any even base. I would expect even base 4 to have some primes.[/QUOTE]

Base 4 is covered by base 2 (since 4^n = 2^(2n)). Similarly, any perfect power will be covered by its base. So, 4,8,16,32,36,etc... need not be searched.

EDIT:- I'll work on base-12 to 50,000. I'll sieve base-18 to 100,000 but not sure how far I'm willing to test. Will know further once I'm done with base-12.

[QUOTE=axn;431719]Base 4 is covered by base 2 (since 4^n = 2^(2n)). Similarly, any perfect power will be covered by its base. So, 4,8,16,32,36,etc... need not be searched.[/QUOTE]

Duh!

I'll run bases 10 and 20 to 100k, and 30 and 40 to 70k for starters.

[QUOTE=rogue;431688]Thanks for joining.

Would you mind starting from n=1? I doubt it would take long to catch up to the range that was searched.[/QUOTE]

I'll let the current search (running to P=1e12) finish and then I'll run the range from n=1 up to where I started already.

Make sure you sieve deeply enough. For base 2, I'm continuing to sieve up to 1e13 and it is still removing factors at more than one an hour. Granted higher bases won't need to be sieved as deeply to find prime with the same number of bits for lower bases, but I wouldn't be surprised if most bases need to be sieved to at least 1e12.

hi,
I do like to reserve base=74
n=1 to 100000

hi,
I do like to reserve base=6
n=1 to 50000
for double checking

hi,
cksieve v1.1.0 gives out a warning - what does it means?
[CODE]
cksieve -P20e10 -i ck.in
cksieve 1.1.0 -- A sieve for Carol (b^n-1)^2-2 and Kynea (b^n+1)^2-2 numbers.
Read 16432 terms for (74^n+/-c)^2-2 from ABC file `ck.in'.
cksieve 1.1.0 started: 3 <= n <= 99999, 60000000000 <= p <= 200000000000
p=77153080019, 141204 p/sec, 150 factors, 12.3% done, 0 sec/factor, ETA 18 Apr 08:19
WARNING: 393216 is not a root (mod 77309411329)

p=81621680057, 141347 p/sec, 190 factors, 15.4% done, 0 sec/factor, ETA 18 Apr 08:19
[/CODE]

[QUOTE=lalera;431815]hi,
cksieve v1.1.0 gives out a warning - what does it means?
[CODE]
cksieve -P20e10 -i ck.in
cksieve 1.1.0 -- A sieve for Carol (b^n-1)^2-2 and Kynea (b^n+1)^2-2 numbers.
Read 16432 terms for (74^n+/-c)^2-2 from ABC file `ck.in'.
cksieve 1.1.0 started: 3 <= n <= 99999, 60000000000 <= p <= 200000000000
p=77153080019, 141204 p/sec, 150 factors, 12.3% done, 0 sec/factor, ETA 18 Apr 08:19
WARNING: 393216 is not a root (mod 77309411329)

p=81621680057, 141347 p/sec, 190 factors, 15.4% done, 0 sec/factor, ETA 18 Apr 08:19
[/CODE][/QUOTE]

There is a piece of code that finds x such at x^2 = 2 (mod p). Sometimes (and I mean rarely) it returns x where x^2 = -2 (mod p). I haven't looked into. Chances are well under 1 in a million that a factor is missed because of this.

Incidentally, that output also show another bug. The factor removal rate is always "0 sec/factor".

...and the ETA seems way off. Or it may be in the wrong timezone (but not UTC, as one could immediately expect).

[QUOTE=Batalov;431844]...and the ETA seems way off. Or it may be in the wrong timezone (but not UTC, as one could immediately expect).[/QUOTE]
ETA is fine. It is in local timezone. It is the p/sec that is quirky. I believe it is counting actual p's being processed, rather than the p-range being processed (i.e. if it crunched from p=1e9 to p=2e9, it counts it as pi(2e9)-pi(1e9) p's processed rather than a range of 1e9 processed).

[QUOTE=axn;431832]Incidentally, that output also show another bug. The factor removal rate is always "0 sec/factor".[/QUOTE]

I noticed that too. It shouldn't be too hard to fix.

[QUOTE=axn;431847]ETA is fine. It is in local timezone. It is the p/sec that is quirky. I believe it is counting actual p's being processed, rather than the p-range being processed (i.e. if it crunched from p=1e9 to p=2e9, it counts it as pi(2e9)-pi(1e9) p's processed rather than a range of 1e9 processed).[/QUOTE]

Correct. I treat "p/sec" as the number of primes tested per second not the size of the range sieved per second. If I were to use the latter, I wouldn't call it "p/sec" as that is misleading (IMO). ETA and removal rate should be all that one cares about.

In the first post I updated to fix the factor removal rate.

[QUOTE=axn;432017]All proven primes, and available in factordb (the larger ones apparently cannot be proven in factordb, even though N+1 is adequately factored).[/QUOTE]
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 [URL="http://factordb.com/index.php?id=1100000000834232306"](40^40778+1)^2-2[/URL] and because this is a shorter form it sticks. And it shows as a P.

[QUOTE=Batalov;432024]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 [URL="http://factordb.com/index.php?id=1100000000834232306"](40^40778+1)^2-2[/URL] and because this is a shorter form it sticks. And it shows as a P.[/QUOTE]

:tu: This is good to know. Nothing can be done about the ones already reported, but I will use this trick for any future finds.

[QUOTE=Batalov;432024]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 [URL="http://factordb.com/index.php?id=1100000000834232306"](40^40778+1)^2-2[/URL] and because this is a shorter form it sticks. And it shows as a P.[/QUOTE]

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

[QUOTE=rogue;432027]Carol and Kynea forms can be proven with pfgw using -tp.[/QUOTE]

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.

[QUOTE=axn;432030]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.[/QUOTE]

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.

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

Status update:

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

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

continuing both.

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.

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

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

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.

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.

[QUOTE=henryzz;432784]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.[/QUOTE]

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

I have filled in the tables for all bases less than 100 for n up to 1000. It was rather tedious. Hopefully I didn't make any mistakes.

hi,
please do reserve for me
base 70 and 72, n=1000 to 10000

[QUOTE=lalera;432942]hi,
please do reserve for me
base 70 and 72, n=1000 to 10000[/QUOTE]

Only 10,000? That could probably less than a day on a single core. I'll be curious to see how long it actually takes.

[QUOTE=rogue;432950]Only 10,000? That could probably less than a day on a single core. I'll be curious to see how long it actually takes.[/QUOTE]

I did it for base 24 in only a few hours(6ish not sure) on a slow PC.:smile:

hi,
please do reserve for me
b=70, n=10000 to 40000
b=72, n=10000 to 40000
b=76, n=1000 to 40000
b=78, n=1000 to 40000

hi,
please do reserve for me
b=92, n=1000 to 30000
b=94, n=1000 to 30000
b=96, n=1000 to 30000
b=98, n=1000 to 30000

hi,
please do reserve for me
b=80, n=1000 to 30000
b=82, n=1000 to 30000
b=84, n=1000 to 30000
b=86, n=1000 to 30000
b=88, n=1000 to 30000
b=90, n=1000 to 30000

hi,
please do reserve for me
b=66, n=1000 to 30000
b=68, n=1000 to 30000

hi,
i would like to get a list of valid bases for b=100 - 200
i want to do them to n=10000 - maybe higher

[QUOTE=lalera;433377]hi,
i would like to get a list of valid bases for b=100 - 200
i want to do them to n=10000 - maybe higher[/QUOTE]

IIRC, only 128 (2^7), 144 (12^2), and 196 (14^2) can be skipped in that range. Good luck.

[QUOTE=rogue;433385]IIRC, only 128 (2^7), 144 (12^2), and 196 (14^2) can be skipped in that range. Good luck.[/QUOTE]

thank you!

[QUOTE=lalera;433377]hi,
i would like to get a list of valid bases for b=100 - 200
i want to do them to n=10000 - maybe higher[/QUOTE]

100 (10^2) also should be skipped.

Base 12 completed to 50k. No new primes found (other than the one reported in the Prime thread). Unreserving.


Base 18 completed to 40k. No new primes. Unresereving. Here is a sieve file from 40k-100k. Sieved not too deep (3e11).

I'd quickly searched them just now. A list generated with GP was
[CODE]? forstep(b=2,2000,2,if(ispower(b)>1,next);q=0;for(n=1,400,if(ispseudoprime((b^n-1)^2-2),q=1;break);if(ispseudoprime((b^n+1)^2-2),q=1;break));if(!q,print1(" "b)))
368 640 688 926 970 982 1038 1270 1318 1388 1432 1452 1466 1468 1484 1614 1656 1852 1950 1992[/CODE]
and then I sieved the smaller ones (up to 1432) to n<=10000 and started pfgw. After a few minutes only b=640, 688, 1388 survived.

I guess, I will reserve b=640, 688 to n <= 30000 for starters, now.

hi,
please do reserve for me
base 28, n=1000 to 30000

Completed to n=600,000. No new primes and continuing.

hi,
please do reserve for me
b=60, n=1000 to 30000
b=62, n=1000 to 30000

hi,
dereserveing base 6

Complete to 625,000 and continuing. (2^621443+1)^2-2 is the only new prime and was reported in the other thread.

hi,
status update for carol / kynea
b=74, n=69000 to 78000
no prime
continuing

Completed to n=650,000. No new primes and continuing.

hi,
dereserveing base 74

[QUOTE=lalera;436270]hi,
dereserveing base 74[/QUOTE]

Did you stop at 78000?

[QUOTE=rogue;436274]Did you stop at 78000?[/QUOTE]
yes

Base 2 completed to n=675,000 and continuing. The primes (2^653490-1)^2-2 and (2^661478+1)^2-2) were already reported.

Completed base 2 to 700,000. The two found primes have ben reported. I need to do more sieving though. I'm at about 1e14 and am removing faster through sieving than PRP testing. There are close to 49,000 tests between n=700,000 and n=1,000,000 for this base.

A few of you haven't updated your reservation in a while. Could you please let me know your status?

BTW, I'm reserving base 1968.

Base 38 searched to n = 40,000, no new PRPs.
continuing to n = 50,000.

(120^12418-1)^2-2
(120^10856+1)^2-2

Tested to 20000

[QUOTE=WMHalsdorf;438516](120^12418-1)^2-2
(120^10856+1)^2-2

Tested to 20000[/QUOTE]

Are you going to test further or are you done?

[QUOTE=rogue;438520]Are you going to test further or are you done?[/QUOTE]

I plan on going to 25000 (just over 100k digits)

I'm still waiting for updates from Serge, Henry, and wombatman.

[QUOTE=rogue;438653]I'm still waiting for updates from Serge, Henry, and wombatman.[/QUOTE]

I will get to it when I am back in windows on that pc. I think a lot of my progress has been in sieving. I need to start testing again.

A little bit of overload IRL right now. I'll try to catch up next week - with the report.

[QUOTE=henryzz;438654]I will get to it when I am back in windows on that pc. I think a lot of my progress has been in sieving. I need to start testing again.[/QUOTE]

At 22k for base 24 currently. Fast progress is being made.

[QUOTE=henryzz;438819]At 22k for base 24 currently. Fast progress is being made.[/QUOTE]

Almost got to 31k before my hard disk stopped working. Count me as having reached 30k. Unreserving for now.

Still waiting for an update from Serge.

Base 2 searched to n=725,000 and continuing. No new primes.

Base 26 is at n=84,239. Will take it up to n=100k

(120^22918+1)^2-2
(120^42427-1)^2-2

Both tested to 44k will continue to 80k

I've completed base 2 to 750,000 and am suspending. I have a sieve file to to 1,000,000 that is sieved deeply enough.

I've completed base 1968 to 50,000 and am suspending. I have a sieve file to to 100,000 that is sieved deeply enough.

I need to focus my resources on cleaning up the Multifactorial mess. If anyone wants to use my files to continue those ranges let me know and I'll send you an ABC file.

Let me reserve base 2010, and I will start the sieve 1 <= n <= 100000
And will see how that goes. maybe I will get lucky on the long run and improve my [url]https://primes.utm.edu/primes/page.php?id=77385[/url]

[QUOTE=BotXXX;447704]Let me reserve base 2010, and I will start the sieve 1 <= n <= 100000
And will see how that goes. maybe I will get lucky on the long run and improve my [url]https://primes.utm.edu/primes/page.php?id=77385[/url][/QUOTE]

Good luck!

Base 2010 checked upto n = 10.000. Checking further up to 100.000.

Primes for 1 <= n <= 10.000 are all which are listed at [url]http://www.mersenneforum.org/showpost.php?p=447706&postcount=80[/url] (ie no new ones discovered since that post).

I would also like to reserve base 316.

Current status:
Base 316 checked upto n = 40.000
Base 2010 checked upto n = 40.000

Primes listed in [url]http://www.mersenneforum.org/showpost.php?p=454362&postcount=82[/url]

I would like to reserve base 50, for the range 1 <= n <= 50000, please.

[QUOTE=Dylan14;454960]I would like to reserve base 50, for the range 1 <= n <= 50000, please.[/QUOTE]

Thanks. Note that base 50 is done to 1000. That will save you a couple minutes of sieving and testing. :smile:

Base 50 to n = 50k is complete. The primes in this range are reported in the prime thread. I would like to continue working on this base to n = 100k, please.

Base 120 is complete to 80k

[QUOTE=WMHalsdorf;456875]Base 120 is complete to 80k[/QUOTE]

Are you done or are you continuing?

I would like to reserve base 252 up to n=10000.
Pre-thanks.

[QUOTE=vasyannyasha;457744]I would like to reserve base 252 up to n=10000.
Pre-thanks.[/QUOTE]

Thanks for joining.

[QUOTE=vasyannyasha;457744]I would like to reserve base 252 up to n=10000.
Pre-thanks.[/QUOTE]
...done
I would like to reserve base 252 to n=50000.
Pre-thanks.

Current status:
Base 316 checked upto n = 50.000
Base 2010 checked upto n = 50.000
No new primes discovered. Continuing my search.

Base 50 to n = 100k is complete. The primes have been posted to the prime thread, and I am releasing the base. I have a sieve file up to 120k for base 50 if anyone is interested (currently at p = 5.5 T).

Reserving bases 214 and 218 for the range 1 <= n <= 10000. Base 216 does not need to be searched, since it is a power of 6 (namely, 6^3).

Reserving bases 220 and 222 for the n range 1 <= n <= 10000. The previous reservations (for bases 214 and 218) are complete (see the prime thread for primes) and they are released.

Also, base 50 for n between 100-120k is now sieved to p = 6.7 T, it is available for whoever wants it.

In reference to [URL]http://www.mersenneforum.org/showpost.php?p=467873&postcount=108[/URL], I am reserving bases 228, 278, 290 and 326 to n = 10k. The previous reservations for bases 220 and 222 are complete and released.

Bases 228, 278, 290 and 326 are complete to n = 10k. Primes have been reported to the Carol/Kynea prime thread.
Since bases 228 and 278 have a Carol prime and base 326 has a Kynea prime, I am releasing those bases. I am extending the reservation of base 290 to n = 20k.

Base 290 has been searched to 20k. No primes were found from 10001 <= n <= 20000. I am releasing this base.

Hi!
I reserve 34 up to n=10k.
Pre-thanks

Base 34 done.
I reserve base 42 up to 10000
Pre-thanks

Base 42 done.

I reserve 290 to n=30000 and 46 to n=10000.
Pre-thanks

Base 48 and 52
 

I reserve base 48 and base 52 up to n=10000
Base 46 done.
Pre-thanks

Reserving base 720 from n = 1 to 10000.