 mersenneforum.org GAPS BETWEEN PRIME PAIRS (Twin Primes)
 Register FAQ Search Today's Posts Mark Forums Read  2020-01-24, 00:37   #177
rudy235

Jun 2015
Vallejo, CA/.

17318 Posts Quote:
 Originally Posted by storm5510 It would appear you are creating negative numbers by subtracting the larger from the smaller.
Technically, yes. But you know what I mean.    2020-01-24, 22:49   #178
Bobby Jacobs

May 2018

3268 Posts Quote:
 Originally Posted by robert44444uk Can you send me the specific paper in which this is defined as such? When I Google the phrase you use, the only reference is your own Mersenneforum post. It sounds as if what you are defining is something that we can name as "maximal merit". I repeat what I said earlier. The definition is, I think, clear. It is not the definition of "maximal merit". What is being described here is,[B] for a prime gap of length x, there is no prime gap of length x or less with a higher merit. [/B}. For a gap of 10 or less, the record merit is 2.06 for the gap following 77. However it is not a "maximal merit" because the gap of 12 at 58 is.
This is the standard definition of record merit for regular prime gaps. By your definition for regular prime gaps, the gap of 12 between 199 and 211 would have record merit. However, it is not really a record merit gap because the gap of 14 between 113 and 127 has higher merit. See A111870, A111871, and A277552 in OEIS.   2020-01-26, 10:33   #179
robert44444uk

Jun 2003
Oxford, UK

1,933 Posts Quote:
 Originally Posted by Bobby Jacobs This is the standard definition of record merit for regular prime gaps. By your definition for regular prime gaps, the gap of 12 between 199 and 211 would have record merit. However, it is not really a record merit gap because the gap of 14 between 113 and 127 has higher merit. See A111870, A111871, and A277552 in OEIS.

I will repeat for the third time, I am not saying this gap has a record merit. I am saying 211 is the upper prime of a record merit for all gaps <=12 between primes. You can argue that there is a gap between 113 and 125 which is the same length, but this is not a gap between primes, and the gap between 113 and 127 is larger than 12.

Last fiddled with by robert44444uk on 2020-01-26 at 10:34   2020-01-28, 15:26   #180
storm5510
Random Account

Aug 2009

194210 Posts Quote:
 Originally Posted by mart_r Did you mean prime twins between 85e15 and 86e15?
I must release these back to the pool. Between losing all the data, once, and being sick for two weeks, i am not getting anywhere with them. I apologize!     2020-01-28, 19:34   #181
mart_r

Dec 2008
you know...around...

22×163 Posts Quote:
 Originally Posted by storm5510 I must release these back to the pool. Between losing all the data, once, and being sick for two weeks, i am not getting anywhere with them. I apologize!  No need to apologize. At the current rate, there are a couple of years to go until we reach k=85e15.

Quote:
 Originally Posted by robert44444uk I will repeat for the third time, I am not saying this gap has a record merit. I am saying 211 is the upper prime of a record merit for all gaps <=12 between primes. You can argue that there is a gap between 113 and 125 which is the same length, but this is not a gap between primes, and the gap between 113 and 127 is larger than 12.
It's also partially my fault to call it "record merit". You described it as "highest merit to date", I don't know about that definition.
Anyway, I've attached the data for k<7e15, where the maximum gaps are simply marked with an asterisk, like in the tables of Dr. Nicely.
There are yet no 5000+ gaps in my current search range.

________

Since at my workplace we're not allowed to run external programs, I took the time to put together my own VBA program that runs in an MS Excel environment. I was pretty delighted to discover that it runs on a decent speed of about 23e6 k's per core per second (Core i5 @ 3.00 GHz). A bit disappointed though that, while trying it out at home, it's only one third of the speed of the Perl program (well, depending on the architecture, YMMV - maybe someone else can gather more data on timings, I'm still in the process of doing so). Still, for me being only a mediocre programmer and I've been told that VBA was slow, that ought to be quite something.

The program is merely a variant of SOE, and utilizes about 700 MB of RAM.
Is it faster to do only a bit of trial division, as it were, and run a probable prime test on the remaining candidates (like I did in Pari) or work with trial division all along the way (like i did here)?

Maybe, just maybe, this can be compiled/optimized to the point where it's faster than the current C program?

Code:
'init k1=start value, k2=end value, mg=mingap report
k1 = 7E+15
k2 = 7.000123E+15
mg& = 3072

