mersenneforum.org Software for finding prime constellations
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-25, 12:50 #12 ATH Einyen     Dec 2003 Denmark 2·17·101 Posts My programs tend to be very messy, so I'll just explain in pseudocode how I trial factor in a test program I made. For example this 19-tuple pattern: p=[0 4 6 10 16 18 24 28 30 34 40 46 48 54 58 60 66 70 76] where the first p is: p=217153 (modulo 510510). I choose a starting point and find the nearest n=217153+76 (modulo 510510), because I use the last prime in the 19-tuple pattern, and then I want to check n+k*510510 for k>=0. So I create a bitset array of k-values to sieve with a size around 1M-2M which seemed most efficient. If a sieving prime divides any one of the 19 prime pattern positions I can exclude this k-value from the array as well as every p'th k-value from this first value: k +c*p for c>=0. Since 510510 = 17# I starting sieving at p=19. Code: for p=19 to sievelimit; p=nextprime { a:=n%p b:=510510%p for k=0 to k

=0 can be reset in the array, because p divides this pattern position in each of them. for j=k to j<=bitsetsize and j=j+p reset bitset[j] break No need to check rest of i values once I found one. a=(a+b)%p } Since I trial factor all 19 different positions in the pattern, the k-values are quickly eliminated, and I only need to trial factor up to like around p=59-83 until there are very few valid k-values left to PRP. Then I PRP the rest of the k-candidates starting from the front or back of the 19-tuple pattern for each k-value. As soon as a composite is found, the current k-value can be skipped, so most k-values requires only 1 or a few PRP tests. Last fiddled with by ATH on 2022-08-25 at 13:09

 2022-08-25, 17:31 #13 Puzzle-Peter     Jun 2009 70010 Posts Robert Gerbizc's Polysieve was not originally written for this kind of stuff, but it can handle these problems using the right input and it can be customized to do it more easily. Not sure about performance at k=19 compared with the code the record holders used but it was good enough for a record at k=12.
 2022-08-26, 12:36 #14 Cybertronic     Jan 2007 Germany 10011010112 Posts 19-tuplet This unknown prime 19-tuplet is very hard. I found with my 2 PCs this smallest prime 17-tuplet 1341829940444122313597407 + d, d = 0, 4, 10, 12, 16, 22, 24, 30, 36, 40, 42, 46, 52, 54, 60, 64, 66 after 3 weeks or so. The offset is 3.4e23. I believe, to reach this offset for 19-tuplet is 10x faster...~2 days, or 1.5e24 per month (or an offset with 6e17+ per sec). My estimation for the 1st one is 5*10^26 or 330 months (27 years). 100 PCs should be found it in 180 days Last fiddled with by Cybertronic on 2022-08-26 at 12:56
 2022-08-26, 15:21 #15 User140242   Jul 2022 3×23 Posts With this code fixed the number of elements and the delta max finds evential k-tuples less than n. To find any k-tuples with elements in two consecutive search blocks it is necessary to increase the wheel from 210 to 2310 in the input values. Code: #include #include #include #include #include #include #include const int64_t PrimesBase[5]={2,3,5,7,11}; const int64_t n_PB_max = 5; const int64_t del_bit[8] = { ~(1 << 0),~(1 << 1),~(1 << 2),~(1 << 3), ~(1 << 4),~(1 << 5),~(1 << 6),~(1 << 7) }; const int64_t bit_count[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; int64_t Euclidean_Diophantine( int64_t coeff_a, int64_t coeff_b) { // return y in Diophantine equation coeff_a x + coeff_b y = 1 int64_t k=1; std::vector div_t; std::vector rem_t; std::vector coeff_t; div_t.push_back(coeff_a); rem_t.push_back(coeff_b); coeff_t.push_back((int64_t)0); div_t.push_back((int64_t)div_t[0]/rem_t[0]); rem_t.push_back((int64_t)div_t[0]%rem_t[0]); coeff_t.push_back((int64_t)0); while (rem_t[k]>1) { k=k+1; div_t.push_back((int64_t)rem_t[k-2]/rem_t[k-1]); rem_t.push_back((int64_t)rem_t[k-2]%rem_t[k-1]); coeff_t.push_back((int64_t)0); } k=k-1; coeff_t[k]=-div_t[k+1]; if (k>0) coeff_t[k-1]=(int64_t)1; while (k > 1) { k=k-1; coeff_t[k-1]=coeff_t[k+1]; coeff_t[k]+=(int64_t)(coeff_t[k+1]*(-div_t[k+1])); } if (k==1) return (int64_t)(coeff_t[k-1]+coeff_t[k]*(-div_t[k])); else return (int64_t)(coeff_t[0]); } void segmented_bit_sieve_wheel(uint64_t n,int64_t max_bW,int64_t num_c,int64_t delta_max) { int64_t sqrt_n = (int64_t) std::sqrt(n); int64_t n_PB=(int64_t)3; int64_t bW=(int64_t)30; //get bW base wheel equal to p1*p2*...*pn <=max_bW with n=n_PB while(n_PB1+PrimesBase[n_PB-1]){ int64_t k_end = (n < bW) ? (int64_t)2 :(int64_t) (n/(uint64_t)bW+1); int64_t k_sqrt = (int64_t) std::sqrt(k_end/bW)+1; //find possible remainder of base module std::vector Remainder_i_t(bW+1,true); for (int64_t i=0; i< n_PB;i++) for (int64_t j=PrimesBase[i]*PrimesBase[i];j< bW+1;j+=PrimesBase[i]) Remainder_i_t[j]=false; std::vector RW; for (int64_t j=PrimesBase[n_PB-1]+1;j< bW+1;j++) if (Remainder_i_t[j]==true) RW.push_back(-bW+j); RW.push_back(1); int64_t nR=RW.size(); std::vector P_c(nR,0); std::vector C1(nR*nR); std::vector C2(nR*nR); for (int64_t j=0; j1) rW_t-=bW; C1[nR*i+j]=rW_t+RW[j]; C2[nR*i+j]=(int64_t)(rW_t*RW[j])/bW+1; if (i==nR-1) C2[nR*i+j]-=1; } } C2[nR*j+nR-2]=(int64_t)1; C1[nR*j+nR-2]=-(bW+RW[j])-1; C1[nR*j+nR-1]=RW[j]+1; C2[nR*j+nR-1]=(int64_t)0; } for (int64_t i=nR-2; i Primes(nB+segment_size_b, 0xff); std::vector Segment_i(nB+segment_size_b, 0xff); int64_t pb,mb,mmin,ib,i,jb,j,k,kb; int64_t kmax = (int64_t) std::sqrt(segment_size/bW)+(int64_t)1; for (k =(int64_t)1; k <= kmax; k++) { kb=k*nB; for (jb = 0; jb=(int64_t)0; mb +=pb ) Primes[mb+ib] &= del_bit[i]; if (pbsegment_size) { mb-=segment_size_b; while (mb<(int8_t)0) mb+=pb; for (; mb <= segment_size_b; mb +=pb ) Segment_i[mb+ib] &= del_bit[i]; } } } } } } } for (int64_t kc = 1; kc < std::min (segment_size+1,k_end); kc++) { int64_t count_p=0; for (int64_t ic = 0; ic=num_c) { int64_t i_P_c=0; for (int64_t ic = 0; icsegment_size) { int64_t k_low,kb_low; std::vector Segment_t(nB+segment_size_b); for (int64_t k_low = segment_size; k_low < k_end; k_low += segment_size) { kb_low=k_low*nB; for (kb = (int64_t)0; kb <(nB+segment_size_b); kb++) Segment_t[kb]=Segment_i[kb]; kmax=(std::min(segment_size,(int64_t)std::sqrt((k_low+segment_size)/bW)+2)); j=p_mask_i; for(k=(int64_t)1; k<=kmax;k++) { kb=k*nB; for (jb = 0; jb=num_c) { int64_t i_P_c=0; for (int64_t ic = 0; ic
 2022-08-27, 10:08 #16 User140242   Jul 2022 10001012 Posts In reference to the code in post #15 I want to specify that I have only modified a sieve that I had made to count the prime numbers. In theory it works for n<2^63 and maybe for n<2^64 if you change std::vectorP_c(nR, 0); in std::vectorP_c (nR, 0); but for such large n is slow, you have to use multithreading. I am not an expert and I do not have the necessary experience but I think you can make m different blocks for multithreading in the second part of the code, using m different Segment_t vectors and increasing for each block k_low by m*segment_size. It is also possible to increase the size of the wheel by adding prime numbers to PrimesBase the problem is that for p>13 the size (number of classes)^2 of the arrays C1 and C2 becomes too large, you have to modify the code a little to use two vectors of size (number of classes) to be calculated from time to time for each single class used and this decreases the speed. Although by increasing the size of the wheel it is possible to reach higher values of n because the algorithm works with numbers smaller than max(sqrt(n),n/bW) and by increasing bW it is possible to increase n always modifying the code and entering sqrt(n) and n/bW as input. Last fiddled with by User140242 on 2022-08-27 at 10:28
