Rosetta Code

Earliest difference between prime gaps: Difference between revisions

Page Discussion

Earliest difference between prime gaps (view source)

Revision as of 18:42, 13 April 2024

14,419 bytes added ,  1 month ago
→‎{{header|jq}}
m (minimum prime gaps were not defined here, but adjacent prime gaps were defined here. and we have a table here illustrating some example minimum occurrences of such gaps.)
 
(9 intermediate revisions by 6 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++}}==
{{libheader|Primesieve}}
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <locale>
#include <unordered_map>
Line 124 ⟶ 228:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 165 ⟶ 269:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Earliest difference between prime gaps. Nigel Galloway: December 1st., 2021
let fN y=let i=System.Collections.Generic.SortedDictionary<int64,int64>()
Line 172 ⟶ 276:
[1..9]|>List.iter(fun g->let fN=fN(pown 10 g) in let n,i=(primes64()|>Seq.skip 1|>Seq.pairwise|>Seq.map fN|>Seq.find Option.isSome).Value
printfn $"%10d{pown 10 g} -> distance between start of gap %d{n.Key}=%d{n.Value} and start of gap %d{i.Key}=%d{i.Value} is %d{abs((n.Value)-(i.Value))}")
</syntaxhighlight>
</lang>
{{out}}
<pre>
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}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 237 ⟶ 394:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 268 ⟶ 425:
Gap 276 starts at 649,580,171, gap 278 starts at 4,260,928,601, difference is 3,611,348,430.
</pre>
 
=={{header|J}}==
 
Implementation:
 
<syntaxhighlight lang="j">lowpgap=: {{
magnitude=. ref=. 10^y
whilst. -.1 e. ok do.
magnitude=. 10*magnitude
g=. 2-~/\ p=.p: i.magnitude
mag=. p{~}.g i. i.&.-: >./g NB. minimum adjacent gaps
dif=. 2-~/\ mag
ok=. ref < dif
end.
(0 1+ok i.1){mag
}}</syntaxhighlight>
 
Task examples:
 
<syntaxhighlight lang="j"> lowpgap 1
7 23
lowpgap 2
113 1831
lowpgap 3
113 1831
lowpgap 4
9551 30593
lowpgap 5
31397 404597
lowpgap 6
396733 1444309
lowpgap 7
2010733 13626257</syntaxhighlight>
 
=={{header|Java}}==
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<langsyntaxhighlight lang="java">import java.util.HashMap;
import java.util.Map;
 
Line 314 ⟶ 504:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 343 ⟶ 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}}==
{{trans|Wren}}
To get to 10^9 correctly we need a limit multiplier of 5 in Julia, not 4. Going up to 10^10 runs out of memory on my machine.
<langsyntaxhighlight lang="julia">using Formatting
using Primes
 
Line 381 ⟶ 701:
 