tm = Timer
Cells(1, 1) = "initializing..."
Dim p&(16252324), c&(378675), d&(7952175), o&(16252324, 2), e&(16252324), a%(185910725)
'p: primes 3 thru 3*10^8, c: temporary variable for the calculation of d, d: index of admissible twins in Z/23#Z, o: offsets for sieve, e: change in offsets per 5*23#, a: 0/1=prime/composite
w = Int(6 * k1 / 223092870)
x = 1 + Int(6 * k2 / 223092870)
b& = x - w: 'length of search interval

'calculate primes p(1)=3, p(2)=5, ... p(16252324)=299999977 - for k2>1.5e16 the number of primes has to be increased! Currently limited to 2^31/6 ~ 3.58e8, thus the program is currently limited to k<2.135e16. Can be scaled up in the routine below marked with *)
For q& = 3 To 17317 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& - 185910725 Mod q&
Next
For q& = 1 To 1989
m& = p&(q&)
m& = (m& - 1) / 2
For t& = m& + p&(q&) To 150000000 Step p&(q&)
a%(t&) = 1
Next
Next
For t& = 8660 To 150000000
If a%(t&) = 0 Then j& = j& + 1: p&(j&) = 2 * t& + 1: e&(j&) = p&(j&) - 185910725 Mod p&(j&)
Next

'calculate indexes of admissible twins in Z/23#Z where d=p/6 corresponds to a twin p±1 (mod 23#)
d&(1) = 2
d&(2) = 3
d&(3) = 5
q& = 0
For j& = 0 To 6
For k& = 1 To 3
r& = (30 * j& + 6 * d&(k&) + 1) Mod 7
If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 5 * j& + d&(k&)
Next
Next
q& = 0
For j& = 0 To 10
For k& = 1 To 15
r& = (210 * j& + 6 * c&(k&) + 1) Mod 11
If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 35 * j& + c&(k&)
Next
Next
q& = 0
For j& = 0 To 12
For k& = 1 To 135
r& = (2310 * j& + 6 * d&(k&) + 1) Mod 13
If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 385 * j& + d&(k&)
Next
Next
q& = 0
For j& = 0 To 16
For k& = 1 To 1485
r& = (30030 * j& + 6 * c&(k&) + 1) Mod 17
If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 5005 * j& + c&(k&)
Next
Next
q& = 0
For j& = 0 To 18
For k& = 1 To 22275
r& = (510510 * j& + 6 * d&(k&) + 1) Mod 19
If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 85085 * j& + d&(k&)
Next
Next
q& = 0
For j& = 0 To 22
For k& = 1 To 378675
r& = (9699690 * j& + 6 * c&(k&) + 1) Mod 23
If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 1616615 * j& + c&(k&)
Next
Next

'initialize offset values for sieve in a, where a(1,2,3...)={0 or 1, twin prime or either p-1 or p+1 composite} correspond to the twin p±1 where p=6*a (mod 23#)
l& = Int(Sqr(x * 223092870)): 'upper trial division limit
j& = 9: 'start at p(9)=29, since all smaller factors are taken care of with the d array
Do
y = Int(((w - 5) * 30030 / p&(j&) - Int((w - 5) * 30030 / p&(j&))) * p&(j&) + 0.5)
y = Int(((y * 7429 + 23) / p&(j&) - Int((y * 7429 + 23) / p&(j&))) * p&(j&) + 0.5)
r& = y: 'the calculation of r=((w-5)*23#+23) mod p is split up because I only have 53 bits of precision
r& = r& + p&(j&) * (r& Mod 2)
For s& = 2 To 6 Step 2: '*) this loop must be changed if primes p>2^31/6 are employed
If (p&(j&) * s& - r&) Mod 6 = 0 Then o&(j&, 1) = 4 + (p&(j&) * s& - r&) / 6
If (p&(j&) * s& - r& - 2) Mod 6 = 0 Then o&(j&, 2) = 4 + (p&(j&) * s& - r& - 2) / 6
Next
j& = j& + 1
Loop While p&(j&) < l&

