QUADRUPLET PRIMES AND THEIR GAPS

[pinhodecarlos]

Taking 51e14 to 63e14.

[pinhodecarlos]

28e14 to 32e14 is done.

[pinhodecarlos]

Originally Posted by pinhodecarlos

Taking 51e14 to 63e14.

Disregard, will make a pause on my runs.

[pinhodecarlos]

32e14 to 44e14 done.

[robert44444uk]

Here are the results to 48e14

Lowest not found

141189
141618
142003
145305
145592
145713
145942

Largest gaps found:

292457 4130270328498071
294839 3358677223488941
297857 4755085294497611
299011 4798720220604041
301661 4675069123945391

[mart_r]

What is your throughput, by the way?

I've modified my VBA program for twin gaps to search for quad gaps. It searches about 420e6 per second on the PC at my workplace (Core i5 @ 3.00 GHz). With two instances running, it's 310e6 per second per core, ballpark.

While only loosely following this thread, all the time I thought you're searching for quadruplets with k corresponding to a quadruplet p=30*k+{11,13,17,19} (or something similar, like with the twins where p±1=6*k±1), hoping my program can somewhat compete. Now I found that your search is only at about 6e15, which would be k=2e14 for my program... means, I'd have to modify it slightly once more - or you go with the output as k corresponding to the quadruplet 30*k+{11,13,17,19}.

The numbers I gave above are for a sample at k=3e15+, i.e. quadruplets > 9e16. So it will be even faster for the range you're currently searching, and I could even tweak it up by another few percent.
Sample output:

210182 3000001826221497
219408 3000003314624064
212435 3000003323759190
205450 3000003708744917
209058 3000004124915549

I may have to do some more tests with it, but it seems to run quite well already. Only requires 1.1 GB of RAM while running.

Anyone interested?

[pinhodecarlos]

4e8/sec/core. Less than 60MB/core. i7-3630QM

[mart_r]

