Successive prime differences
You are encouraged to solve this task according to the task description, using any language you may know.
The series of increasing prime numbers begins: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
The task applies a filter to the series returning groups of successive primes, (s'primes), that differ from the next by a given value or values.
Example 1: Specifying that the difference between s'primes be 2
leads to the groups:
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ...
(Known as Twin primes or Prime pairs)
Example 2: Specifying more than one difference between s'primes leads to groups of size one greater than the number of differences. Differences of 2, 4
leads to the groups:
(5, 7, 11), (11, 13, 17), (17, 19, 23), (41, 43, 47), ...
.
In the first group 7 is two more than 5 and 11 is four more than 7; as well as 5, 7, and 11 being successive primes.
Differences are checked in the order of the values given, (differences of 4, 2
would give different groups entirely).
- Task
- In each case use a list of primes less than 1_000_000
- For the following Differences show the first and last group, as well as the number of groups found:
- Differences of
2
. - Differences of
1
. - Differences of
2, 2
. - Differences of
2, 4
. - Differences of
4, 2
. - Differences of
6, 4, 2
.
- Differences of
- Show output here.
Note: Generation of a list of primes is a secondary aspect of the task. Use of a built in function, well known library, or importing/use of prime generators from other Rosetta Code tasks is encouraged.
- references
Factor
<lang factor>USING: formatting fry grouping kernel math math.primes math.statistics sequences ; IN: rosetta-code.successive-prime-differences
- seq-diff ( seq diffs -- seq' quot )
dup [ length 1 + <clumps> ] dip '[ differences _ sequence= ] ; inline
- show ( seq diffs -- )
[ "...for differences %u:\n" printf ] keep seq-diff [ find nip { } like ] [ find-last nip { } like ] [ count ] 2tri "First group: %u\nLast group: %u\nCount: %d\n\n" printf ;
- successive-prime-differences ( -- )
"Groups of successive primes up to one million...\n" printf 1,000,000 primes-upto { { 2 } { 1 } { 2 2 } { 2 4 } { 4 2 } { 6 4 2 } } [ show ] with each ;
MAIN: successive-prime-differences</lang>
- Output:
Groups of successive primes up to one million... ...for differences { 2 }: First group: { 3 5 } Last group: { 999959 999961 } Count: 8169 ...for differences { 1 }: First group: { 2 3 } Last group: { 2 3 } Count: 1 ...for differences { 2 2 }: First group: { 3 5 7 } Last group: { 3 5 7 } Count: 1 ...for differences { 2 4 }: First group: { 5 7 11 } Last group: { 999431 999433 999437 } Count: 1393 ...for differences { 4 2 }: First group: { 7 11 13 } Last group: { 997807 997811 997813 } Count: 1444 ...for differences { 6 4 2 }: First group: { 31 37 41 43 } Last group: { 997141 997147 997151 997153 } Count: 306
Go
<lang go>package main
import "fmt"
func sieve(limit int) []int {
primes := []int{2} c := make([]bool, limit+1) // composite = true // no need to process even numbers > 2 p := 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 } } } for i := 3; i <= limit; i += 2 { if !c[i] { primes = append(primes, i) } } return primes
}
func successivePrimes(primes, diffs []int) [][]int {
var results [][]int dl := len(diffs)
outer:
for i := 0; i < len(primes)-dl; i++ { group := make([]int, dl+1) group[0] = primes[i] for j := i; j < i+dl; j++ { if primes[j+1]-primes[j] != diffs[j-i] { group = nil continue outer } group[j-i+1] = primes[j+1] } results = append(results, group) group = nil } return results
}
func main() {
primes := sieve(999999) diffsList := [][]int{{2}, {1}, {2, 2}, {2, 4}, {4, 2}, {6, 4, 2}} fmt.Println("For primes less than 1,000,000:-\n") for _, diffs := range diffsList { fmt.Println(" For differences of", diffs, "->") sp := successivePrimes(primes, diffs) if len(sp) == 0 { fmt.Println(" No groups found") continue } fmt.Println(" First group = ", sp[0]) fmt.Println(" Last group = ", sp[len(sp)-1]) fmt.Println(" Number found = ", len(sp)) fmt.Println() }
}</lang>
- Output:
For primes less than 1,000,000:- For differences of [2] -> First group = [3 5] Last group = [999959 999961] Number found = 8169 For differences of [1] -> First group = [2 3] Last group = [2 3] Number found = 1 For differences of [2 2] -> First group = [3 5 7] Last group = [3 5 7] Number found = 1 For differences of [2 4] -> First group = [5 7 11] Last group = [999431 999433 999437] Number found = 1393 For differences of [4 2] -> First group = [7 11 13] Last group = [997807 997811 997813] Number found = 1444 For differences of [6 4 2] -> First group = [31 37 41 43] Last group = [997141 997147 997151 997153] Number found = 306
Perl 6
Essentially the code from the Sexy primes task with minor tweaks.
<lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;
my $max = 1_000_000; my @primes = $sieve.primes($max); my $filter = @primes.Set; my $primes = @primes.categorize: &successive;
sub successive ($i) {
gather { take '2' if $filter{$i + 2}; take '1' if $filter{$i + 1}; take '2_2' if all($filter{$i «+« (2,4)}); take '2_4' if all($filter{$i «+« (2,6)}); take '4_2' if all($filter{$i «+« (4,6)}); take '6_4_2' if all($filter{$i «+« (6,10,12)}) and none($filter{$i «+« (2,4,8)}); }
}
sub comma { $^i.flip.comb(3).join(',').flip }
for (2,), (1,), (2,2), (2,4), (4,2), (6,4,2) -> $succ {
say "## Sets of {1+$succ} successive primes <= { comma $max } with " ~ "successive differences of { $succ.join: ', ' }"; my $i = $succ.join: '_'; for 'First', 0, ' Last', * - 1 -> $where, $ind { say "$where group: ", join ', ', [\+] flat $primes{$i}[$ind], |$succ } say ' Count: ', +$primes{$i}, "\n";
}</lang>
- Output:
## Sets of 2 successive primes <= 1,000,000 with successive differences of 2 First group: 3, 5 Last group: 999959, 999961 Count: 8169 ## Sets of 2 successive primes <= 1,000,000 with successive differences of 1 First group: 2, 3 Last group: 2, 3 Count: 1 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 2, 2 First group: 3, 5, 7 Last group: 3, 5, 7 Count: 1 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 2, 4 First group: 5, 7, 11 Last group: 999431, 999433, 999437 Count: 1393 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 4, 2 First group: 7, 11, 13 Last group: 997807, 997811, 997813 Count: 1444 ## Sets of 4 successive primes <= 1,000,000 with successive differences of 6, 4, 2 First group: 31, 37, 41, 43 Last group: 997141, 997147, 997151, 997153 Count: 306
Python
Uses the Sympy library.
<lang python># https://docs.sympy.org/latest/index.html from sympy import Sieve
def nsuccprimes(count, mx):
"return tuple of <count> successive primes <= mx (generator)" sieve = Sieve() sieve.extend(mx) primes = sieve._list return zip(*(primes[n:] for n in range(count)))
def check_value_diffs(diffs, values):
"Differences between successive values given by successive items in diffs?" return all(v[1] - v[0] == d for d, v in zip(diffs, zip(values, values[1:])))
def successive_primes(offsets=(2, ), primes_max=1_000_000):
return (sp for sp in nsuccprimes(len(offsets) + 1, primes_max) if check_value_diffs(offsets, sp))
if __name__ == '__main__':
for offsets, mx in [((2,), 1_000_000), ((1,), 1_000_000), ((2, 2), 1_000_000), ((2, 4), 1_000_000), ((4, 2), 1_000_000), ((6, 4, 2), 1_000_000), ]: print(f"## SETS OF {len(offsets)+1} SUCCESSIVE PRIMES <={mx:_} WITH " f"SUCCESSIVE DIFFERENCES OF {str(list(offsets))[1:-1]}") for count, last in enumerate(successive_primes(offsets, mx), 1): if count == 1: first = last print(" First group:", str(first)[1:-1]) print(" Last group:", str(last)[1:-1]) print(" Count:", count)</lang>
- Output:
## SETS OF 2 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2 First group: 3, 5 Last group: 999959, 999961 Count: 8169 ## SETS OF 2 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 1 First group: 2, 3 Last group: 2, 3 Count: 1 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2, 2 First group: 3, 5, 7 Last group: 3, 5, 7 Count: 1 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2, 4 First group: 5, 7, 11 Last group: 999431, 999433, 999437 Count: 1393 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 4, 2 First group: 7, 11, 13 Last group: 997807, 997811, 997813 Count: 1444 ## SETS OF 4 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 6, 4, 2 First group: 31, 37, 41, 43 Last group: 997141, 997147, 997151, 997153 Count: 306
REXX
<lang rexx>/*REXX program finds and displays primes with successive differences (up to a limit).*/ parse arg H . 1 . difs /*allow the highest number be specified*/ if H== | H=="," then H= 1000000 /*Not specified? Then use the default.*/ if difs= then difs= 2 1 2.2 2.4 4.2 6.4.2 /* " " " " " " */ call genP H
do j=1 for words(difs) /*traipse through the lists.*/ dif= translate( word(difs, j),,.); dw= words(dif) /*obtain true differences. */ do i=1 for dw; dif.i= word(dif, i) /*build an array of diffs. */ end /*i*/ /* [↑] for optimization. */ say center('primes with differences of:' dif, 50, '─') /*display title.*/ p= 1; c= 0; grp= /*init. prime#, count, grp.*/ do a=1; p= nextP(p+1); if p==0 then leave /*find the next DIF primes*/ aa= p; !.= /*AA: nextP; the group #'s.*/ !.1= p /*assign 1st prime in group.*/ do g=2 for dw /*get the rest of the group.*/ aa= nextP(aa+1); if aa==0 then leave a /*obtain the next prime. */ !.g= aa; _= g-1 /*prepare to add difference.*/ if !._ + dif._\==!.g then iterate a /*determine if fits criteria*/ end /*g*/ c= c+1 /*bump count of # of groups.*/ grp= !.1; do b=2 for dw; grp= grp !.b /*build a list of primes. */ end /*b*/ if c==1 then say ' first group: ' grp /*display the first group. */ end /*a*/ /* [↓] test if group found.*/ if grp== then say " (none)" /*display the last group. */ else say ' last group: ' grp /* " " " " */ say ' count: ' c /* " " group count. */ say end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ nextP: do nxt=arg(1) to H; if @.nxt==. then return nxt; end /*nxt*/; return 0 /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: procedure expose @.; parse arg N; != 0; @.=.; @.1= /*initialize the array.*/
do e=4 by 2 for (N-1)%2; @.e=; end /*treat the even integers > 2 special.*/ /*all primes are indicated with a "." */ do j=1 by 2 for (N-1)%2; k= j /*use odd integers up to N inclusive.*/ if @.j==. then do; if ! then iterate /*Prime? Should skip the top part ? */ jj= j * j /*compute the square of J. ___ */ if jj>N then != 1 /*indicate skip top part if j > √ N */ do m=jj to N by j+j; @.m=; end /*odd multiples.*/ end /* [↑] strike odd multiples ¬ prime. */</lang>
- output when using the default inputs:
──────────primes with differences of: 2─────────── first group: 3 5 last group: 999959 999961 count: 8169 ──────────primes with differences of: 1─────────── first group: 2 3 last group: 2 3 count: 1 ─────────primes with differences of: 2 2────────── first group: 3 5 7 last group: 3 5 7 count: 1 ─────────primes with differences of: 2 4────────── first group: 5 7 11 last group: 999431 999433 999437 count: 1393 ─────────primes with differences of: 4 2────────── first group: 7 11 13 last group: 997807 997811 997813 count: 1444 ────────primes with differences of: 6 4 2───────── first group: 31 37 41 43 last group: 997141 997147 997151 997153 count: 306
Sidef
<lang ruby>var limit = 1e6 var primes = limit.primes
say "Groups of successive primes <= #{limit.commify}:"
for diffs in [[2], [1], [2,2], [2,4], [4,2], [6,4,2]] {
var groups = [] primes.each_cons(diffs.len+1, {|*group| if (group.map_cons(2, {|a,b| b-a}) == diffs) { groups << group } })
say ("...for differences #{diffs}, there are #{groups.len} groups, where ", "the first group = #{groups.first} and the last group = #{groups.last}")
}</lang>
- Output:
Groups of successive primes <= 1,000,000: ...for differences [2], there are 8169 groups, where the first group = [3, 5] and the last group = [999959, 999961] ...for differences [1], there are 1 groups, where the first group = [2, 3] and the last group = [2, 3] ...for differences [2, 2], there are 1 groups, where the first group = [3, 5, 7] and the last group = [3, 5, 7] ...for differences [2, 4], there are 1393 groups, where the first group = [5, 7, 11] and the last group = [999431, 999433, 999437] ...for differences [4, 2], there are 1444 groups, where the first group = [7, 11, 13] and the last group = [997807, 997811, 997813] ...for differences [6, 4, 2], there are 306 groups, where the first group = [31, 37, 41, 43] and the last group = [997141, 997147, 997151, 997153]
zkl
GNU Multiple Precision Arithmetic Library
Using GMP ( probabilistic primes), because it is easy and fast to generate primes.
Extensible prime generator#zkl could be used instead. <lang zkl>const PRIME_LIMIT=1_000_000; var [const] BI=Import("zklBigNum"); // libGMP var [const] primeBitMap=Data(PRIME_LIMIT).fill(0x30); // one big string p:= BI(1); while(p.nextPrime()<=PRIME_LIMIT){ primeBitMap[p]="1" } // bitmap of primes
fcn primeWindows(m,deltas){ // eg (6,4,2)
n,r := 0,List(); ds:=deltas.len().pump(List,'wrap(n){ deltas[0,n+1].sum(0) }); // (6,10,12) sp:=Data(Void,"1" + "0"*deltas.sum(0)); foreach n in (ds){ sp[n]="1" } // "1000001000101" while(n=primeBitMap.find(sp,n+1)){ r.append(n) } // (31, 61, 271,...) r.apply('wrap(n){ T(n).extend(ds.apply('+(n))) }) //( (31,37,41,43), (61,67,71,73), (271,277,281,283) ...)
}</lang> <lang zkl>foreach w in (T( T(2), T(1), T(2,2), T(2,4), T(4,2), T(6,4,2) )){
r:=primeWindows(PRIME_LIMIT,w); println("Primes with deltas of %s (%,d groups):".fmt(w.concat(","),r.len())); println(" First group: %s; Last group: %s\n" .fmt(r[0].concat(", "),r[-1].concat(", ")));
}</lang>
- Output:
Primes with deltas of 2 (8,169 groups): First group: 3, 5; Last group: 999959, 999961 Primes with deltas of 1 (1 groups): First group: 2, 3; Last group: 2, 3 Primes with deltas of 2,2 (1 groups): First group: 3, 5, 7; Last group: 3, 5, 7 Primes with deltas of 2,4 (1,393 groups): First group: 5, 7, 11; Last group: 999431, 999433, 999437 Primes with deltas of 4,2 (1,444 groups): First group: 7, 11, 13; Last group: 997807, 997811, 997813 Primes with deltas of 6,4,2 (306 groups): First group: 31, 37, 41, 43; Last group: 997141, 997147, 997151, 997153