'overhead finished, start search in intervals of 1115464350=5*23# (if MS allows it, I might push the envelope here and make the intervals even larger)
Do
Cells(h& + 1, 1) = "searching...  (k =" + Str$((w + f&) * 37182145) + " at a rate of" + Str$(Int(185910725 / (Timer - tm))) + " k's per second)"
tm = Timer
Erase a%()
For m& = 9 To 262143
o&(m&, 1) = (o&(m&, 1) + e&(m&)) Mod p&(m&)
o&(m&, 2) = (o&(m&, 2) + e&(m&)) Mod p&(m&)
v& = o&(m&, 1)
For n% = 0 To 4
If v& Mod 5 = 1 Or v& Mod 5 = 4 Then GoTo 1: 'skip sieve when 5 divides one member of 6d±1; could do it also for 7, but that probably makes the routine unwieldy and thus slower (someone might check that though)
For k& = v& To 185910725 Step p&(m&) * 5
a%(k&) = 1
Next
1           v& = v& + p&(m&)
Next
v& = o&(m&, 2)
For n% = 0 To 4
If v& Mod 5 = 1 Or v& Mod 5 = 4 Then GoTo 2
For k& = v& To 185910725 Step p&(m&) * 5
a%(k&) = 1
Next
2           v& = v& + p&(m&)
Next
Next
For m& = 262144 To j& - 1: ' for larger values p&(m&) the skip (mod 5) 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&)
For k& = o&(m&, 1) To 185910725 Step p&(m&)
a%(k&) = 1
Next
For k& = o&(m&, 2) To 185910725 Step p&(m&)
a%(k&) = 1
Next
Next
'sieving done, now looking for gaps
v& = 0
For n% = 0 To 4
For m& = 1 To 7952175
If a%(d&(m&) + v&) = 0 Then g& = d&(m&) - u&: u& = d&(m&): If g& >= mg& Then h& = h& + 1: Cells(h&, 1) = g&: Cells(h&, 2) = Str$(w + f& + n%) + " * 23#/6 +" + Str$(d&(m&) - g&)
Next
'TBD: skip m by 0.7~0.8*mg after a twin, subroutine ensues, but since the sieving requires 93% of the calc time and the search in a% only 7%, the overall speedup shouldn't be too significant, possibly about 5%
'also TBD: output k as a whole number, maybe next week...
u& = u& - 37182145
v& = v& + 37182145
Next
f& = f& + 5
If f& Mod 256 = 0 Then ActiveWorkbook.Save: 'saves every 793e6/(throughput in k's per second) minutes
Loop While f& <= b&
Cells(h& + 1, 1) = "finished search in the interval [" + Str$(k1) + "; " + Str$(k2) + " ]"
Attached Files twingaps up to 7.0e15.txt (294.0 KB, 120 views)   2020-01-29, 01:02   #182
storm5510
Random Account

Aug 2009

2×971 Posts Quote:
 Originally Posted by mart_r Reserving 7.0e15 to 7.5e15. It appears that, apart from you, I'm currently the only person in the world looking for gaps between prime twins.
No one else! Amazing. Perhaps they moved on to the Riesel search and PFGW.   2020-01-29, 03:00   #183
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2×2,393 Posts Quote:
 Originally Posted by storm5510 No one else! Amazing. Perhaps they moved on to the Riesel search and PFGW.
One more time, since you seem to have missed it- the Riesel prime search does not use PFGW. We use LLR.   2020-01-29, 17:07   #184
storm5510
Random Account

Aug 2009

194210 Posts Quote:
 Originally Posted by VBCurtis One more time, since you seem to have missed it- the Riesel prime search does not use PFGW. We use LLR.
No, I did not miss it. I have LLR installed here.I have been using NewPGen to generate work files for it. I have been using the console version of LLR. It seems to handle the NewPGen output files without issue. Knowing what to put in NewPGen is the problem.