2022-08-27, 10:23   #17
ATH
Einyen

Dec 2003
Denmark

343410 Posts

Quote:
 Originally Posted by Cybertronic I believe, to reach this offset for 19-tuplet is 10x faster...~2 days, or 1.5e24 per month (or an offset with 6e17+ per sec).
How would you get 6e17+ per sec? On many cores or on GPU or do you have a highly optimized assembly program for this?

On 1 core on a very old 5960X corei7 I'm getting 6.3e13 per sec. I know my program is pretty basic without assembly, but I was expecting a very good program to be 10x to 100x faster at most, not 10000x faster.

2022-08-27, 10:42   #18
Cybertronic

Jan 2007
Germany

26B16 Posts

Quote:
 Originally Posted by ATH How would you get 6e17+ per sec? On many cores or on GPU or do you have a highly optimized assembly program for this? On 1 core on a very old 5960X corei7 I'm getting 6.3e13 per sec. I know my program is pretty basic without assembly, but I was expecting a very good program to be 10x to 100x faster at most, not 10000x faster.

Okay, forgot to say 6e17 (or more) is on 32 threads (two Ryzen 7 1700 @3GHz, round 3e16 per core and sec,without SMT.).
This target runs with 53# blocksize under my sparse freebasic code....note, I'm not a programming expert.
The searching is systematic with all 32 threads simultaneous...for this task I use an offset-range of 53#*2000=6.5e22...tooks maybe a day or so.

