20211209, 20:27  #56 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·29·113 Posts 
CPAP10 (121 digits)
New CPAP10 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 CPAP10 is that size cannot be large enough to patch all "holes" (in the 1881 positions, 66 holes are minimal by stage1 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 wellmodellable, and my estimate was that I will need 14.0 ('quasiCP')AP10 hits; luckily the reality was very near to the estimate. 
20211209, 21:25  #57 
Jan 2007
Germany
736_{8} Posts 
CPAP10
Wow, that was fast , congratulation Serge !!!
Site is updated: https://www.pzktupel.de/JensKruseAndersen/CPAP.htm An idea to find the smallest CPAP7 ?? It is also the first known googol CPAP10! greetings Last fiddled with by Cybertronic on 20211209 at 21:27 
20211209, 21:48  #58 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×29×113 Posts 
I'll ponder it.
_________________ A few more words about CPAP11 (based on CPAP10 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 nonzero and ten more residues are forbidden for each prime; in particular for CPAP10, x = 1 mod(11) (the only allowed resudie, so that one step before and one step after CPAP10, 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_{2}+x+n" (for example, this CPAP is in disguise k*257#*269+x+n, 263 is skipped; and this killed one more hole than equivalentlysized 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"78ish" 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 CPAP8910. the more higher p values we give up, the more holes open up. There will be no need to retune the x_{universal} seed search for every size. That's what I called stage1 preresearch in the earlier messages. I applied the same philosophy to CPAP11. 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 CPAP11 discussion) 
20211209, 22:25  #59  
"Robert Gerbicz"
Oct 2005
Hungary
3040_{8} Posts 
Quote:
Code:
? t=1;forprime(p=2,257,t*=p);x=1153762228327967262749742078637565852209646810567096822339169424875092523431859764709708315833909447378791; ? sum(i=0,9*210,gcd(res+i,t)==1)10 %51 = 69 ? Last fiddled with by R. Gerbicz on 20211209 at 22:26 

20211209, 22:28  #60 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10011001100111_{2} Posts 
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 692 = 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 115ish lead to nearly the same time effort. For low primorial range, AP10s pop up more frequently but one would need ~10^2 of them. And at 120digit size, rate of hits is slower, but you only need ME of 12.0 AP10s ( ME ~= 1 / (1p_{prime})^N_{holes} and from 100digit to 120digit 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 130digits and up, and the fact that you'd only need 4, 3 or even just 2 AP10 hits stops compensating for size^{10} trend. Here's my scrapworksheet from 3 weeks ago at the preplanning 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: 
20211210, 11:00  #61  
"Robert Gerbicz"
Oct 2005
Hungary
3040_{8} Posts 
Quote:
Code:
Record found: th_id=7; nc=64; rec=74 iteration=733668094 time=8038 sec;res=2419167755128732489596925401897421203775324274819447414938199577634806748818003387070777086520499840711323;m=251#*271*317=5520927690164777955047307880540963420397784189525372241470424483999917403653527565723982420249039338698610; Code:
? 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 

20211210, 17:39  #62  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·29·113 Posts 
Quote:
However, there is a wrinkle; that covering set is not allowed to kill _any_ of the 10 CPAPpositioned 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 CPAP9 but not for CPAP10  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 supersensitive to the deviation of 12 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 AP10s with 1, 2, 3 defects for longer than just 14 attempts; all a matter of luck. (One AP10 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.) 

20211210, 21:37  #63  
"Robert Gerbicz"
Oct 2005
Hungary
1568_{10} Posts 
Quote:
Code:
Record found: th_id=5; rec=9 iteration=291167407 it=47407 time=2837 sec;res=3239410289190426582065834981069503777767010327567828368221450072331609155637096750556623222154500106163060234382727523333428826240429413701585154748544659526294240266461735063483555729082257216891;m=457#*587*839*829=8947171094482520720610444905601995814587255662246159130691652504705462505844714330730062502048894728685321597692135810705741584947645300925487713309276543994343171905149273958372999915587164064490; Code:
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 I'm not that fast, it was an existing code, now allows to use 3 large primes (out of the order). 

20211210, 22:14  #64 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×29×113 Posts 
Ah, I meant full CPAP10 (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 CPAP9, yes. Interestingly you will get nearly the same result for CPAP10 as with CPAP9, because the last hole or two in the last 209er 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 AP10 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 tosieve, 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 CPAP11 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 some2000ish number of remaining holes to maybe 1020 less  and it is immaterial for making search faster. 
20211216, 20:16  #65 
"Robert Gerbicz"
Oct 2005
Hungary
2^{5}×7^{2} Posts 
Improving all solutions:
(res,m) for cpap9 using only 84 primes completely eliminating the holes for composites: Code:
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 Code:
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 Code:
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*(1p0)^count 1/pr/10^25 %17 = 625 ? %18 = 11 ? %19 = 297 ? %21 = 2.7754908747047876331527211281495045032 E26 ? %22 = 3.6029662684672455281572935962661205077 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 cpapeleven. 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...01013746.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 12%, 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 cpap10. Because there they would needed to test 3e15 numbers to get a single cpap10, 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. 
20220131, 19:12  #66 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·29·113 Posts 
CPAP5

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exponent Progression  storm5510  Information & Answers  15  20170726 18:02 
Bertrand's Theorem for Arithmetic Progression  literka  Math  0  20130601 12:42 
sieving primes in arithmetic progressions  maxal  Software  18  20101004 17:11 
nth prime number in an arithmetic progression  Unregistered  Information & Answers  1  20100404 22:06 
Arithmetic and Polynomial Progression of Primes?  drake2  Math  13  20061010 00:43 