Riesel: Is this not a strict format of 5*2^x-1? It seems this would dry up rapidly with lots of people working on it.   2020-02-03, 21:34 #185 mart_r   Dec 2008 you know...around... 22·163 Posts Twin prime gap search program for Excel/VBA There, I sped my program up by almost 30% If C or Perl is not an option for anybody, maybe this will do it? Code: 'k1=start value, k2=end value, mg=mingap report '---------------------------------------------- k1 = 7.492811E+15 k2 = 7.492812E+15 mg& = 4096 '---------------------------------------------- '(come think of it, I could use an input box here...) tm = Timer Cells(1, 1) = "initializing... (may take a couple of seconds)" Dim p&(16252324), c&(378675), d&(7952175), o&(16252324, 2), e&(16252324), a%(185910725), aa%(34) 'p: primes 3 thru 3*10^8, c: temporary variable for the calculation of d, d: index of admissible twins in Z/23#Z, o: offsets for sieve, e: change in offsets per 5*23#, a: 0/1=prime/composite, aa: 0/1=skip sieve in sieving routine below n/y w = Int(6 * k1 / 223092870) x = 1 + Int(6 * k2 / 223092870) b& = x - w: 'length of search interval 'calculate primes p(1)=3, p(2)=5, ... p(16252324)=299999977 - for k2>1.5e16 the number of primes has to be increased! Currently limited to 2^31/6 ~ 3.58e8, thus the program is currently limited to k<2.135e16. Can be scaled up in the routine below marked with *) For q& = 3 To 17317 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& - 185910725 Mod q& Next For q& = 1 To 1989 m& = p&(q&) m& = (m& - 1) / 2 For t& = m& + p&(q&) To 150000000 Step p&(q&) a%(t&) = 1 Next Next For t& = 8660 To 150000000 If a%(t&) = 0 Then j& = j& + 1: p&(j&) = 2 * t& + 1: e&(j&) = p&(j&) - 185910725 Mod p&(j&) Next 'calculate indexes of admissible twins in Z/23#Z where d=p/6 corresponds to a twin p±1 (mod 23#) d&(1) = 2 d&(2) = 3 d&(3) = 5 q& = 0 For j& = 0 To 6 For k& = 1 To 3 r& = (30 * j& + 6 * d&(k&) + 1) Mod 7 If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 5 * j& + d&(k&) Next Next q& = 0 For j& = 0 To 10 For k& = 1 To 15 r& = (210 * j& + 6 * c&(k&) + 1) Mod 11 If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 35 * j& + c&(k&) Next Next q& = 0 For j& = 0 To 12 For k& = 1 To 135 r& = (2310 * j& + 6 * d&(k&) + 1) Mod 13 If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 385 * j& + d&(k&) Next Next q& = 0 For j& = 0 To 16 For k& = 1 To 1485 r& = (30030 * j& + 6 * c&(k&) + 1) Mod 17 If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 5005 * j& + c&(k&) Next Next q& = 0 For j& = 0 To 18 For k& = 1 To 22275 r& = (510510 * j& + 6 * d&(k&) + 1) Mod 19 If r& <> 0 And r& <> 2 Then q& = q& + 1: c&(q&) = 85085 * j& + d&(k&) Next Next q& = 0 For j& = 0 To 22 For k& = 1 To 378675 r& = (9699690 * j& + 6 * c&(k&) + 1) Mod 23 If r& <> 0 And r& <> 2 Then q& = q& + 1: d&(q&) = 1616615 * j& + c&(k&) Next Next 'initialize offset values for sieve in a, where a(1,2,3...)={0 or 1, twin prime or either p-1 or p+1 composite} correspond to the twin p±1 where p=6*a (mod 23#) l& = Int(Sqr(x * 223092870)): 'upper trial division limit j& = 9: 'start at p(9)=29, since all smaller factors are taken care of with the d array Do y = Int(((w - 5) * 30030 / p&(j&) - Int((w - 5) * 30030 / p&(j&))) * p&(j&) + 0.5) y = Int(((y * 7429 + 23) / p&(j&) - Int((y * 7429 + 23) / p&(j&))) * p&(j&) + 0.5) r& = y: 'the calculation of r=((w-5)*23#+23) mod p is split up because I only have 53 bits of precision r& = r& + p&(j&) * (r& Mod 2) For s& = 2 To 6 Step 2: '*) this loop must be changed if primes p>2^31/6 are employed If (p&(j&) * s& - r&) Mod 6 = 0 Then o&(j&, 1) = 4 + (p&(j&) * s& - r&) / 6 If (p&(j&) * s& - r& - 2) Mod 6 = 0 Then o&(j&, 2) = 4 + (p&(j&) * s& - r& - 2) / 6 Next j& = j& + 1 Loop While p&(j&) < l& 'these are used to speed up the sieving routine below For q& = 0 To 204 Step 6 If q& Mod 5 = 1 Or q& Mod 5 = 4 Or q& Mod 7 = 1 Or q& Mod 7 = 6 Then aa%(q& / 6) = 1 Else aa%(q& / 6) = 0 Next 'overhead finished, start search in intervals of 1115464350=5*23# (if MS allows it, I might push the envelope here and make the intervals even larger) Do Cells(h& + 1, 1) = "searching... (k =" + Str$((w + f&) * 37182145) + " at a rate of" + Str$(Int(185910725 / (Timer - tm))) + " k's per second)" tm = Timer Erase a%() For m& = 9 To 65535 o&(m&, 1) = (o&(m&, 1) + e&(m&)) Mod p&(m&) o&(m&, 2) = (o&(m&, 2) + e&(m&)) Mod p&(m&) v& = o&(m&, 1) For n% = 0 To 34 If aa%(v& Mod 35) Then GoTo 1: 'skip sieve when 5 or 7 divides one member of 6d±1 For k& = v& To 185910725 Step p&(m&) * 35 a%(k&) = 1 Next 1 v& = v& + p&(m&) Next v& = o&(m&, 2) For n% = 0 To 34 If aa%(v& Mod 35) Then GoTo 2 For k& = v& To 185910725 Step p&(m&) * 35 a%(k&) = 1 Next 2 v& = v& + p&(m&) Next Next For m& = 65536 To 393215 o&(m&, 1) = (o&(m&, 1) + e&(m&)) Mod p&(m&) o&(m&, 2) = (o&(m&, 2) + e&(m&)) Mod p&(m&) v& = o&(m&, 1) For n% = 0 To 4 If aa%(v& Mod 5) Then GoTo 3: 'skip sieve when 5 divides one member of 6d±1 For k& = v& To 185910725 Step p&(m&) * 5 a%(k&) = 1 Next 3 v& = v& + p&(m&) Next v& = o&(m&, 2) For n% = 0 To 4 If aa%(v& Mod 5) Then GoTo 4 For k& = v& To 185910725 Step p&(m&) * 5 a%(k&) = 1 Next 4 v& = v& + p&(m&) Next Next For m& = 393216 To j& - 1: ' for larger values p&(m&) the skip (mod 5) 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&) For k& = o&(m&, 1) To 185910725 Step p&(m&) a%(k&) = 1 Next For k& = o&(m&, 2) To 185910725 Step p&(m&) a%(k&) = 1 Next Next 'sieving done, now looking for gaps v& = 0 For n% = 0 To 4 For m& = 1 To 7952175 If a%(d&(m&) + v&) = 0 Then g& = d&(m&) - u&: If g& >= mg& Then GoSub 5 Else i% = 0: GoSub 6: 'see below Next 'TBD: output k as a whole number, maybe next week... u& = u& - 37182145 v& = v& + 37182145 Next f& = f& + 5 If f& Mod 256 = 0 Then ActiveWorkbook.Save: 'saves every 793e6/(throughput in k's per second) minutes Loop While f& <= b& Cells(h& + 1, 1) = "finished search in the interval [" + Str$(k1) + "; " + Str$(k2) + " ]" End 5 If i% = 0 Then h& = h& + 1: Cells(h&, 1) = g&: Cells(h&, 2) = Str$(w + f& + n%) + " * 23#/6 +" + Str$(d&(m&) - g&): GoTo 6: 'i%=0: no jump in m, so no interval left unchecked 'when i%=1, there's an unchecked interval t+[1..320] after a twin 6*d(t)± 1 that has to be examined i% = 0 For q& = t& + 320 To t& + 1 Step -1 If a%(d&(q&) + v&) = 0 Then u& = d&(q&): q& = t& + 1 Next g& = d&(m&) - u& If g& >= mg& Then h& = h& + 1: Cells(h&, 1) = g&: Cells(h&, 2) = Str$(w + f& + n%) + " * 23#/6 +" + Str$(d&(m&) - g&) 6 u& = d&(m&) If m& < 7946240 Then t& = m&: m& = m& + 320: i% = 1: 'skip some values after a twin is found to accelerate the search, but only if an interval overlap is out of question Return   2020-02-04, 00:27   #186
ATH
Einyen