BTW, here is my german k-tuplet thread on "Matroids Matheplanet", 12 pages, there are a lot of running informations.

https://matheplanet.de/matheplanet/n...232720&start=0

I can try to recode the 17-tuplet for this special 19-tuplet ..so I have the exact rate/s. I have not try this yet.

After I found the smallest 7k triplet 2nd kind, I will look for the smallest 55-digit prime 12-tuplet. This will take 1 week to reach an offset 1e21.

Last fiddled with by Cybertronic on 2022-08-27 at 11:03

 2022-08-27, 14:37 #19 Cybertronic     Jan 2007 Germany 619 Posts 19tuplet code Testsieve is done. Pattern: d=00,04,06,10,12,16,24,30,34,40,42,46,52,54,60,66,70,72,76 I get per core 3.36e16 / s [ 1e18/s ! with 32 threads] . The program works in cycles and one is done in 11.2 days with complete offset up to 32589158477190044730000 Deep sieving max. p<48000 My estimation is one 19-tuplet ~3000 cycles. So ~10 days with 3000 cores. RAM in using 50MB per task. Even I found: 14 / 19 conditions are prime 28026688763307365621377 12 / 19 conditions are prime 15642812740222210642987 9 / 19 conditions are prime 20107537050380847377197 11 / 19 conditions are prime 3128586964390514346607 Last fiddled with by Cybertronic on 2022-08-27 at 14:52
 2022-08-27, 16:34 #20 Cybertronic     Jan 2007 Germany 11538 Posts I wrote on my page: k=19 s=76 B={0 4 6 10 12 16 24 30 34 40 42 46 52 54 60 66 70 72 76} smallest is unknown But one is known ! 622803914376064301858782434517 + d, d = 0, 4, 6, 10, 12, 16, 24, 30, 34, 40, 42, 46, 52, 54, 60, 66, 70, 72, 76 I must rewrite the code for the smallest nontrivial , this is unknown .... d = 0, 4, 6, 10, 16, 18, 24, 28, 30, 34, 40, 46, 48, 54, 58, 60, 66, 70, 76 [trivial: 13,17,...,89] ; 217153 (modulo 510510). For this pattern, the speed is 3x faster... ~ 1e17 /s and core. Last fiddled with by Cybertronic on 2022-08-27 at 16:38
 2022-08-27, 17:44 #21 Cybertronic     Jan 2007 Germany 11538 Posts Edit: Sieve for d = 0, 4, 6, 10, 16, 18, 24, 28, 30, 34, 40, 46, 48, 54, 58, 60, 66, 70, 76 is also ready. here an example with 14/19 are prime , first 10 conditions are prime 4008486315568214747203+d,d=0, 4, 6, 10, 16, 18, 24, 28, 30, 34, (40), 46, (48), (54), 58, 60, (66), 70, (76) Ratio 1:2,7 Running time 5 days per cycle and one core up to 32589158477190044730000 Last fiddled with by Cybertronic on 2022-08-27 at 17:52
 2022-08-28, 16:40 #22 Cybertronic     Jan 2007 Germany 619 Posts test run I have run now 32 threads...will see, how many conditions in order are true ... up to 32589158477190044730000 Tooks me 4h, so the offset progress (averaged) is 7e16/s and core After 30min: first with 13/19 in order. 3718239377799223934593+d, d=00,04,06,10,16,18,24,28,30,34,40,46,48 ; [like primes 13,..,61] Last fiddled with by Cybertronic on 2022-08-28 at 17:12

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 160 2022-07-18 08:34 robert44444uk Prime Gap Searches 45 2022-02-24 18:28 enzocreti enzocreti 3 2020-02-14 12:21 lukerichards Factoring 87 2019-03-28 13:31 CRGreathouse Software 10 2017-07-14 09:45

All times are UTC. The time now is 16:49.

Sat Jan 28 16:49:30 UTC 2023 up 163 days, 14:18, 0 users, load averages: 0.78, 0.95, 0.98