Earliest difference between prime gaps: Difference between revisions
Earliest difference between prime gaps (view source)
Revision as of 18:42, 13 April 2024
, 2 months ago→{{header|jq}}
(→Faster version: Now finds earliest difference above 10 billion.) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
Line 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 480 ⟶ 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 547 ⟶ 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 1,401 ⟶ 1,585:
{{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 for the earliest difference above 100 million) on my machine (core i7, 32GB RAM, Ubuntu 20.04).
<syntaxhighlight lang="
import "./fmt" for Fmt
var limit = 1e9
Line 1,468 ⟶ 1,652:
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="
import "./math" for Int
import "./fmt" for Fmt
| |||