Earliest difference between prime gaps
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 difference between the prime gap start value 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.
Raku
1e1 through 1e7 are pretty speedy (less than 5 seconds total). 1e8 and 1e9 take several minutes. <lang perl6>use Lingua::EN::Numbers;
my $iterator = Math::Primesieve::iterator.new; my @gaps; my $last = 2;
for 1..9 {
my $m = exp $_, 10;
my $this;
my $found;
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
Wren
Judging by the Raku solution, I've assumed that it's the absolute value of the difference that is to be tested. If not, for the earliest positive difference > 100,000, we'd have: Gap 72 starts at 31,397, gap 74 starts at 404,597, difference is 373,200.
Unfortunately, my machine doesn't have enough memory to look for the earliest difference > 1 billion. <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.