Earliest difference between prime gaps: Difference between revisions
(Added Java solution) |
(Added Rust solution) |
||
Line 383: | Line 383: | ||
Earliest difference > 1,000,000,000 between adjacent prime gap starting primes: |
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> |
Gap 276 starts at 649,580,171, gap 278 starts at 4,260,928,601, difference is 3,611,348,430</pre> |
||
=={{header|Rust}}== |
|||
<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; |
|||
} |
|||
} |
|||
}</lang> |
|||
{{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|Wren}}== |
=={{header|Wren}}== |
Revision as of 13:58, 22 November 2021
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.
gap | minimal starting prime |
ending prime |
---|---|---|
2 | 3 | 5 |
4 | 7 | 11 |
6 | 23 | 29 |
8 | 89 | 97 |
10 | 139 | 149 |
12 | 199 | 211 |
14 | 113 | 127 |
16 | 1831 | 1847 |
18 | 523 | 541 |
20 | 887 | 907 |
22 | 1129 | 1151 |
24 | 1669 | 1693 |
26 | 2477 | 2503 |
28 | 2971 | 2999 |
30 | 4297 | 4327 |
This task involves locating the minimal primes corresponding to those gaps.
Though every gap value exists, they don't seem to come in any particular order. For example, this table shows the gaps and minimum starting value primes for 2 through 30:
For the purposes of this task, considering only primes greater than 2, consider prime gaps that differ by exactly two to be adjacent.
- Task
For each order of magnitude m from 10¹ through 10⁶:
- Find the first two sets of adjacent minimum prime gaps where where the absolute value of the difference between the prime gap start values is greater than m.
- E.G.
For an m of 10¹;
The start value of gap 2 is 3, the start value of gap 4 is 7, the difference is 7 - 3 or 4. 4 < 10¹ so keep going.
The start value of gap 4 is 7, the start value of gap 6 is 23, the difference is 23 - 7, or 16. 16 > 10¹ so this the earliest adjacent gap difference > 10¹.
- Stretch goal
- Do the same for 10⁷ and 10⁸ (and higher?) orders of magnitude
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.
Java
Uses the PrimeGenerator class from Extensible prime generator#Java. <lang java>import java.util.HashMap; import java.util.Map;
public class PrimeGaps {
private Map<Integer, Integer> gapStarts = new HashMap<>(); int lastPrime; 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; } }
}</lang>
- Output:
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.
Julia
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. <lang julia>using Formatting using Primes
function primegaps(limit = 10^9)
c(n) = format(n, commas=true) pri = primes(limit * 5) gapstarts = Dict{Int, Int}() for i in 2:length(pri) get!(gapstarts, pri[i] - pri[i - 1], pri[i - 1]) end pm, gap1 = 10, 2 while true while !haskey(gapstarts, gap1) gap1 += 2 end start1 = gapstarts[gap1] gap2 = gap1 + 2 if !haskey(gapstarts, gap2) gap1 = gap2 + 2 continue end start2 = gapstarts[gap2] if ((diff = abs(start2 - start1)) > pm) println("Earliest difference > $(c(pm)) between adjacent prime gap starting primes:") println("Gap $gap1 starts at $(c(start1)), gap $(c(gap2)) starts at $(c(start2)), difference is $(c(diff)).\n") pm == limit && break pm *= 10 else gap1 = gap2 end end
end
primegaps()
</lang>
- Output:
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.
Perl
<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"; } }</lang>
- Output:
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 )
Phix
with javascript_semantics constant limit = iff(platform()=JS?1e7:1e8), gslim = 250 sequence primes = get_primes_le(limit*4), gapstarts = repeat(0,gslim) for i=2 to length(primes) do integer gap = primes[i]-primes[i-1] if gapstarts[gap]=0 then gapstarts[gap] = primes[i-1] end if end for integer pm = 10, gap1 = 2 while true do while gapstarts[gap1]=0 do gap1 += 2 end while integer start1 = gapstarts[gap1], gap2 = gap1 + 2 if gapstarts[gap2]=0 then gap1 = gap2 + 2 else integer start2 = gapstarts[gap2], diff = abs(start2 - start1) if diff>pm then printf(1,"Earliest difference >%,d between adjacent prime gap starting primes:\n",{pm}) printf(1,"Gap %d starts at %,d, gap %d starts at %,d, difference is %,d.\n\n", {gap1, start1, gap2, start2, diff}) if pm=limit then exit end if pm *= 10 else gap1 = gap2 end if end if end while
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).
Python
<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
</lang>
- Output:
Same as Raku, Wren and Julia versions.
Raku
1e1 through 1e7 are pretty speedy (less than 5 seconds total). 1e8 and 1e9 take several minutes. <lang perl6>use Math::Primesieve; use Lingua::EN::Numbers;
my $iterator = Math::Primesieve::iterator.new; my @gaps; my $last = 2;
for 1..9 {
my $m = exp $_, 10; my $this; loop { $this = (my $p = $iterator.next) - $last; if !@gaps[$this].defined { @gaps[$this]= $last; check-gap($m, $this, @gaps) && last if $this > 2 and @gaps[$this - 2].defined and (abs($last - @gaps[$this - 2]) > $m); } $last = $p; }
}
sub check-gap ($n, $this, @p) {
my %upto = @p[^$this].pairs.grep: *.value; my @upto = (1..$this).map: { last unless %upto{$_ * 2}; %upto{$_ * 2} } my $key = @upto.rotor(2=>-1).first( {.sink; abs(.[0] - .[1]) > $n}, :k ); return False unless $key; say "Earliest difference > {comma $n} between adjacent prime gap starting primes:"; printf "Gap %s starts at %s, gap %s starts at %s, difference is %s\n\n", |(2 * $key + 2, @upto[$key], 2 * $key + 4, @upto[$key+1], abs(@upto[$key] - @upto[$key+1]))»., True
}</lang>
- Output:
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
Rust
<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; } }
}</lang>
- Output:
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.
Wren
Unfortunately, my machine doesn't have enough memory to look for the earliest difference > 1 billion.
This takes 23 seconds to run on my machine (core i7, 32GB RAM, Ubuntu 20.04) which is what I'd expect as Wren is typically 4 or 5 times slower than Phix.
If anyone's wondering why I can't sieve 5 billion numbers with this much RAM, the reason is that bools require 8 bytes of storage in Wren (all value types do) compared to only 1 byte in most statically typed languages (or even 1 bit if they support bitarrays). <lang ecmascript>import "./math" for Int import "/fmt" for Fmt
var limit = 1e8 var gapStarts = {} var primes = Int.primeSieve(limit * 4) for (i in 1...primes.count) {
var gap = primes[i] - primes[i-1] if (!gapStarts[gap]) gapStarts[gap] = primes[i-1]
} 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 }
}</lang>
- Output:
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.