Next special primes
n is smallest prime such that the difference of successive terms is strictly increasing,
where n < 1050.
- Task
ALGOL W
<lang algolw>begin % find some primes where the gap between the current prtime and the next is greater than %
% the gap between previus primes and the current % % sets p( 1 :: n ) to a sieve of primes up to n % procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; begin p( 1 ) := false; p( 2 ) := true; for i := 3 step 2 until n do p( i ) := true; for i := 4 step 2 until n do p( i ) := false; for i := 3 step 2 until truncate( sqrt( n ) ) do begin integer ii; ii := i + i; if p( i ) then for pr := i * i step ii until n do p( pr ) := false end for_i ; end Eratosthenes ; integer MAX_NUMBER; MAX_NUMBER := 1050; begin logical array prime( 1 :: MAX_NUMBER ); integer pCount, pGap, thisPrime, nextPrime; % sieve the primes to MAX_NUMBER % Eratosthenes( prime, MAX_NUMBER ); % the first gap is 1 (between 2 and 3) the gap between all other primes is even % % so we treat 2-3 as a special case % write( " this next" ); write( "element prime prime gap" ); pCount := pGap := 1; thisPrime := 2; nextPrime := 3; write( i_w := 5, s_w := 0, " ", pCount, ":", thisPrime, " ", nextPrime, pGap ); pGap := 0; while thisPrime < MAX_NUMBER do begin thisPrime := nextPrime; while begin pGap := pGap + 2; nextPrime := thisPrime + pGap; nextPrime < MAX_NUMBER and not prime( nextPrime ) end do begin end; if nextPrime < MAX_NUMBER then begin pCount := pCount + 1; write( i_w := 5, s_w := 0, " ", pCount, ":", thisPrime, " ", nextPrime, pGap ) end if_nextPrime_lt_MAX_NUMBER end while_thisPrime_lt_MAX_NUMBER end
end.</lang>
- Output:
this next element prime prime gap 1: 2 3 1 2: 3 5 2 3: 5 11 6 4: 11 19 8 5: 19 29 10 6: 29 41 12 7: 41 59 18 8: 59 79 20 9: 79 101 22 10: 101 127 26 11: 127 157 30 12: 157 191 34 13: 191 227 36 14: 227 269 42 15: 269 313 44 16: 313 359 46 17: 359 409 50 18: 409 461 52 19: 461 521 60 20: 521 587 66 21: 587 659 72 22: 659 733 74 23: 733 809 76 24: 809 887 78 25: 887 967 80 26: 967 1049 82
AWK
<lang AWK>
- syntax: GAWK -f NEXT_SPECIAL_PRIMES.AWK
BEGIN {
start = 1 stop = 1050 print("Prime1 Prime2 Gap") last_special = 3 last_gap = 1 printf("%6d %6d %3d\n",2,3,last_gap) count = 1 for (i=start; i<=stop; i++) { if (is_prime(i) && i-last_special > last_gap) { last_gap = i - last_special printf("%6d %6d %3d\n",last_special,i,last_gap) last_special = i count++ } } printf("Next special primes %d-%d: %d\n",start,stop,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82 Next special primes 1-1050: 26
C
<lang c>#include <stdio.h>
- include <stdbool.h>
bool isPrime(int n) {
int d; if (n < 2) return false; if (!(n%2)) return n == 2; if (!(n%3)) return n == 3; d = 5; while (d*d <= n) { if (!(n%d)) return false; d += 2; if (!(n%d)) return false; d += 4; } return true;
}
int main() {
int i, lastSpecial = 3, lastGap = 1; printf("Special primes under 1,050:\n"); printf("Prime1 Prime2 Gap\n"); printf("%6d %6d %3d\n", 2, 3, lastGap); for (i = 5; i < 1050; i += 2) { if (isPrime(i) && (i-lastSpecial) > lastGap) { lastGap = i - lastSpecial; printf("%6d %6d %3d\n", lastSpecial, i, lastGap); lastSpecial = i; } }
}</lang>
- Output:
Special primes under 1,050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Next special primes. Nigel Galloway: March 26th., 2021 let mP=let mutable n,g=2,0 in primes32()|>Seq.choose(fun y->match y-n>g,n with (true,i)->g<-y-n; n<-y; Some(i,g,y) |_->None) mP|>Seq.takeWhile(fun(_,_,n)->n<1050)|>Seq.iteri(fun i (n,g,l)->printfn "n%d=%d n%d=%d n%d-n%d=%d" i n (i+1) l (i+1) i g) </lang>
- Output:
n0=2 n1=3 n1-n0=1 n1=3 n2=5 n2-n1=2 n2=5 n3=11 n3-n2=6 n3=11 n4=19 n4-n3=8 n4=19 n5=29 n5-n4=10 n5=29 n6=41 n6-n5=12 n6=41 n7=59 n7-n6=18 n7=59 n8=79 n8-n7=20 n8=79 n9=101 n9-n8=22 n9=101 n10=127 n10-n9=26 n10=127 n11=157 n11-n10=30 n11=157 n12=191 n12-n11=34 n12=191 n13=227 n13-n12=36 n13=227 n14=269 n14-n13=42 n14=269 n15=313 n15-n14=44 n15=313 n16=359 n16-n15=46 n16=359 n17=409 n17-n16=50 n17=409 n18=461 n18-n17=52 n18=461 n19=521 n19-n18=60 n19=521 n20=587 n20-n19=66 n20=587 n21=659 n21-n20=72 n21=659 n22=733 n22-n21=74 n22=733 n23=809 n23-n22=76 n23=809 n24=887 n24-n23=78 n24=887 n25=967 n25-n24=80 n25=967 n26=1049 n26-n25=82
Here's another way of writing the mP sequence above which is (hopefully) a little clearer: <lang fsharp> let mP = seq {
let mutable prevp, maxdiff = 2, 0 for p in primes32() do let diff = p - prevp if diff > maxdiff then yield (prevp, diff, p) maxdiff <- diff prevp <- p
} </lang>
Factor
<lang>USING: formatting io kernel math math.primes ;
"2 " write 1 3 [ dup 1050 < ] [
2dup "(%d) %d " printf [ + next-prime ] keep 2dup - nip swap
] while 2drop nl</lang>
- Output:
2 (1) 3 (2) 5 (6) 11 (8) 19 (10) 29 (12) 41 (18) 59 (20) 79 (22) 101 (26) 127 (30) 157 (34) 191 (36) 227 (42) 269 (44) 313 (46) 359 (50) 409 (52) 461 (60) 521 (66) 587 (72) 659 (74) 733 (76) 809 (78) 887 (80) 967 (82) 1049
FreeBASIC
<lang freebasic>#include "isprime.bas"
dim as integer p = 3, i = 2
print "2 3 "; 'special case do
if isprime( p + i ) then p += i print p;" "; end if i += 2
loop until p+i >=1050 : print</lang>
- Output:
2 3 5 11 19 29 41 59 79 101 127 157 191 227 269 313 359 409 461 521 587 659 733 809 887 967 1049
Go
<lang go>package main
import "fmt"
func sieve(limit int) []bool {
limit++ // True denotes composite, false denotes prime. c := make([]bool, limit) // all false by default c[0] = true c[1] = true // no need to bother with even numbers over 2 for this task p := 3 // Start from 3. for { p2 := p * p if p2 >= limit { break } for i := p2; i < limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } return c
}
func main() {
c := sieve(1049) fmt.Println("Special primes under 1,050:") fmt.Println("Prime1 Prime2 Gap") lastSpecial := 3 lastGap := 1 fmt.Printf("%6d %6d %3d\n", 2, 3, lastGap) for i := 5; i < 1050; i += 2 { if !c[i] && (i-lastSpecial) > lastGap { lastGap = i - lastSpecial fmt.Printf("%6d %6d %3d\n", lastSpecial, i, lastGap) lastSpecial = i } }
}</lang>
- Output:
Special primes under 1,050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
Java
<lang java>class SpecialPrimes {
private static boolean isPrime(int n) { if (n < 2) return false; if (n%2 == 0) return n == 2; if (n%3 == 0) return n == 3; int d = 5; while (d*d <= n) { if (n%d == 0) return false; d += 2; if (n%d == 0) return false; d += 4; } return true; }
public static void main(String[] args) { System.out.println("Special primes under 1,050:"); System.out.println("Prime1 Prime2 Gap"); int lastSpecial = 3; int lastGap = 1; System.out.printf("%6d %6d %3d\n", 2, 3, lastGap); for (int i = 5; i < 1050; i += 2) { if (isPrime(i) && (i-lastSpecial) > lastGap) { lastGap = i - lastSpecial; System.out.printf("%6d %6d %3d\n", lastSpecial, i, lastGap); lastSpecial = i; } } }
}</lang>
- Output:
Special primes under 1,050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
Julia
<lang julia>using Primes
let
println("Special primes under 1050:\nPrime1 Prime2 Gap") println(" 2 3 1") pmask = primesmask(1, 1050) n, gap = 3, 2 while n + gap < 1050 if pmask[n + gap] println(lpad(n, 6), lpad(n + gap, 6), lpad(gap, 4)) n += gap end gap += 2 end
end
</lang>
- Output:
Special primes under 1050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
Nim
<lang Nim>import strutils, sugar
func isPrime(n: Positive): bool =
if (n and 1) == 0: return n == 2 var m = 3 while m * m <= n: if n mod m == 0: return false inc m, 2 result = true
iterator nextSpecialPrimes(lim: Positive): int =
assert lim >= 3 yield 2 yield 3 var last = 3 var lastGap = 1 for n in countup(5, lim, 2): if not n.isPrime: continue if n - last > lastGap: lastGap = n - last last = n yield n
let list = collect(newSeq, for p in nextSpecialPrimes(1050): p) echo "List of next special primes less than 1050:" echo list.join(" ")</lang>
- Output:
List of next special primes less than 1050: 2 3 5 11 19 29 41 59 79 101 127 157 191 227 269 313 359 409 461 521 587 659 733 809 887 967 1049
Pascal
just showing the small difference to increasing prime gaps.
LastPrime is updated outside or inside If
<lang pascal> program NextSpecialprimes; //increasing prime gaps see //https://oeis.org/A002386 https://en.wikipedia.org/wiki/Prime_gap uses
sysutils, primTrial;
procedure GetIncreasingGaps; var
Gap,LastPrime,p : NativeUInt;
Begin
InitPrime; Writeln('next increasing prime gap'); writeln('Prime1':8,'Prime2':8,'Gap':4); Gap := 0; LastPrime := actPrime; repeat p := NextPrime; if p-LastPrime > Gap then Begin Gap := p-LastPrime; writeln(LastPrime:8,P:8,Gap:4);
end; LastPrime := p; until LastPrime > 1000;
end;
procedure NextSpecial; var
Gap,LastPrime,p : NativeUInt;
Begin
InitPrime; Writeln('next special prime'); writeln('Prime1':8,'Prime2':8,'Gap':4); Gap := 0; LastPrime := actPrime; repeat p := NextPrime; if p-LastPrime > Gap then Begin Gap := p-LastPrime; writeln(LastPrime:8,P:8,Gap:4); LastPrime := p; end;
until LastPrime > 1000;
end;
begin
GetIncreasingGaps; writeln; NextSpecial;
end.</lang>
- Output:
next increasing prime gap Prime1 Prime2 Gap 2 3 1 3 5 2 7 11 4 23 29 6 89 97 8 113 127 14 523 541 18 887 907 20 next special prime Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
Perl
<lang perl>use strict; use warnings; use feature <state say>; use ntheory 'primes';
my $limit = 1050;
sub is_special {
state $previous = 2; state $gap = 0; state @primes = @{primes( 2*$limit )};
shift @primes while $primes[0] <= $previous + $gap; $gap = $primes[0] - $previous; $previous = $primes[0]; [$previous, $gap];
}
my @specials = [2, 0]; do { push @specials, is_special() } until $specials[-1][0] >= $limit;
pop @specials; printf "%4d %4d\n", @$_ for @specials;</lang>
- Output:
2 0 3 1 5 2 11 6 19 8 29 10 41 12 59 18 79 20 101 22 127 26 157 30 191 34 227 36 269 42 313 44 359 46 409 50 461 52 521 60 587 66 659 72 733 74 809 76 887 78 967 80 1049 82
Phix
integer lastSpecial = 3, lastGap = 1 printf(1,"Special primes under 1,050:\n") printf(1,"Prime1 Prime2 Gap\n") printf(1,"%6d %6d %3d\n", {2, 3, lastGap}) for i=5 to 1050 by 2 do if is_prime(i) and (i-lastSpecial) > lastGap then lastGap = i - lastSpecial printf(1,"%6d %6d %3d\n", {lastSpecial, i, lastGap}) lastSpecial = i end if end for
- Output:
Special primes under 1,050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82
Raku
<lang perl6>sub is-special ( ($previous, $gap) ) {
state @primes = grep *.is-prime, 2..*; shift @primes while @primes[0] <= $previous + $gap; return ( @primes[0], @primes[0] - $previous );
}
my @specials = (2, 0), &is-special … *;
my $limit = @specials.first: :k, *.[0] > 1050;
say .fmt('%4d') for @specials.head($limit);</lang>
- Output:
2 0 3 1 5 2 11 6 19 8 29 10 41 12 59 18 79 20 101 22 127 26 157 30 191 34 227 36 269 42 313 44 359 46 409 50 461 52 521 60 587 66 659 72 733 74 809 76 887 78 967 80 1049 82
REXX
<lang rexx>/*REXX program finds next special primes: difference of successive terms is increasing.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1050 /* " " " " " " */ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */
@nsp= ' next special primes < ' commas(hi) , " such that the different of successive terms is increasing"
if cols>0 then say ' index │'center(@nsp , 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') op= @.1 /*assign oldPrime to the first prime.*/ nsp= 0; idx= 1 /*initialize number of nsp and index.*/ $= /*a list of nice primes (so far). */
do j=0; np= op + j /*assign newPrime to oldPrime + j */ if np>=hi then leave /*Is newPrimeN ≥ hi? Then leave loop.*/ if \!.np then iterate /*Is np a prime? Then skip this J.*/ nsp= nsp + 1 /*bump the number of nsp's. */ op= np /*set oldPrime to the value of newPrime*/ if cols==0 then iterate /*Build the list (to be shown later)? */ c= commas(np) /*maybe add commas to the number. */ $= $ right(c, max(w, length(c) ) ) /*add a nice prime ──► list, allow big#*/ if nsp//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'Found ' commas(nsp) @nsp exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to hi /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above five lines saves time*/ do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ next special primes < 1,050 such that the different of successive terms is increasing ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 11 19 29 41 59 79 101 11 │ 127 157 191 227 269 313 359 409 461 521 21 │ 587 659 733 809 887 967 1,049 Found 27 next special primes < 1,050 such that the different of successive terms is increasing
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl
Primes = [] limit1 = 100 oldPrime = 2
for n = 1 to limit1
nextPrime = oldPrime + n if isprime(nextPrime) add(Primes,nextPrime) oldPrime = nextPrime ok
next
see "prime1 prime2 Gap" + nl for n = 1 to Len(Primes)-1
diff = Primes[n+1] - Primes[n] see ""+ Primes[n] + " " + Primes[n+1] + " " + diff + nl
next
see nl + "done..." + nl
</lang>
- Output:
working... prime1 prime2 Gap 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82 done...
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var primes = Int.primeSieve(1049) System.print("Special primes under 1,050:") System.print("Prime1 Prime2 Gap") var lastSpecial = primes[1] var lastGap = primes[1] - primes[0] Fmt.print("$6d $6d $3d", primes[0], primes[1], lastGap) for (p in primes.skip(2)) {
if ((p - lastSpecial) > lastGap) { lastGap = p - lastSpecial Fmt.print("$6d $6d $3d", lastSpecial, p, lastGap) lastSpecial = p }
}</lang>
- Output:
Special primes under 1,050: Prime1 Prime2 Gap 2 3 1 3 5 2 5 11 6 11 19 8 19 29 10 29 41 12 41 59 18 59 79 20 79 101 22 101 127 26 127 157 30 157 191 34 191 227 36 227 269 42 269 313 44 313 359 46 359 409 50 409 461 52 461 521 60 521 587 66 587 659 72 659 733 74 733 809 76 809 887 78 887 967 80 967 1049 82