Primes Arithmetic Progression (PAP) and CPAP

[Batalov]

New CPAP-10 record with 121 decimal digits size.

189382061960492204*257#+x106+210*n, n=0..9 (121 digits)
where x106=1153762228327967262749742078637565852209646810567096822339169424875092523431859764709708315833909447378791

P.S. The tough thing about CPAP-10 is that size cannot be large enough to patch all "holes" (in the 1881 positions, 66 holes are minimal by stage-1 careful choice of x106; with a choice of eight such values; this x106 happened to be the winner).
The Poisson selection of number of unwanted primes peeking through the 66 holes is well-modellable, and my estimate was that I will need 14.0 ('quasi-CP')AP-10 hits; luckily the reality was very near to the estimate.

[Cybertronic]

Wow, that was fast , congratulation Serge !!!
Site is updated: https://www.pzktupel.de/JensKruseAndersen/CPAP.htm

An idea to find the smallest CPAP-7 ??


It is also the first known googol CPAP-10!


greetings

[Batalov]

I'll ponder it.
_________________

A few more words about CPAP-11 (based on CPAP-10 experience).

I will add very little to past knowledge that it will require some novel and clever heuristics. I have written an optimizer of x addend for various "k*p#+x+n" forms for various p (which dictates range of search). This amounts to a multidimensional search in the 100+-ish array of residues (mod each p), combined with CRT chinese(). Obviously these are all non-zero and ten more residues are forbidden for each prime; in particular for CPAP-10, x = 1 mod(11) (the only allowed resudie, so that one step before and one step after CPAP-10, values are divisible by 11), for other primes mileage varies. That's the search space, -- and then you shake and bake, searching for the minimum of remaining holes, and using e.g. simulated annealing otherwise the search space is too large for direct enumeration (visiting every node of this graph).

