Earliest difference between prime gaps: Difference between revisions
Earliest difference between prime gaps (view source)
Revision as of 18:42, 13 April 2024
, 1 month ago→{{header|jq}}
(Created Nim solution.) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 69:
Note: the earliest value found for each order of magnitude may not be unique, in fact, ''is'' not unique; also, with the gaps in ascending order, the minimal starting values are not strictly ascending.
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find the differences between primes for each value of the gap #
# the prime and the next #
PR read "primes.incl.a68" PR # include prime utilities #
INT max prime = 2 000 000; # maximum prime we will consider #
[]BOOL prime = PRIMESIEVE max prime; # sieve the primes to max prime #
[ 1 : max prime OVER 2 ]INT start prime; # index of the first prime with #
# gap of subscript / 2 #
# find the prime gaps #
FOR i TO UPB start prime DO start prime[ i ] := 0 OD;
INT prev prime := 3;
FOR i FROM 5 BY 2 TO UPB prime DO
IF prime[ i ] THEN
INT gap = ( i - prev prime ) OVER 2;
IF start prime[ gap ] = 0 THEN
start prime[ gap ] := prev prime
FI;
prev prime := i
FI
OD;
# to reiterate the task: we must find the earliest start primes where #
# the distance betweeen the gaps is 10, 100, 1000, 10 000 etc. #
# The distance is the distance between the start prime with gap g and #
# start prime with the a gap of g + 2, e.g. 3 has a gap of 2 as the next #
# prime is 5, 7 has a gap of 4 as the next prime is 11, so the distance #
# is: 7 - 3 = 4 #
# shows a prime gap #
PROC show gap = ( INT start pos )VOID:
print( ( whole( start prime[ start pos ], 0 )
, "(", whole( start pos * 2, 0 ),")"
, whole( start prime[ start pos ] + ( start pos * 2 ), 0 )
)
);
# shows a prime gap distance #
PROC show distance = ( INT gap, pos )VOID:
BEGIN
print( ( "First distance > ", whole( gap, 0 )
, " betweeen prime gaps:", newline
, " ", whole( ABS ( start prime[ pos + 1 ] - start prime[ pos ] ), 0 )
, " between "
)
);
show gap( pos );
print( " and " );
show gap( pos + 1 );
print( ( newline ) )
END # show distance # ;
INT g10 := 0, g100 := 0, gt := 0, g10t := 0, g100t := 0, gm := 0;
FOR i TO UPB start prime - 1 DO
IF start prime[ i ] /= 0 AND start prime[ i + 1 ] /= 0 THEN
INT distance = ABS ( start prime[ i + 1 ] - start prime[ i ] );
IF distance > 10
THEN
IF g10 = 0 THEN g10 := i FI
FI;
IF distance > 100
THEN
IF g100 = 0 THEN g100 := i FI
FI;
IF distance > 1 000
THEN
IF gt = 0 THEN gt := i FI
FI;
IF distance > 10 000
THEN
IF g10t = 0 THEN g10t := i FI
FI;
IF distance > 100 000
THEN
IF g100t = 0 THEN g100t := i FI
FI;
IF distance > 1 000 000
THEN
IF gm = 0 THEN gm := i FI
FI
FI
OD;
show distance( 10, g10 );
show distance( 100, g100 );
show distance( 1 000, gt );
show distance( 10 000, g10t );
show distance( 100 000, g100t );
show distance( 1 000 000, gm )
END
</syntaxhighlight>
{{out}}
<pre>
First distance > 10 betweeen prime gaps:
16 between 7(4)11 and 23(6)29
First distance > 100 betweeen prime gaps:
1718 between 113(14)127 and 1831(16)1847
First distance > 1000 betweeen prime gaps:
1718 between 113(14)127 and 1831(16)1847
First distance > 10000 betweeen prime gaps:
21042 between 9551(36)9587 and 30593(38)30631
First distance > 100000 betweeen prime gaps:
141962 between 173359(70)173429 and 31397(72)31469
First distance > 1000000 betweeen prime gaps:
1047576 between 396733(100)396833 and 1444309(102)1444411
</pre>
=={{header|C++}}==
Line 185 ⟶ 289:
1000000000 -> distance between start of gap 276=649580171 and start of gap 278=4260928601 is 3611348430
</pre>
=={{header|FreeBASIC}}==
{{trans|C++}}
<syntaxhighlight lang="vbnet">Type PrimeGaps
As Ulong lastPrime
As Ulongint gapStarts(1 To 1e7)
End Type
Function NextPrime(n As Ulong) As Ulong
Dim As Ulong j, i = n + 1
Do
For j = 2 To Sqr(i)
If i Mod j = 0 Then Exit For
Next j
If j > Sqr(i) Then Return i
i += 1
Loop
End Function
Function findGapStart(Byref pg As PrimeGaps, gap As Ulongint) As Ulongint
Dim As Ulongint prev, diff
If pg.gapStarts(gap) <> 0 Then Return pg.gapStarts(gap)
Do
prev = pg.lastPrime
pg.lastPrime = NextPrime(pg.lastPrime)
diff = pg.lastPrime - prev
pg.gapStarts(diff) = prev
If gap = diff Then Return prev
Loop
End Function
Dim Shared As PrimeGaps pg
pg.lastPrime = NextPrime(2)
Dim As Ulongint limit = 1e7
Dim As Integer pm = 10
Dim As Ulongint start1, start2, gap1 = 2, gap2, diff
Do
start1 = findGapStart(pg, gap1)
gap2 = gap1 + 2
start2 = findGapStart(pg, gap2)
diff = Abs(start2 - start1)
If diff > pm Then
Print "Earliest difference >"; pm; " between adjacent prime gap starting primes:"
Print "Gap "; gap1; " starts at "; start1; ", gap "; gap2; " starts at "; start2; ", difference is "; diff; !".\n"
If pm = limit Then Exit Do
pm *= 10
Else
gap1 = gap2
End If
Loop
Sleep</syntaxhighlight>
=={{header|Go}}==
{{trans|Wren}}
Line 376 ⟶ 533:
</pre>
=={{header|jq}}==
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
In the following, `gaps` emits a stream of objects corresponding to the sequence OEIS A000230
except that `gaps` starts with 3 because 5-3 is the first occurrence of 2.
<syntaxhighlight lang="jq">
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
def idivide($j):
(. % $j) as $mod
| (. - $mod) / $j ;
def properfactors:
. as $in
| [2, $in, false]
| recurse(
. as [$p, $q, $valid, $s]
| if $q == 1 then empty
elif $q % $p == 0 then [$p, ($q|idivide($p)), true]
elif $p == 2 then [3, $q, false, $s]
else ($s // ($q | sqrt)) as $s
| if ($p + 2) <= $s then [$p + 2, $q, false, $s]
else [$q, 1, true]
end
end )
| if .[2] and .[0] != $in then .[0] else empty end ;
def stream_of_primes:
2, (range(3; infinite; 2) | if first(properfactors) // null then empty else . end);
# Emit a sequence of objects {gap, p, previous} starting with
# {"gap":2,"p":5,"previous":3}
# {"gap":6,"p":29,"previous":23}
# The stream of .previous values corresponds to the OEIS sequence https://oeis.org/A000230
# except that `gaps` starts with .previous equal to 3 because 5-3 is the first occurrence of 2.
def gaps:
foreach stream_of_primes as $p (null;
if . == null then { $p, next: 2 }
else (.next|tostring) as $next
| if .[$next] then .emit = .[$next] | del( .[$next] ) | .next += 2 else .emit = null end
| .emit2 = null
| ($p - .p) as $gap
| .previous = .p
| .p = $p
| if $gap < .next then .
else ($gap|tostring) as $s
| if $gap == .next then .emit2 = {$gap, p, previous} | .next += 2 | del( .[$s] )
elif .[$s] then .
else .[$s] = {$gap, p, previous}
end
end
end;
if .emit then .emit else empty end,
if .emit2 then .emit2 else empty end
);
# Report $n results, one for each order of magnitude starting with 10
def earliest_difference($n):
def report($gap):
if (($gap.previous - .previous)|length) > .magnitude
then .emit += [del(.emit) + {p: $gap.previous}]
| .magnitude *= 10
| report($gap)
else .
end;
limit($n;
foreach gaps as $gap (null;
if . == null then {magnitude: 10, n:0, previous: $gap.previous }
else .emit = null
| .n += 1
| report($gap)
| .previous = $gap.previous
end)
| select(.emit).emit[]);
earliest_difference(7)
</syntaxhighlight>
{{output}}
<pre>
{
"magnitude": 10,
"n": 2,
"previous": 7,
"p": 23
}
{
"magnitude": 100,
"n": 7,
"previous": 113,
"p": 1831
}
{
"magnitude": 1000,
"n": 7,
"previous": 113,
"p": 1831
}
{
"magnitude": 10000,
"n": 18,
"previous": 9551,
"p": 30593
}
{
"magnitude": 100000,
"n": 35,
"previous": 173359,
"p": 31397
}
{
"magnitude": 1000000,
"n": 50,
"previous": 396733,
"p": 1444309
}
{
"magnitude": 10000000,
"n": 74,
"previous": 2010733,
"p": 13626257
}
</pre>
=={{header|Julia}}==
Line 443 ⟶ 730:
Gap 276 starts at 649,580,171, gap 278 starts at 4,260,928,601, difference is 3,611,348,430.
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">primes = Prime[Range[10^7]];
Line 471 ⟶ 759:
=={{header|Nim}}==
{{trans|Wren}}
To find the primes, we used a sieve of Erathostenes for odd numbers only where each element is a bit.
<syntaxhighlight lang="Nim">import std/[bitops, math, strformat, tables]
Line 1,294 ⟶ 1,584:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
This uses a segmented sieve to avoid running out of memory when looking for the earliest difference above 1 billion. Takes a little over 5½ minutes to run (25 seconds
<syntaxhighlight lang="
import "./fmt" for Fmt
var limit = 1e9
var gapStarts = {}
var primes = Int.segmentedSieve(limit * 5,
for (i in 1...primes.count) {
var gap = primes[i] - primes[i-1]
Line 1,355 ⟶ 1,645:
Earliest difference > 1,000,000,000 between adjacent prime gap starting primes:
Gap 276 starts at 649,580,171, gap 278 starts at 4,260,928,601, difference is 3,611,348,430.
</pre>
===Faster version===
{{libheader|Wren-psieve}}
This uses our bindings to the C++ library ''primesieve'' and, as we're now iterating through the primes rather than sieving for them, uses very little memory compared to the first version.
It's also far quicker - 1.9 seconds when looking for the earliest difference above 100 million, 17.1 seconds for the earliest difference above one billion and even 10 billion (165 seconds) is now viable.
<syntaxhighlight lang="wren">import "./psieve" for Primes
import "./math" for Int
import "./fmt" for Fmt
var limit = 1e10
var gapStarts = {}
var it = Primes.iter()
var pc = Primes.count(2, limit * 5)
var p1 = it.next
var p2 = it.next
for (i in 1...pc) {
var gap = p2 - p1
if (!gapStarts[gap]) gapStarts[gap] = p1
p1 = p2
p2 = it.next
}
var pm = 10
var gap1 = 2
while (true) {
while (!gapStarts[gap1]) gap1 = gap1 + 2
var start1 = gapStarts[gap1]
var gap2 = gap1 + 2
if (!gapStarts[gap2]) {
gap1 = gap2 + 2
continue
}
var start2 = gapStarts[gap2]
var diff = (start2 - start1).abs
if (diff > pm) {
Fmt.print("Earliest difference > $,d between adjacent prime gap starting primes:", pm)
Fmt.print("Gap $d starts at $,d, gap $d starts at $,d, difference is $,d.\n", gap1, start1, gap2, start2, diff)
if (pm == limit) break
pm = pm * 10
} else {
gap1 = gap2
}
}
</syntaxhighlight>
{{out}}
Same as first version, plus:
<pre>
Earliest difference > 10,000,000,000 between adjacent prime gap starting primes:
Gap 332 starts at 5,893,180,121, gap 334 starts at 30,827,138,509, difference is 24,933,958,388.
</pre>
| |||