Successive prime differences
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.
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
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
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
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]