Dec 2003
Denmark

60768 Posts Quote:
 Originally Posted by storm5510 Riesel: Is this not a strict format of 5*2^x-1? It seems this would dry up rapidly with lots of people working on it.
Riesel search is for numbers of the form k*2n - 1 and k<2n

https://en.wikipedia.org/wiki/Lucas%...%93Riesel_test (LLR)

Proth numbers are of the form k*2n + 1 and k<2n

https://en.wikipedia.org/wiki/Proth%27s_theorem

and the corresponding software to run the test is Proth: https://github.com/galloty/proth20   2020-02-12, 20:20 #187 mart_r   Dec 2008 you know...around... 22·163 Posts Reserving 7.5e15 to 8e15. Nothing special in my previous range, only one 5000+ gap: Code: 5103 7181481105338907 Smallest unknown gap is still 4239, and 9 of the first 10 smallest unknown gaps are either 1 or 4 mod 5. I hope I can someday work out some idea about how to give a heuristic argument that the number of "late gaps", as Bobby called them, that are not 1 or 4 mod 5 might be finite... I'll update the tables once I finished this new range.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Bobby Jacobs Prime Gap Searches 52 2020-08-22 15:20 Pietro Maiorana Twin Prime Search 8 2019-09-26 23:07 hal1se Miscellaneous Math 13 2018-11-05 16:34 carpetpool Miscellaneous Math 3 2017-08-10 13:47 PawnProver44 Miscellaneous Math 10 2016-04-10 19:32

All times are UTC. The time now is 10:53.

Sat May 15 10:53:17 UTC 2021 up 37 days, 5:34, 0 users, load averages: 1.55, 1.52, 1.51