Earliest difference between prime gaps: Difference between revisions

← Older edit

Earliest difference between prime gaps (view source)

Revision as of 18:42, 13 April 2024

51,258 bytes added , 1 month ago

→‎{{header|jq}}

Peak

2,442

edits

Revision as of 22:32, 20 November 2021 (view source) Wherrera (talk \| contribs) m (sp) ← Older edit		Latest revision as of 18:42, 13 April 2024 (view source) Peak (talk \| contribs) (→‎{{header\|jq}})
(32 intermediate revisions by 14 users not shown)
Line 1: {{~~draft~~ task}} When calculating prime numbers > 2, the difference between adjacent primes is always an even number. This difference, also referred to as the gap, varies in an random pattern; at least, no pattern has ever been discovered, and it is strongly conjectured that no pattern exists. However, it is also conjectured that between some two adjacent primes will be a gap corresponding to every positive even integer. Line 52: For each order of magnitude '''m''' from '''10¹''' through '''10⁶''': * Find the first two sets of minimum adjacent ~~minimum~~ prime gaps ~~where~~ where the absolute value of the difference between the prime gap start values is greater than '''m'''. 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}} <syntaxhighlight lang="cpp">#include <iostream> #include <locale> #include <unordered_map> #include <primesieve.hpp> class prime_gaps { public: prime_gaps() { last_prime_ = iterator_.next_prime(); } uint64_t find_gap_start(uint64_t gap); private: primesieve::iterator iterator_; uint64_t last_prime_; std::unordered_map<uint64_t, uint64_t> gap_starts_; }; uint64_t prime_gaps::find_gap_start(uint64_t gap) { auto i = gap_starts_.find(gap); if (i != gap_starts_.end()) return i->second; for (;;) { uint64_t prev = last_prime_; last_prime_ = iterator_.next_prime(); uint64_t diff = last_prime_ - prev; gap_starts_.emplace(diff, prev); if (gap == diff) return prev; } } int main() { std::cout.imbue(std::locale("")); const uint64_t limit = 100000000000; prime_gaps pg; for (uint64_t pm = 10, gap1 = 2;;) { uint64_t start1 = pg.find_gap_start(gap1); uint64_t gap2 = gap1 + 2; uint64_t start2 = pg.find_gap_start(gap2); uint64_t diff = start2 > start1 ? start2 - start1 : start1 - start2; if (diff > pm) { std::cout << "Earliest difference > " << pm << " between adjacent prime gap starting primes:\n" << "Gap " << gap1 << " starts at " << start1 << ", gap " << gap2 << " starts at " << start2 << ", difference is " << diff << ".\n\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 1,831, difference is 1,718. Earliest difference > 1,000 between adjacent prime gap starting primes: Gap 14 starts at 113, gap 16 starts at 1,831, difference is 1,718. Earliest difference > 10,000 between adjacent prime gap starting primes: Gap 36 starts at 9,551, gap 38 starts at 30,593, difference is 21,042. Earliest difference > 100,000 between adjacent prime gap starting primes: Gap 70 starts at 173,359, gap 72 starts at 31,397, difference is 141,962. Earliest difference > 1,000,000 between adjacent prime gap starting primes: Gap 100 starts at 396,733, gap 102 starts at 1,444,309, difference is 1,047,576. Earliest difference > 10,000,000 between adjacent prime gap starting primes: Gap 148 starts at 2,010,733, gap 150 starts at 13,626,257, difference is 11,615,524. Earliest difference > 100,000,000 between adjacent prime gap starting primes: Gap 198 starts at 46,006,769, gap 200 starts at 378,043,979, difference is 332,037,210. 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. 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. Earliest difference > 100,000,000,000 between adjacent prime gap starting primes: Gap 386 starts at 35,238,645,587, gap 388 starts at 156,798,792,223, difference is 121,560,146,636. </pre> =={{header\|F_Sharp\|F#}}== This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] <syntaxhighlight lang="fsharp"> // Earliest difference between prime gaps. Nigel Galloway: December 1st., 2021 let fN y=let i=System.Collections.Generic.SortedDictionary<int64,int64>() let fN()=i\|>Seq.pairwise\|>Seq.takeWhile(fun(n,g)->g.Key=n.Key+2L)\|>Seq.tryFind(fun(n,g)->abs(n.Value-g.Value)>y) (fun(n,g)->let e=g-n in match i.TryGetValue(e) with (false,_)->i.Add(e,n); fN() \|_->None) [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> {{out}} <pre> 10 -> distance between start of gap 4=7 and start of gap 6=23 is 16 100 -> distance between start of gap 14=113 and start of gap 16=1831 is 1718 1000 -> distance between start of gap 14=113 and start of gap 16=1831 is 1718 10000 -> distance between start of gap 36=9551 and start of gap 38=30593 is 21042 100000 -> distance between start of gap 70=173359 and start of gap 72=31397 is 141962 1000000 -> distance between start of gap 100=396733 and start of gap 102=1444309 is 1047576 10000000 -> distance between start of gap 148=2010733 and start of gap 150=13626257 is 11615524 100000000 -> distance between start of gap 198=46006769 and start of gap 200=378043979 is 332037210 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}} <syntaxhighlight lang="go">package main import ( "fmt" "rcu" ) func main() { limit := int(1e9) gapStarts := make(map[int]int) primes := rcu.Primes(limit * 5) for i := 1; i < len(primes); i++ { gap := primes[i] - primes[i-1] if _, ok := gapStarts[gap]; !ok { gapStarts[gap] = primes[i-1] } } pm := 10 gap1 := 2 for { for _, ok := gapStarts[gap1]; !ok; { gap1 += 2 } start1 := gapStarts[gap1] gap2 := gap1 + 2 if _, ok := gapStarts[gap2]; !ok { gap1 = gap2 + 2 continue } start2 := gapStarts[gap2] diff := start2 - start1 if diff < 0 { diff = -diff } if diff > pm { cpm := rcu.Commatize(pm) cst1 := rcu.Commatize(start1) cst2 := rcu.Commatize(start2) cd := rcu.Commatize(diff) fmt.Printf("Earliest difference > %s between adjacent prime gap starting primes:\n", cpm) fmt.Printf("Gap %d starts at %s, gap %d starts at %s, difference is %s.\n\n", gap1, cst1, gap2, cst2, cd) 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 1,831, difference is 1,718. Earliest difference > 1,000 between adjacent prime gap starting primes: Gap 14 starts at 113, gap 16 starts at 1,831, difference is 1,718. Earliest difference > 10,000 between adjacent prime gap starting primes: Gap 36 starts at 9,551, gap 38 starts at 30,593, difference is 21,042. Earliest difference > 100,000 between adjacent prime gap starting primes: Gap 70 starts at 173,359, gap 72 starts at 31,397, difference is 141,962. Earliest difference > 1,000,000 between adjacent prime gap starting primes: Gap 100 starts at 396,733, gap 102 starts at 1,444,309, difference is 1,047,576. Earliest difference > 10,000,000 between adjacent prime gap starting primes: Gap 148 starts at 2,010,733, gap 150 starts at 13,626,257, difference is 11,615,524. Earliest difference > 100,000,000 between adjacent prime gap starting primes: Gap 198 starts at 46,006,769, gap 200 starts at 378,043,979, difference is 332,037,210. 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> =={{header\|J}}== Implementation: <syntaxhighlight lang="j">lowpgap=: {{ magnitude=. ref=. 10^y whilst. -.1 e. ok do. magnitude=. 10magnitude 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]]. <syntaxhighlight lang="java">import java.util.HashMap; import java.util.Map; public class PrimeGaps { private Map<Integer, Integer> gapStarts = new HashMap<>(); private int lastPrime; private PrimeGenerator primeGenerator = new PrimeGenerator(1000, 500000); public static void main(String[] args) { final int limit = 100000000; PrimeGaps pg = new PrimeGaps(); for (int pm = 10, gap1 = 2;;) { int start1 = pg.findGapStart(gap1); int gap2 = gap1 + 2; int start2 = pg.findGapStart(gap2); int diff = start2 > start1 ? start2 - start1 : start1 - start2; if (diff > pm) { System.out.printf( "Earliest difference > %,d between adjacent prime gap starting primes:\n" + "Gap %,d starts at %,d, gap %,d starts at %,d, difference is %,d.\n\n", pm, gap1, start1, gap2, start2, diff); if (pm == limit) break; pm = 10; } else { gap1 = gap2; } } } private int findGapStart(int gap) { Integer start = gapStarts.get(gap); if (start != null) return start; for (;;) { int prev = lastPrime; lastPrime = primeGenerator.nextPrime(); int diff = lastPrime - prev; gapStarts.putIfAbsent(diff, prev); if (diff == gap) return prev; } } }</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 1,831, difference is 1,718. Earliest difference > 1,000 between adjacent prime gap starting primes: Gap 14 starts at 113, gap 16 starts at 1,831, difference is 1,718. Earliest difference > 10,000 between adjacent prime gap starting primes: Gap 36 starts at 9,551, gap 38 starts at 30,593, difference is 21,042. Earliest difference > 100,000 between adjacent prime gap starting primes: Gap 70 starts at 173,359, gap 72 starts at 31,397, difference is 141,962. Earliest difference > 1,000,000 between adjacent prime gap starting primes: Gap 100 starts at 396,733, gap 102 starts at 1,444,309, difference is 1,047,576. Earliest difference > 10,000,000 between adjacent prime gap starting primes: Gap 148 starts at 2,010,733, gap 150 starts at 13,626,257, difference is 11,615,524. Earliest difference > 100,000,000 between adjacent prime gap starting primes: Gap 198 starts at 46,006,769, gap 200 starts at 378,043,979, difference is 332,037,210. </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 ~~Raku's~~ 4. Going up to 10^10 runs out of memory on my machine. <~~lang~~syntaxhighlight lang="julia">using Formatting using Primes Line 107 ⟶ 701: primegaps() </~~lang~~syntaxhighlight>{{out}} <pre> Earliest difference > 10 between adjacent prime gap starting primes: Line 136 ⟶ 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]]; gaps = {Differences[primes], Most[primes]} // Transpose; tmp = GatherBy[gaps, First][[All, 1]]; tmp = SortBy[tmp, First]; starts = Association[Rule @@@ tmp]; set = {Most[tmp[[All, 1]]], Abs@Differences[tmp[[All, 2]]]} // Transpose; data = Table[{n, k} = SelectFirst[set, Last/GreaterThan[10^i]]; {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;</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.</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}}=== <syntaxhighlight lang="pascal">program primesieve; // sieving small ranges of 65536 //{$O+,R+} {$IFDEF FPC} {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$CODEALIGN proc=32} uses sysutils; {$ENDIF} {$IFDEF WINDOWS} {$APPTYPE CONSOLE} {$ENDIF} const smlPrimes :array [0..10] of Byte = (2,3,5,7,11,13,17,19,23,29,31); maxPreSievePrime = 17; sieveSize = 1 shl 15;//327682 ->max count of FoundPrimes = 6542 type tSievePrim = record svdeltaPrime:word;//diff between actual and new prime svSivOfs:word;//-> sieveSize< 1 shl 16 svSivNum:LongWord;// 1 shl (16+32) = 2.8e14 end; var {$Align 16} //primes up to 1E6-> sieving to 1E12 sievePrimes : array[0..78497] of tSievePrim; {$Align 16} preSieve :array[0..357111317-1] of Byte; {$Align 16} Sieve :array[0..sieveSize-1] of Byte; {$Align 16} FoundPrimes : array[0..6542] of LongWord; {$Align 16} Gaps : array[0..255] Of Uint64; {$Align 16} Limit,OffSet : Uint64; SieveMaxIdx, preSieveOffset, SieveNum, FoundPrimesCnt, PrimPos, LastInsertedSievePrime :NativeUInt; procedure CopyPreSieveInSieve;forward; procedure CollectPrimes;forward; procedure sieveOneSieve;forward; procedure preSieveInit; var i,pr,j,umf : NativeInt; Begin fillchar(preSieve[0],SizeOf(preSieve),#1); i := 1;// starts with pr = 3 umf := 1; repeat IF preSieve[i] <> 0 then Begin pr := 2i+1; j := i; repeat preSieve[j] := 0; inc(j,pr); until j> High(preSieve); umf := umfpr; end; inc(i); until umf>High(preSieve); preSieveOffset := 0; end; procedure CalcSievePrimOfs(lmt:NativeUint); var i,pr : NativeUInt; sq : Uint64; begin pr := 0; i := 0; repeat with sievePrimes[i] do Begin pr := pr+svdeltaPrime; IF sqr(pr) < (SieveSize2) then Begin svSivNum := 0; svSivOfs := (prpr-1) DIV 2; end else Begin SieveMaxIdx := i; pr := pr-svdeltaPrime; BREAK; end; end; inc(i); until i > lmt; for i := i to lmt do begin with sievePrimes[i] do Begin pr := pr+svdeltaPrime; sq := sqr(pr); svSivNum := sq DIV (2SieveSize); svSivOfs := ( (sq - Uint64(svSivNum)(2SieveSize))-1)DIV 2; end; end; end; procedure InitSieve; begin preSieveOffset := 0; SieveNum :=0; CalcSievePrimOfs(PrimPos-1); end; procedure InsertSievePrimes; var j :NativeUINt; i,pr : NativeUInt; begin i := 0; //ignore first primes already sieved with if SieveNum = 0 then repeat inc(i); until FoundPrimes[i] > maxPreSievePrime; pr :=0; j := Uint64(SieveNum)SieveSize2-LastInsertedSievePrime; with sievePrimes[PrimPos] do Begin pr := FoundPrimes[i]; svdeltaPrime := pr+j; j := pr; end; inc(PrimPos); for i := i+1 to FoundPrimesCnt-1 do Begin IF PrimPos > High(sievePrimes) then BREAK; with sievePrimes[PrimPos] do Begin pr := FoundPrimes[i]; svdeltaPrime := (pr-j); j := pr; end; inc(PrimPos); end; LastInsertedSievePrime :=Uint64(SieveNum)(SieveSize2)+pr; end; procedure sievePrimesInit; var i,j,pr:NativeInt; Begin LastInsertedSievePrime := 0; PrimPos := 0; preSieveOffset := 0; SieveNum :=0; CopyPreSieveInSieve; i := 1; // start with 3 repeat while Sieve[i] = 0 do inc(i); pr := 2i+1; inc(i); j := ((prpr)-1) DIV 2; if j > High(Sieve) then BREAK; repeat Sieve[j] := 0; inc(j,pr); until j > High(Sieve); until false; CollectPrimes; InsertSievePrimes; IF PrimPos < High(sievePrimes) then Begin InitSieve; //Erste Sieb nochmals, aber ohne Eintrag CopyPreSieveInSieve; sieveOneSieve; repeat inc(SieveNum); CopyPreSieveInSieve; sieveOneSieve; CollectPrimes; InsertSievePrimes; until PrimPos > High(sievePrimes); end; end; procedure OutGaps(g1,g2,delta:NativeUint); begin if g2= 0 then writeln(2g1:4,2g1+2:4,delta:13,Gaps[g1]:13,Gaps[g1+1]:13) else writeln(2g2-1:4,2g1:4,delta:13,Gaps[g1-1]:13,Gaps[g1]:13); end; function GetDiffval(val1,val2: NativeInt): NativeInt; begin if val1val2 = 0 then EXIT(0); dec(val1,val2); if val1<0 then val1 :=-val1; GetDiffval := val1; end; procedure CheckGaps; var val1,val2,val3,i,DekaLimit : NativeInt; Begin writeln('Gap1 Gap2 difference first second prime'); dekaLimit := 10; i := 1; repeat val1 := Gaps[i]; if val1 <> 0 then Begin val2 := GetDiffval(val1,Gaps[i-1]); val3 := GetDiffval(val1,Gaps[i+1]); while (val2>DekaLimit) or (val3>DekaLimit) do begin writeln(DekaLimit:21,'<'); if val2 = 0 then begin if val3 > 0 then OutGaps(i,0,val3); end else begin if val3 = 0 then OutGaps(i,1,val2) else Begin if val3 > val2 then OutGaps(i,0,val3) else OutGaps(i,1,val2); end; end; DekaLimit := 10DekaLimit; end; end; inc(i); until i>=254; end; procedure CopyPreSieveInSieve; var lmt : NativeInt; Begin lmt := preSieveOffset+sieveSize; lmt := lmt-(High(preSieve)+1); IF lmt<= 0 then begin Move(preSieve[preSieveOffset],Sieve[0],sieveSize); if lmt <> 0 then inc(preSieveOffset,sieveSize) else preSieveOffset := 0; end else begin Move(preSieve[preSieveOffset],Sieve[0],sieveSize-lmt); Move(preSieve[0],Sieve[sieveSize-lmt],lmt); preSieveOffset := lmt end; end; procedure CollectPrimes; var pSieve : pbyte; pFound : pLongWord; i,idx : NativeInt; Begin pFound := @FoundPrimes[0]; idx := 0; i := 0; IF SieveNum = 0 then Begin repeat pFound[idx] := smlPrimes[idx]; inc(idx); until smlPrimes[idx]>maxPreSievePrime; i := (smlPrimes[idx] -1) DIV 2; end; pSieve := @Sieve[0]; repeat pFound[idx]:= 2i+1; inc(idx,pSieve[i]); inc(i); until i>High(Sieve); FoundPrimesCnt:= idx; end; procedure sieveOneSieve; var i,j,pr,dSievNum :NativeUint; Begin pr := 0; For i := 0 to SieveMaxIdx do with sievePrimes[i] do begin pr := pr+svdeltaPrime; IF svSivNum = sieveNum then Begin j := svSivOfs; repeat Sieve[j] := 0; inc(j,pr); until j > High(Sieve); dSievNum := j DIV SieveSize; svSivOfs := j-dSievNumSieveSize; inc(svSivNum,dSievNum); end; end; i := SieveMaxIdx+1; repeat if i > High(SievePrimes) then BREAK; with sievePrimes[i] do begin if svSivNum > sieveNum then Begin SieveMaxIdx := I-1; Break; end; pr := pr+svdeltaPrime; j := svSivOfs; repeat Sieve[j] := 0; inc(j,pr); until j > High(Sieve); dSievNum := j DIV SieveSize; svSivOfs := j-dSievNumSieveSize; inc(svSivNum,dSievNum); inc(i); end; until false; end; var T1,T0,CNT,ActPrime,LastPrime,delta : Int64; i: Int32; begin T0 := GetTickCount64; Limit := 10100010001000;//158100010001000; preSieveInit; sievePrimesInit; InitSieve; offset := 0; Cnt := 1;//==2 LastPrime := 2; repeat CopyPreSieveInSieve;sieveOneSieve;CollectPrimes; inc(Cnt,FoundPrimesCnt); //collect first occurrence of gap i := 0; repeat ActPrime := Offset+FoundPrimes[i]; delta := (ActPrime - LastPrime) shr 1; If Gaps[delta] = 0 then Gaps[delta] := LastPrime; LastPrime := ActPrime; inc(i); until (i >= FoundPrimesCnt); inc(SieveNum); inc(offset,2SieveSize); until SieveNum > (Limit DIV (2SieveSize)); CheckGaps; T1 := GetTickCount64; OffSet := Uint64(SieveNum-1)(2SieveSize); i := FoundPrimesCnt; repeat dec(i); dec(cnt); until (i = 0) OR (OffSet+FoundPrimes[i]<Limit); writeln; writeln(cnt,' in ',Limit,' takes ',T1-T0,' ms'); {$IFDEF WINDOWS} writeln('Press <Enter>');readln; {$ENDIF} end.</syntaxhighlight> {{out\|@TIO.RUN}} <pre> Gap1 Gap2 difference first second prime 10< 4 6 16 7 23 100< 14 16 1718 113 1831 1000< 14 16 1718 113 1831 10000< 36 38 21042 9551 30593 100000< 70 72 141962 173359 31397 1000000< 100 102 1047576 396733 1444309 10000000< 148 150 11615524 2010733 13626257 100000000< 198 200 332037210 46006769 378043979 50847534 in 1000000000 takes 886 ms //@home primes til 158,000,000,000 like C++ 276 278 3611348430 649580171 4260928601 10000000000< 332 334 24933958388 5893180121 30827138509 100000000000< 386 388 121560146636 35238645587 156798792223 6385991032 in 158000000000 takes 247532 ms </pre> =={{header\|Perl}}== <syntaxhighlight lang="perl">#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/Earliest_difference_between_prime_gaps use warnings; use ntheory qw( primes ); my @gaps; my $primeref = primes( 1e9 ); for my $i ( 2 .. $#$primeref ) { my $diff = $primeref->[$i] - $primeref->[$i - 1]; $gaps[ $diff >> 1 ] //= $primeref->[$i - 1]; } my %first; for my $i ( 1 .. $#gaps ) { defined $gaps[$i] && defined $gaps[$i-1] or next; my $diff = abs $gaps[$i] - $gaps[$i-1]; for my $m ( map 10 * $_, 1 .. 10 ) { $diff > $m and !$first{$m}++ and print "above $m gap @{[$i * 2 - 2 ]} abs( $gaps[$i-1] - $gaps[$i] )\n"; } }</syntaxhighlight> {{out}} <pre> above 10 gap 4 abs( 7 - 23 ) above 100 gap 14 abs( 113 - 1831 ) above 1000 gap 14 abs( 113 - 1831 ) above 10000 gap 36 abs( 9551 - 30593 ) above 100000 gap 70 abs( 173359 - 31397 ) above 1000000 gap 100 abs( 396733 - 1444309 ) above 10000000 gap 148 abs( 2010733 - 13626257 ) above 100000000 gap 198 abs( 46006769 - 378043979 ) </pre> =={{header\|Phix}}== {{trans\|Wren}} <!--<syntaxhighlight lang="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> <span style="color: #000000;">gslim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">250</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;"></span><span style="color: #000000;">4</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">gapstarts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gslim</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">if</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gap1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> <span style="color: #008080;">while</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> <span style="color: #000000;">gap1</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">start1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">gap2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">2</span> <span style="color: #008080;">if</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">gap1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap2</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">2</span> <span style="color: #008080;">else</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">start2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gapstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gap2</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">diff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start2</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">start1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">></span><span style="color: #000000;">pm</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Earliest difference >%,d between adjacent prime gap starting primes:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pm</span><span style="color: #0000FF;">})</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Gap %d starts at %,d, gap %d starts at %,d, difference is %,d.\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">gap1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">start1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gap2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">start2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">if</span> <span style="color: #000000;">pm</span><span style="color: #0000FF;">=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">pm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span> <span style="color: #008080;">else</span> <span style="color: #000000;">gap1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap2</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <!--</syntaxhighlight>--> 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). =={{header\|Python}}== {{trans\|Julia, Wren}} <syntaxhighlight lang="python">""" https://rosettacode.org/wiki/Earliest_difference_between_prime_gaps """ from primesieve import primes LIMIT = 10*9 pri = primes(LIMIT 5) gapstarts = {} for i in range(1, len(pri)): if pri[i] - pri[i - 1] not in gapstarts: gapstarts[pri[i] - pri[i - 1]] = pri[i - 1] PM, GAP1, = 10, 2 while True: while GAP1 not in gapstarts: GAP1 += 2 start1 = gapstarts[GAP1] GAP2 = GAP1 + 2 if GAP2 not in gapstarts: GAP1 = GAP2 + 2 continue start2 = gapstarts[GAP2] diff = abs(start2 - start1) if diff > PM: print(f"Earliest difference >{PM: ,} between adjacent prime gap starting primes:") print(f"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}}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" ~~perl6~~line>use Math::Primesieve; use Lingua::EN::Numbers; Line 170 ⟶ 1,422: \|(2 $key + 2, @upto[$key], 2 * $key + 4, @upto[$key+1], abs(@upto[$key] - @upto[$key+1]))»., True }</~~lang~~syntaxhighlight> {{out}} <pre>Earliest difference > 10 between adjacent prime gap starting primes: Line 198 ⟶ 1,450: 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> =={{header\|Rust}}== <syntaxhighlight lang="rust">// [dependencies] // primal = "0.3" fn main() { use std::collections::HashMap; let mut primes = primal::Primes::all(); let mut last_prime = primes.next().unwrap(); let mut gap_starts = HashMap::new(); let mut find_gap_start = move \|gap: usize\| -> usize { if let Some(start) = gap_starts.get(&gap) { return start; } loop { let prev = last_prime; last_prime = primes.next().unwrap(); let diff = last_prime - prev; if !gap_starts.contains_key(&diff) { gap_starts.insert(diff, prev); } if gap == diff { return prev; } } }; let limit = 100000000000; let mut pm = 10; let mut gap1 = 2; loop { let start1 = find_gap_start(gap1); let gap2 = gap1 + 2; let start2 = find_gap_start(gap2); let diff = if start2 > start1 { start2 - start1 } else { start1 - start2 }; if diff > pm { println!( "Earliest difference > {} between adjacent prime gap starting primes:\n\ Gap {} starts at {}, gap {} starts at {}, difference is {}.\n", pm, gap1, start1, gap2, start2, diff ); 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. Earliest difference > 1000000000 between adjacent prime gap starting primes: Gap 276 starts at 649580171, gap 278 starts at 4260928601, difference is 3611348430. Earliest difference > 10000000000 between adjacent prime gap starting primes: Gap 332 starts at 5893180121, gap 334 starts at 30827138509, difference is 24933958388. Earliest difference > 100000000000 between adjacent prime gap starting primes: Gap 386 starts at 35238645587, gap 388 starts at 156798792223, difference is 121560146636. </pre> =={{header\|Sidef}}== <syntaxhighlight lang="ruby">func prime_gap_records(upto) { var gaps = [] var p = 3 each_prime(p.next_prime, upto, {\|q\| gaps[q-p] := p p = q }) gaps.grep { defined(_) } } var gaps = prime_gap_records(1e8) for m in (1 .. gaps.max.len) { gaps.each_cons(2, {\|p,q\| if (abs(q-p) > 10*m) { say "10^#{m} -> (#{p}, #{q}) with gaps (#{ p.next_prime-p}, #{q.next_prime-q}) and difference #{abs(q-p)}" break } }) }</syntaxhighlight> {{out}} <pre> 10^1 -> (7, 23) with gaps (4, 6) and difference 16 10^2 -> (113, 1831) with gaps (14, 16) and difference 1718 10^3 -> (113, 1831) with gaps (14, 16) and difference 1718 10^4 -> (9551, 30593) with gaps (36, 38) and difference 21042 10^5 -> (173359, 31397) with gaps (70, 72) and difference 141962 10^6 -> (396733, 1444309) with gaps (100, 102) and difference 1047576 10^7 -> (2010733, 13626257) with gaps (148, 150) and difference 11615524 </pre> =={{header\|Wren}}== {{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 for the earliest difference above 100 million) on my machine (core i7, 32GB RAM, Ubuntu 20.04). ~~Unfortunately, my machine doesn't have enough memory to look for the earliest difference > 1 billion.~~ <~~lang~~syntaxhighlight ~~ecmascript~~lang="wren">import "./math" for Int import "./fmt" for Fmt var limit = ~~1e8~~1e9 var gapStarts = {} var primes = Int.~~primeSieve~~segmentedSieve(limit 45, 128 * 1024) // 128 KB cache for (i in 1...primes.count) { var gap = primes[i] - primes[i-1] Line 233 ⟶ 1,615: gap1 = gap2 } }</~~lang~~syntaxhighlight> {{out}} Line 260 ⟶ 1,642: Earliest difference > 100,000,000 between adjacent prime gap starting primes: Gap 198 starts at 46,006,769, gap 200 starts at 378,043,979, difference is 332,037,210. 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>