I also included "k*p#*p₂+x+n" (for example, this CPAP is in disguise k*257#*269+x+n, 263 is skipped; and this killed one more hole than equivalently-sized k*263#+x+n).

I searched wide in space of a bounding high p, and as a byproduct i was able to improve on the legacy magic x253 (which used residues up to 569#). My best found universal seed (there are thousands equivalently good seeds 'x') is smaller and can be used for CPAP-"7-8-ish" without any later overhead because those 'x' values eliminate all holes. It is easy to sacrifice high p values one by one (and going down in size) and taking x_universal % chosen_lower_p# for CPAP-8-9-10. the more higher p values we give up, the more holes open up. There will be no need to re-tune the x_universal seed search for every size. That's what I called stage-1 pre-research in the earlier messages.

I applied the same philosophy to CPAP-11. Optimization is not gaining much there, and there are still near two thousand holes at e.g. 97# chosen level.

(... to be continued, esp only now arriving to CPAP-11 discussion)

[R. Gerbicz]

Originally Posted by Batalov

New CPAP-10 record with 121 decimal digits size.

189382061960492204*257#+x106+210*n, n=0..9 (121 digits)
where x106=1153762228327967262749742078637565852209646810567096822339169424875092523431859764709708315833909447378791

P.S. The tough thing about CPAP-10 is that size cannot be large enough to patch all "holes" (in the 1881 positions, 66 holes are minimal by stage-1 careful choice of x106; with a choice of eight such values; this x106 happened to be the winner).
The Poisson selection of number of unwanted primes peeking through the 66 holes is well-modellable, and my estimate was that I will need 12 ('quasi-CP')AP-10 hits; luckily the reality was very near to the estimate.

Should not be that 69 holes ??

? t=1;forprime(p=2,257,t*=p);x=1153762228327967262749742078637565852209646810567096822339169424875092523431859764709708315833909447378791;
? sum(i=0,9*210,gcd(res+i,t)==1)-10
%51 = 69
?

[Batalov]

Originally Posted by R. Gerbicz

Should not be that 69 holes ??

It would have been (for 257#), but like I said, 269 is used on top of that and removes exactly 3. (set t=269 in your script and done).
263# can only remove 69-2 = 67.

Curiously this is how I chose the size to aim at. These are the last values that keep removing 3 holes; after that each next prime in primorial removes 2, and later just one for the last few primes (which are at those last stages trivial to pick; the only better outcome would be to remove two holes, but they can't.)

One would not expect it, but the practical implementation for search between sizes of 100 digit and 115-ish lead to nearly the same time effort. For low primorial range, AP-10s pop up more frequently but one would need ~10^2 of them. And at 120-digit size, rate of hits is slower, but you only need ME of 12.0 AP-10s ( ME ~= 1 / (1-p_prime)^N_holes and from 100-digit to 120-digit p_prime inches down from ~5% to 4%; that is because inevitably "holes" are naturally presieved as well by having p# in them). The 'wanted' 10 primes are sieved deeper (but only as deep as it takes the same to PRP them).
So the compound ME of necessary work first stays nearly flat, and then takes of at 130-digits and up, and the fact that you'd only need 4, 3 or even just 2 AP-10 hits stops compensating for size¹⁰ trend.

Here's my scrap-worksheet from 3 weeks ago at the pre-planning stage. Row 55 is highlighted as chosen (footnote 'alt' means that a variation with using next prime, i.e. 269 is used for best gain); the bottom of the worksheet also shows that now at 467#*487 we can eliminate all holes with a wide choice of x213's:

[R. Gerbicz]

Originally Posted by Batalov

It would have been (for 257#), but like I said, 269 is used on top of that and removes exactly 3. (set t=269 in your script and done).

OK, so your best is 66 holes (and what was used to find your cpap-10) when the m (the step) is divisible by (exactly) primepi(257)+1=56 primes, it isn't that super useful because killing 1-2 numbers doesn't help the search too much, but you can reach 64 holes:

Record found: th_id=7; nc=64; rec=74 iteration=733668094 time=8038 sec;res=2419167755128732489596925401897421203775324274819447414938199577634806748818003387070777086520499840711323;m=251#*271*317=5520927690164777955047307880540963420397784189525372241470424483999917403653527565723982420249039338698610;

this gives rec-10=64 holes (nc has a different meaning), just to confirm:

? res=2419167755128732489596925401897421203775324274819447414938199577634806748818003387070777086520499840711323;
? m=1;forprime(p=2,251,m*=p);m*=271*317;
? sum(i=0,9*210,gcd(res+i,m)==1)-10
%3 = 64
? omega(m)
%4 = 56

[Batalov]

Originally Posted by R. Gerbicz

OK, so your best is 66 holes (and what was used to find your cpap-10) when the m (the step) is divisible by (exactly) primepi(257)+1=56 primes, it isn't that super useful because killing 1-2 numbers doesn't help the search too much, but you can reach 64 holes:

Excellent, thanks! You gathered the gist of this problem precisely. (if simplified, it could make for a good 'Ponder this' or a EulerProject quiz problem.)

However, there is a wrinkle; that covering set is not allowed to kill _any_ of the 10 CPAP-positioned future primes (offset%210==0). Did you include this restriction?* Let me give you an example: the favorite x253 (back from J.K.Andersen searches) works for CPAP-9 but not for CPAP-10 - it kill the 10th position with 41. That is one of the reasons that I had to refactor the x253 and not just cut it down to size by simple "% some_p#"; of course I could rotate that x253 res around 41 and I did, and then got interested to shake all of them.
*I think that you did - your res doesn't hit the 10 protected numbers. Super.

And makes sense, because my search was not exhaustive in space of noncontiguous prime sets and as because cost function is not super-sensitive to the deviation of 1-2 holes (it just help by a few percent, at this size ~4% each). And the cost function is just the ME but I was prepared to search and keep getting AP-10s with 1, 2, 3 defects for longer than just 14 attempts; all a matter of luck. (One AP-10 managed to bring with it 7 defects, even though the mode was expected to be ~3. Poisson process is a cruel mistress.)

Your result is very neat. I am sure that you can improve on my upper boundary (bottom of the scrapbook), as well - the full covering set, perhaps with 90 primes? (J.K.Andersen's x253 was using 104, up to 569#; my limited simulated annealing reached 92, I think.)

[R. Gerbicz]

Originally Posted by Batalov

Your result is very neat. I am sure that you can improve on my upper boundary (bottom of the scrapbook), as well - the full covering set, perhaps with 90 primes? (J.K.Andersen's x253 was using 104, up to 569#; my limited simulated annealing reached 92, I think.)

In less than 1 hour:

Record found: th_id=5; rec=9 iteration=291167407 it=47407 time=2837 sec;res=3239410289190426582065834981069503777767010327567828368221450072331609155637096750556623222154500106163060234382727523333428826240429413701585154748544659526294240266461735063483555729082257216891;m=457#*587*839*829=8947171094482520720610444905601995814587255662246159130691652504705462505844714330730062502048894728685321597692135810705741584947645300925487713309276543994343171905149273958372999915587164064490;

it is using only 91 primes, fully eliminates all 8*210-9 numbers (leaving only the 9 spots for the primes), just reworked the two large primes in m (they eliminate only one numbers) to give smaller m:

res=1421202324329848223641491401426751845184269260571736360806467505095088875500611881228902064898968824830424578196878794962469612573094629531345136888416103706650763632653157402533411268132513020921;
m=1;forprime(p=2,463,m*=p);m*=587;
? ? 
? sum(i=0,8*210,gcd(res+i,m)==1)-9
%3 = 0
? sum(i=0,8,gcd(res+210*i,m)==1)
%4 = 9
? omega(m)
%5 = 91

ps. yes checking that we won't sieve out the res+210*i positions, and using a fixed length of interval (say 8*210).
I'm not that fast, it was an existing code, now allows to use 3 large primes (out of the order).

[Batalov]

Ah, I meant full CPAP-10 (suppose we had huge compute resources and they wouldn't be an issue; and suppose we wanted a perfect smallest magic x).*

J.K.A's x253 was for the CPAP-9, yes.

Interestingly you will get nearly the same result for CPAP-10 as with CPAP-9, because the last hole or two in the last 209-er range is easy to be hit with a (what do they call it in chess?) "a fork", -- meaning if we have last two holes, we can kill them with some picked last higher prime both.

*Also, practically, of course we don't totally need to plug all of them. 409# is a good level, and we'd need only 1.5 AP-10 hits. 409# is a good level for another reason too. With pfgw, next level is suddenly 10x slower to test. the reason is that below GMP is used (but then again, I can hack PFGW to keep using GMP longer still. Or, - what I implemented in reality was that I stopped using PFGW external- to-sieve, instead I call GMP is_probab_prime_p() inside sieve when sieving is done.
I'd put a "toy" PFGW inside the sieve, then optimized for L3 cache and total runtime per chunk. And the latter means running tons of them at the same time; it is easy to write a sieve that runs very fast and then when run with 47 siblings it grinds to a halt because all L3 cache is used right away; so the art is to go in small chunks that fit L2 and spill just enough to get the last boost into L3.)
___________

Now, what I started to write above about CPAP-11 is that, given all the toolset that we now created, does it help? Well, not really because there all the optimization brings number of holes from some-2000-ish number of remaining holes to maybe 10-20 less - and it is immaterial for making search faster.

[R. Gerbicz]

Improving all solutions:
(res,m) for cpap-9 using only 84 primes completely eliminating the holes for composites:

Record found: th_id=6; rec=9 iteration=60708 it=10708 ii=0 time=68 sec;res=161925624061213598311320945936652149619611228904800382078477140334981400578415814587128896116969071847948774653886033332671824594192370499495710805482458595716596656297012880193;m=359#*367*439*373*379*419*383*509*389*397*401*409*421=657532915701052664076023862262275456042643486667271911649995920181140246719307835166720716075588191829357285486121975311770952205586059310371275678163196371211228378857970084890;

res=161925624061213598311320945936652149619611228904800382078477140334981400578415814587128896116969071847948774653886033332671824594192370499495710805482458595716596656297012880193;m=1;forprime(p=2,421,m*=p);m*=439*509;
count=sum(i=0,8*210,gcd(res+i,m)==1)-9
sum(i=0,8,gcd(res+210*i,m)==1)
omega(m)
? %7 = 0
? %8 = 9
? %9 = 84

(res,m) on cpap-10 using omega(m)=56 primes and leaving only 63 holes for composites.

Record found: th_id=7; rec=73 iteration=1 it=1 ii=0 time=0 sec;res=6378750995709123277164536971759649750665348074107740992880185971291283678447159066244129706414082270910601;m=199#*307*251*211*263*229*233*227*271*269*409=12044886230263071772311575755582577459657753956075505638485480179186031225934262196870061784975021112927690;

res=6378750995709123277164536971759649750665348074107740992880185971291283678447159066244129706414082270910601;
m=1;forprime(p=2,211,m*=p);m*=307*251*263*229*233*227*271*269*409;
count=sum(i=0,9*210,gcd(res+i,m)==1)-10
sum(i=0,9,gcd(res+210*i,m)==1)
omega(m)
? %3 = 63
? %4 = 10
? %5 = 56

An interesting res,m candidate after a deep search for cpap-11 using omega(m)=297 (my main searches initially used omega(m)=295, it is only a minor hack):

Record found: th_id=2; rec=636 iteration=3 it=3 ii=0 time=0 sec;res=7529146232237445898667605657937124071520344956338643577766362943840036712482329640337303489394909379342891672333310655527958188671776973615341917208465500521802450798983841225677632398073638704593849876108982692652191747146126844449766710734420091854799886848315934791787641568709561477610452133137798875241506470810359731768578693467861717546008945639539837528937418123410399728518902566076733188886376603756276146258994350664738568540498722140594663171998675578458588084427338965108994412034123243071583323561300446038127514633511103957764750291374875284976859560759498979065271347318641614225608262583318156160500349464103284715688448833567754690121997670072859214643102511883716658020511372759752421425677225257796027228811414260553364855127838641872466454696496339118665998258904175111151317222187079678902931290519887;m=1867#*2251*2063*2609*2069*1987*2213*2099*2027*2297*2239*1913*1997=18797013775920469064906097339814990319147833179459483188483464449288136974283270808974418301145287031693169531696352630946797958103208036067420105397029938953755350842554915648196180999109296709237069391660500919641721631827501072439059778813589609472062377597950611062603433958496528416992370115926115435914803110472576384204241203277255228686535565886118431691694404870401684702776184230001278931070834303646602895361551209617271361675387690898668963304675250534519145757279181108860314075703064460844770287148907711762994765217023326947746468939575559724878964751989313287877326320440997664166246858468803218223580683760538971359571973968951728884671227841792566480094290152373052538557724308361501901717312689118553393743297525818179040050395565188409270082491066091813751078442174597354346395952287528961672165860471270;

res=7529146232237445898667605657937124071520344956338643577766362943840036712482329640337303489394909379342891672333310655527958188671776973615341917208465500521802450798983841225677632398073638704593849876108982692652191747146126844449766710734420091854799886848315934791787641568709561477610452133137798875241506470810359731768578693467861717546008945639539837528937418123410399728518902566076733188886376603756276146258994350664738568540498722140594663171998675578458588084427338965108994412034123243071583323561300446038127514633511103957764750291374875284976859560759498979065271347318641614225608262583318156160500349464103284715688448833567754690121997670072859214643102511883716658020511372759752421425677225257796027228811414260553364855127838641872466454696496339118665998258904175111151317222187079678902931290519887;m=1;forprime(p=2,1867,m*=p);m*=2251*2063*2609*2069*1987*2213*2099*2027*2297*2239*1913*1997;
count=sum(i=0,10*2310,gcd(res+i,m)==1)-11
sum(i=0,10,gcd(res+2310*i,m)==1)
omega(m)
p0=m/eulerphi(m)/log(m);
pr=p0^11*(1-p0)^count
1/pr/10^25
%17 = 625
? %18 = 11
? %19 = 297
? %21 = 2.7754908747047876331527211281495045032 E-26
? %22 = 3.6029662684672455281572935962661205077

Just to appreciate this: with random swappings you could get "only" 740-750 holes starting from a random res, and improving that.

That is in average you need 3.6029*10^25 k values to find a single k for that res+k*m+2310*i for i=0..10 is a cpap-eleven.
m has only 824 digits, so we could get a solution in the p~850 digits range lower than the expected optimal 910 digits in https://www.ams.org/journals/mcom/20...01-01374-6.pdf .
optimal omega(m) could be a little different from this, solutions for omega(m)=285..305 range are very close to each other, roughly within 1-2%, what is a change equivalent to 3 composite places for a given res,m pair.

Still not that super freindly number, but surprisingly refutes the claim from the above paper that it is a trillion times slower what was a cpap-10. Because there they would needed to test 3e15 numbers to get a single cpap-10, so the difference is roughly 12 billion times harder, as you can easily hide (with some time penalty) the prp cost with a little "oversieving", so it doesn't matter that here we have much larger ~850 digits numbers. Even with sieving only up to 2^32, what you can do a cache freindly way you would get ~6800 surviving k for a billion length interval. If you could sieve a billion numbers (and prp the survivors) in 1 sec, then you need 1.1 billion cpu years. (sieving on cpu and prp testing on gpu is the easier way).
Maybe within 40 years we will see a solution.

ps.
Timings are a joke, all of them came from different very good solutions.
A little slowdown comes from the fact that you need to use much larger k value at the end in the range of 1e25, so you get primes at a lower rate, but composites between them at a higher rate, the overall effect is a little slowdown, what you could roughly halve if you change res say at every trillion values, what could be real: just modify the res%p at some places and allow say at most opt+3=628 composite places, to avoid duplicate work, maybe fix m, and regard different res values.

[Batalov]

New largest CPAP-5 -

2738129459017*4211#+3399421517+30*n, n=0..4 (1805 digits)