Okay, so at k=2e14, i.e. p=6e15, I get a throughput of up to 560e6/s or 18.7e6 k/s. Unfortunately, it drops down to under 400e6/s/core with two instances running...
With the newest hardware, I think that 1e9/s is possible. I also have one or two more ideas which might increase the speed by about 20% (well, that's me being optimistic:).

Like I said, this is VBA code for an MS Excel environment. Personally, I prefer to insert an ActiveX button into a spreadsheet and copy-paste the code into it, then press that button to let it run. (I'm not sure how many people around here actually work with VBA...)

'please enter your values of choice here: k1=range start, k2=range end, mg&=mingap report
'----------------------------------------------------------------------------------------
k1 = 6E+15 / 30
k2 = 6.1E+15 / 30
mg& = 150000
'----------------------------------------------------------------------------------------



tm = Timer
Cells(1, 4) = "initializing..."
Dim p&(22914109), c&(700244), d&(17506124), o&(22914109, 4), e&(22914109), a%(215656441), aa%(6)
'p: primes 3 thru 29#/15, c: temporary variable for the calculation of d, d: index of admissible quads in Z/29#Z, o: offsets for sieve, e: change in offsets per 29#, a: 0/1=prime/composite, aa: 0/1=skip sieve in sieving routine below n/y

w = Int(30 * k1 / 6469693230#)
x = 1 + Int(30 * k2 / 6469693230#)
b& = x - w: 'length of search interval

'calculate primes p(1)=3, p(2)=5, ... p(22914109)=431312881 - for k2>6.2e15 the number of primes has to be increased!
Cells(1, 4) = "calculate primes below 29#/15... ( 0%)"
For q& = 3 To 20759 Step 2
    i% = 1
    For t& = 3 To Sqr(q&) Step 2
    If q& Mod t& = 0 Then i% = 0: t& = Sqr(q&)
    Next
    If i% Then j& = j& + 1: p&(j&) = q&: e&(j&) = q& - 215656441 Mod q&
Next
Cells(1, 4) = "calculate primes below 29#/15... ( 1%)"
q2& = 1
For q& = 1 To 2338
    m& = p&(q&)
    m& = (m& - 1) / 2
    For t& = m& + p&(q&) To 215656441 Step p&(q&)
    a%(t&) = 1
    Next
    If q& = q2& Then q2& = q2& * 4: t1$ = Str$(Int(Sqr(q&) / 0.8)): Cells(1, 4) = "calculate primes below 29#/15... (" + t1$ + "%)"
Next
Cells(1, 4) = "calculate primes below 29#/15... ( 60%)"
For t& = 10385 To 215656441
If a%(t&) = 0 Then j& = j& + 1: p&(j&) = 2 * t& + 1: e&(j&) = p&(j&) - 215656441 Mod p&(j&)
Next
t& = 0

'calculate indexes of admissible quads in Z/29#Z where d=p/30 corresponds to a quadruplet p+{11,13,17,19} (mod 29#)
Cells(1, 4) = "calculate admissible quads in Z/29#Z..."
d&(0) = 0
d&(1) = 3
d&(2) = 6
q& = -1
For j& = 0 To 10
    For k& = 0 To 2
    r& = (210 * j& + 30 * d&(k&) + 19) Mod 11
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: c&(q&) = 7 * j& + d&(k&)
    Next
Next
q& = -1
For j& = 0 To 12
    For k& = 0 To 20
    r& = (2310 * j& + 30 * c&(k&) + 19) Mod 13
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: d&(q&) = 77 * j& + c&(k&)
    Next
Next
q& = -1
For j& = 0 To 16
    For k& = 0 To 188
    r& = (30030 * j& + 30 * d&(k&) + 19) Mod 17
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: c&(q&) = 1001 * j& + d&(k&)
    Next
Next
q& = -1
For j& = 0 To 18
    For k& = 0 To 2456
    r& = (510510 * j& + 30 * c&(k&) + 19) Mod 19
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: d&(q&) = 17017 * j& + c&(k&)
    Next
Next
q& = -1
For j& = 0 To 22
    For k& = 0 To 36854
    r& = (9699690 * j& + 30 * d&(k&) + 19) Mod 23
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: c&(q&) = 323323 * j& + d&(k&)
    Next
Next
q& = -1
For j& = 0 To 28
    For k& = 0 To 700244
    r& = 223092870 Mod 29
    r& = (r& * j& + 30 * c&(k&) + 19) Mod 29
    If r& <> 0 And r& <> 2 And r& <> 6 And r& <> 8 Then q& = q& + 1: d&(q&) = 7436429 * j& + c&(k&)
    Next
Next

'estimate time for calculating the offset values
l& = Int(Sqr(x * 6469693230#)): 'upper trial division limit
t0 = Int((Timer - tm) * l& / 650000000 + 0.5) * 10
If t0 < 90 Then t1$ = " seconds)" Else t0 = Int(t0 / 60 + 0.5): t1$ = " minutes)"

'initialize offset values for sieve in a, where a(1,2,3...n)={0 or 1, quadruplet or at least one composite} correspond to the quad p+{11,13,17,19} where p=30*d(n) (mod 29#)
Cells(1, 4) = "calculate offsets for sieve... (this may take about" + Str$(t0) + t1$
j& = 10: 'start at p(10)=31, since all smaller factors are taken care of with the d array
Do
    y = Int(((w - 1) * 510510 / p&(j&) - Int((w - 1) * 510510 / p&(j&))) * p&(j&) + 0.5)
    y = Int(((y * 12673 + 29) / p&(j&) - Int((y * 12673 + 29) / p&(j&))) * p&(j&) + 0.5)
    r& = y: 'the calculation of r=((w-1)*29#+29) mod p is split up because I only have 53 bits of precision
    r& = r& + p&(j&) * (r& Mod 2)
    pp = p&(j&)
    For s& = 2 To 30 Step 2
    If ((p&(j&) Mod 30) * s& - r& + 18) Mod 30 = 0 Then o&(j&, 1) = 1 + (pp * s& - r& + 18) / 30
    If ((p&(j&) Mod 30) * s& - r& + 16) Mod 30 = 0 Then o&(j&, 2) = 1 + (pp * s& - r& + 16) / 30
    If ((p&(j&) Mod 30) * s& - r& + 12) Mod 30 = 0 Then o&(j&, 3) = 1 + (pp * s& - r& + 12) / 30
    If ((p&(j&) Mod 30) * s& - r& + 10) Mod 30 = 0 Then o&(j&, 4) = 1 + (pp * s& - r& + 10) / 30
    Next
    j& = j& + 1
Loop While p&(j&) < l&

'these are used to speed up the sieving routine below
For q& = 30 To 210 Step 30
If q& Mod 7 > 2 Then aa%(q& / 30) = 1
Next

sk& = mg& * 2 / 25
'this is for the number of values in d skipped after a quadruplet is found to accelerate the search
'a small overview of the max. difference between sk consecutive values of d vs. the largest possible gap that would be missed:
'1000/12782, 2000/25155, 3000/37552, 4000/49958, 5000/62374, 6000/74788, 7000/87080, 8000/99404, 9000/111696, 10000/123987, 15000/185683, 20000/247370, 25000/308830 (ratio approaching 12.3189 = 29#/30/(3*7*9*13*15*19*25))

'overhead finished, start search in intervals of 6469693230=29#
Do
    Cells(1, 4) = "searching...  (p =" + Str$((w + f&) * 6469693230) + "  at a rate of" + Str$(Int(6469.69323 / (Timer - tm))) + "e6 per second)"
    tm = Timer
    Erase a%()
    
    For m& = 10 To 786431
        o&(m&, 1) = (o&(m&, 1) + e&(m&)) Mod p&(m&)
        o&(m&, 2) = (o&(m&, 2) + e&(m&)) Mod p&(m&)
        o&(m&, 3) = (o&(m&, 3) + e&(m&)) Mod p&(m&)
        o&(m&, 4) = (o&(m&, 4) + e&(m&)) Mod p&(m&)
        v& = o&(m&, 1)
        For n% = 0 To 6
            If aa%(v& Mod 7) Then GoTo 1: 'skip sieve when 7 divides one member of 30d+{11,13,17,19}
            For k& = v& To 215656441 Step p&(m&) * 7
            a%(k&) = 1
            Next
1           v& = v& + p&(m&)
        Next
        v& = o&(m&, 2)
        For n% = 0 To 6
            If aa%(v& Mod 7) Then GoTo 2
            For k& = v& To 215656441 Step p&(m&) * 7
            a%(k&) = 1
            Next
2           v& = v& + p&(m&)
        Next
        v& = o&(m&, 3)
        For n% = 0 To 6
            If aa%(v& Mod 7) Then GoTo 3
            For k& = v& To 215656441 Step p&(m&) * 7
            a%(k&) = 1
            Next
3           v& = v& + p&(m&)
        Next
        v& = o&(m&, 4)
        For n% = 0 To 6
            If aa%(v& Mod 7) Then GoTo 4
            For k& = v& To 215656441 Step p&(m&) * 7
            a%(k&) = 1
            Next
4           v& = v& + p&(m&)
        Next
    Next
    For m& = 786432 To j& - 1: 'for larger values p(m) the skip (mod 7) as above has no longer an effect w.r.t. speed and can even be counterproductive
        o&(m&, 1) = (o&(m&, 1) + e&(m&)) Mod p&(m&)
        o&(m&, 2) = (o&(m&, 2) + e&(m&)) Mod p&(m&)
        o&(m&, 3) = (o&(m&, 3) + e&(m&)) Mod p&(m&)
        o&(m&, 4) = (o&(m&, 4) + e&(m&)) Mod p&(m&)
        For k& = o&(m&, 1) To 215656441 Step p&(m&)
        a%(k&) = 1
        Next
        For k& = o&(m&, 2) To 215656441 Step p&(m&)
        a%(k&) = 1
        Next
        For k& = o&(m&, 3) To 215656441 Step p&(m&)
        a%(k&) = 1
        Next
        For k& = o&(m&, 4) To 215656441 Step p&(m&)
        a%(k&) = 1
        Next
    Next
    
    'sieving done, now looking for gaps
    For m& = 0 To 17506124
    If a%(d&(m&) + 1) = 0 Then g& = d&(m&) - u&: If g& >= mg& Then GoSub 5 Else i% = 0: GoSub 6: 'see below
    Next
    
    f& = f& + 1
    If f& Mod 256 = 0 Then ActiveWorkbook.Save: 'saves every 920e6/(throughput in k's per second) minutes
Loop While f& <= b&
Cells(1, 4) = "finished search in the interval [" + Str$(k1*30) + ";" + Str$(k2*30) + " ]"
End

'what to do after a quad gap is found
5   If i% = 0 Then GoSub 7: GoTo 6: 'i=0: no jump in m, so no interval left unchecked
    'when i=1, there's an unchecked interval t+[1..sk] after a quad 30*d(t)+{11,13,17,19} that has to be examined
    i% = 0
    For q& = t& + sk& To t& + 1 Step -1
    If a%(d&(q&) + 1) = 0 Then u& = d&(q&): q& = t& + 1
    Next
    g& = d&(m&) - u&
    If g& >= mg& Then GoSub 7
6   u& = d&(m&)
    If m& < 17301504 Then t& = m&: m& = m& + sk&: i% = 1: 'skip some values (sk=mg/12.5, see above) after a quadruplet is found to accelerate the search, but only if an interval overlap is out of question
Return

'output gap size and initial quadruplet member p where p=(w+f)*29#+30*(d-g)+11 is transformed to a string, else it would show as "1.2345...E+15" and a digit or two would be missed
7   h& = h& + 1: 'line number in the spreadsheet
    Cells(h&, 1) = g&
    k0 = w + f&
    kk$ = Str$(Int(((k0 * 215656441 + d&(m&) - g&) * 30 + 11) / 10000)): 'the four rightmost digits are separated
    'error checking routine b/c of possible rounding errors in k0 (compare 5th digit from the right of output value p):
    kc$ = Str$(Int(((Int((k0 / 100000 - Int(k0 / 100000)) * 100000 + 0.5) * 56441 + d&(m&) - g&) * 30 + 11) / 10000))
    If Right$(kc$, 1) <> Right$(kk$, 1) Then kk$ = Str$(Val(kk$) + 1)
    If Right$(kc$, 1) <> Right$(kk$, 1) Then kk$ = Str$(Val(kk$) - 2): 'if there's a difference of 1 then it could be either way
    If Right$(kc$, 1) <> Right$(kk$, 1) Then Cells(h&, 3) = "roundoff error - actual value is ± 10000*n": 'according to my calculations, this should never happen, but please notify me if it does
    k0 = (Int((k0 / 10000 - Int(k0 / 10000)) * 10000 + 0.5) * 6441 + d&(m&) - g&) * 30 + 11
    kk$ = kk$ + Right$(Str$(k0), 4): 'attach the four rightmost digits of p
    Cells(h&, 2) = "'" + kk$
  Return

Sample output, open for a doublecheck:

157408     6000001640668151
193407     6000002159655611
168354     6000003739794431
154493     6000011459357051
157143     6000012374499881
158959     6000016376027741
179215     6000023351176661
158259     6000057185313551
152205     6000080439010961
157682     6000103401410771
151760     6000122628523481
152417     6000132294625361
155295     6000133069290251
159687     6000135231403121
170215     6000171234646151
177764     6000193829450531
172522     6000219920155841
151494     6000228823614671
159775     6000236248927091
152818     6000236322087191
153824     6000244257843371
151659     6000245036603891
159516     6000259663039331
157259     6000286444067561
164717     6000293576349461
183889     6000305208085451
152704     6000305789926571
158442     6000310748399501
156486     6000333261789281
150843     6000375083766521
155359     6000405248900981
172008     6000418068980051
202398     6000429250142021
179879     6000442814491241
152274     6000454624067081
173043     6000489549459401
151372     6000494145438971
167220     6000509205050411
156675     6000511112965931
167167     6000522139337651
161504     6000535610418521
154938     6000538023166781
190985     6000546117033071
165096     6000547163903441
162018     6000595415536151
163691     6000633443235791
152859     6000653488841021
168094     6000674484836651
152684     6000687207138731
165810     6000756599086811
172404     6000757714747091
154769     6000796416450161
167453     6000812350040771
167465     6000898568751341
153745     6000909269962721
161699     6000986802988811
153580     6001002678856901
154927     6001052741241401
200609     6001079275241201
157753     6001105549171721
152061     6001154602816691
165885     6001166031516191
161010     6001168360224881
159264     6001189480424681
165432     6001200136575401
189406     6001207193410901
153384     6001225149549521
152362     6001249901454251
152778     6001255394984651
173565     6001282206815891
150339     6001289006445371
173601     6001290059284571
151497     6001302910874981
151449     6001324616830091
161434     6001329889759661
151785     6001335587842871
175154     6001356810879971
158729     6001382977244021
159866     6001399836567761
162845     6001404010319951
164672     6001411917995231
192478     6001437200512541
157893     6001523767483001
155658     6001527598895441
153083     6001534581622421
154234     6001553349993911
159814     6001566094464041
157223     6001576142838161
153174     6001597444733741
172354     6001605345871691
174531     6001612114324991
156002     6001619234346341
157017     6001636809774491
151409     6001720634955581
161013     6001730748934001
159467     6001745717794241
192360     6001757176627361
168729     6001773504247061
155736     6001792594746251
156387     6001816173543731
164625     6001823584213181
204704     6001850996589731
150521     6001860741894881
178763     6001864208888831


sorted by gap size:
150339     6001289006445371
150521     6001860741894881
150843     6000375083766521
151372     6000494145438971
151409     6001720634955581
151449     6001324616830091
151494     6000228823614671
151497     6001302910874981
151659     6000245036603891
151760     6000122628523481
151785     6001335587842871
152061     6001154602816691
152205     6000080439010961
152274     6000454624067081
152362     6001249901454251
152417     6000132294625361
152684     6000687207138731
152704     6000305789926571
152778     6001255394984651
152818     6000236322087191
152859     6000653488841021
153083     6001534581622421
153174     6001597444733741
153384     6001225149549521
153580     6001002678856901
153745     6000909269962721
153824     6000244257843371
154234     6001553349993911
154493     6000011459357051
154769     6000796416450161
154927     6001052741241401
154938     6000538023166781
155295     6000133069290251
155359     6000405248900981
155658     6001527598895441
155736     6001792594746251
156002     6001619234346341
156387     6001816173543731
156486     6000333261789281
156675     6000511112965931
157017     6001636809774491
157143     6000012374499881
157223     6001576142838161
157259     6000286444067561
157408     6000001640668151
157682     6000103401410771
157753     6001105549171721
157893     6001523767483001
158259     6000057185313551
158442     6000310748399501
158729     6001382977244021
158959     6000016376027741
159264     6001189480424681
159467     6001745717794241
159516     6000259663039331
159687     6000135231403121
159775     6000236248927091
159814     6001566094464041
159866     6001399836567761
161010     6001168360224881
161013     6001730748934001
161434     6001329889759661
161504     6000535610418521
161699     6000986802988811
162018     6000595415536151
162845     6001404010319951
163691     6000633443235791
164625     6001823584213181
164672     6001411917995231
164717     6000293576349461
165096     6000547163903441
165432     6001200136575401
165810     6000756599086811
165885     6001166031516191
167167     6000522139337651
167220     6000509205050411
167453     6000812350040771
167465     6000898568751341
168094     6000674484836651
168354     6000003739794431
168729     6001773504247061
170215     6000171234646151
172008     6000418068980051
172354     6001605345871691
172404     6000757714747091
172522     6000219920155841
173043     6000489549459401
173565     6001282206815891
173601     6001290059284571
174531     6001612114324991
175154     6001356810879971
177764     6000193829450531
178763     6001864208888831
179215     6000023351176661
179879     6000442814491241
183889     6000305208085451
189406     6001207193410901
190985     6000546117033071
192360     6001757176627361
192478     6001437200512541
193407     6000002159655611
200609     6001079275241201
202398     6000429250142021
204704     6001850996589731

[robert44444uk]

Taking 51e14 to 55e14

Best Results for 48e14 to51e14

311546 4973407410305771	
272010 4875302967363971	
259721 4892662650863171	
257432 4908977413132151	
255570 5020375020286511	
254174 4832025731643371	
250327 5036027092938551	
250247 4858056545875781

Lowest not found:

141189 (6) 
141618 (1)
142003 (1)
145305 (6)
145592 (6)
145713 (1)

[mart_r]

Sometimes I wonder why I even bother...

[robert44444uk]

Originally Posted by mart_r

Sometimes I wonder why I even bother...

Do bother, mart_r. What you are doing is progress.

Personally I dont have much time to devote to learning/ running new software at present. Others may have more time.