primegaps()
</langsyntaxhighlight>{{out}}
<pre>
Earliest difference > 10 between adjacent prime gap starting primes:
Line 410 ⟶ 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}}==
<langsyntaxhighlight Mathematicalang="mathematica">primes = Prime[Range[10^7]];
gaps = {Differences[primes], Most[primes]} // Transpose;
tmp = GatherBy[gaps, First][[All, 1]];
Line 420 ⟶ 741:
{10^i, n, starts[n], n + 2, starts[n + 2], k}, {i, 1, 7}];
StringTemplate["Earliest difference > `` between adjacent prime gap starting primes:
Gap `` starts at ``, gap `` starts at ``, difference is ``."]/*Print @@@ data;</langsyntaxhighlight>
{{out}}
<pre>Earliest difference > 10 between adjacent prime gap starting primes:
Line 436 ⟶ 757:
Earliest difference > 10000000 between adjacent prime gap starting primes:
Gap 148 starts at 2010733, gap 150 starts at 13626257, difference is 11615524.</pre>
 
=={{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]
 
type Sieve = object
data: seq[byte]
 
proc `[]`(sieve: Sieve; idx: Positive): bool =
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
 
proc `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
 
proc newSieve(lim: Positive): Sieve =
result.data = newSeq[byte]((lim + 16) shr 4)
 
proc initPrimes(lim: Positive): seq[Natural] =
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
for n in countup(3, lim, 2):
if not composite[n]:
result.add n
 
const Limit = 100_000_000
let primes = initPrimes(Limit * 5)
var gapStarts: Table[int, int]
for i in 1..primes.high:
let gap = primes[i] - primes[i - 1]
if gap notin gapStarts:
gapStarts[gap] = primes[i - 1]
var pm = 10
var gap1 = 2
while true:
while gap1 notin gapStarts:
inc gap1, 2
let start1 = gapStarts[gap1]
let gap2 = gap1 + 2
if gap2 notin gapStarts:
gap1 = gap2 + 2
continue
let start2 = gapStarts[gap2]
let diff = abs(start2 - start1)
if diff > pm:
echo &"Earliest difference > {pm} between adjacent prime gap starting primes:"
echo &"Gap {gap1} starts at {start1}, gap {gap2} starts at {start2}, difference is {diff}.\n"
if pm == Limit: break
pm *= 10
else:
gap1 = gap2
</syntaxhighlight>
 
{{out}}
<pre>Earliest difference > 10 between adjacent prime gap starting primes:
Gap 4 starts at 7, gap 6 starts at 23, difference is 16.
 
Earliest difference > 100 between adjacent prime gap starting primes:
Gap 14 starts at 113, gap 16 starts at 1831, difference is 1718.
 
Earliest difference > 1000 between adjacent prime gap starting primes:
Gap 14 starts at 113, gap 16 starts at 1831, difference is 1718.
 
Earliest difference > 10000 between adjacent prime gap starting primes:
Gap 36 starts at 9551, gap 38 starts at 30593, difference is 21042.
 
Earliest difference > 100000 between adjacent prime gap starting primes:
Gap 70 starts at 173359, gap 72 starts at 31397, difference is 141962.
 
Earliest difference > 1000000 between adjacent prime gap starting primes:
Gap 100 starts at 396733, gap 102 starts at 1444309, difference is 1047576.
 
Earliest difference > 10000000 between adjacent prime gap starting primes:
Gap 148 starts at 2010733, gap 150 starts at 13626257, difference is 11615524.
 
Earliest difference > 100000000 between adjacent prime gap starting primes:
Gap 198 starts at 46006769, gap 200 starts at 378043979, difference is 332037210.
</pre>
 
=={{header|Pascal}}==
==={{header|Free Pascal}}===
<langsyntaxhighlight lang="pascal">program primesieve;
// sieving small ranges of 65536
//{$O+,R+}
Line 836 ⟶ 1,246:
writeln('Press <Enter>');readln;
{$ENDIF}
end.</langsyntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Line 869 ⟶ 1,279:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Earliest_difference_between_prime_gaps
Line 892 ⟶ 1,302:
print "above $m gap @{[$i * 2 - 2 ]} abs( $gaps[$i-1] - $gaps[$i] )\n";
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 907 ⟶ 1,317:
=={{header|Phix}}==
{{trans|Wren}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1e7</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1e8</span><span style="color: #0000FF;">),</span>
Line 941 ⟶ 1,351:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</langsyntaxhighlight>-->
Output same as Wren. Takes 5s on desktop/Phix but would take 17s under p2js so limited that to keep it under 2s.
A limit of 1e9 needs 64 bit (hence not p2js compatible), and a multiplier of 5, and a gslim of 354, and takes 2 mins 43s, and nearly killed my poor little box, but matched the output of Julia, which managed it in 40s (and with no signs of any stress). Python needed more memory than I've got for 1e9, but took 15s for a limit of 1e8, while Wren (bless, also 1e8) took just over 3 minutes (an old i5/8GB/w10).
Line 947 ⟶ 1,357:
=={{header|Python}}==
{{trans|Julia, Wren}}
<langsyntaxhighlight lang="python">""" https://rosettacode.org/wiki/Earliest_difference_between_prime_gaps """
 
from primesieve import primes
Line 977 ⟶ 1,387:
else:
GAP1 = GAP2
</langsyntaxhighlight>{{out}}Same as Raku, Wren and Julia versions.
 
=={{header|Raku}}==
 
1e1 through 1e7 are pretty speedy (less than 5 seconds total). 1e8 and 1e9 take several minutes.
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
use Lingua::EN::Numbers;
 
Line 1,012 ⟶ 1,422:
|(2 * $key + 2, @upto[$key], 2 * $key + 4, @upto[$key+1], abs(@upto[$key] - @upto[$key+1]))».&comma;
True
}</langsyntaxhighlight>
{{out}}
<pre>Earliest difference > 10 between adjacent prime gap starting primes:
Line 1,042 ⟶ 1,452:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
 
Line 1,096 ⟶ 1,506:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,136 ⟶ 1,546:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func prime_gap_records(upto) {
 
var gaps = []
Line 1,159 ⟶ 1,569:
}
})
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,174 ⟶ 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 tofor reachthe firstearliest difference above 100 million) on my machine (core i7, 32GB RAM, Ubuntu 20.04).
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./fmt" for Fmt
var limit = 1e9
var gapStarts = {}
var primes = Int.segmentedSieve(limit * 5, 8 * 1024128 * 1024) // 8128 MBKB cache
for (i in 1...primes.count) {
var gap = primes[i] - primes[i-1]
Line 1,205 ⟶ 1,615:
gap1 = gap2
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,235 ⟶ 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>
Peak
2,442

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/317767...363556"