Successive prime differences: Difference between revisions
| Line 254: | Line 254: | ||
println("Diff Sequence Count First Last") |
println("Diff Sequence Count First Last") |
||
for delt in deltas |
for delt in deltas |
||
ret = trues(length(allprimes)) |
ret = trues(length(allprimes) - length(delt)) |
||
for (i, d) in enumerate(delt), j in 1:length(ret) |
|||
| ⚫ | |||
for (i, d) in enumerate(delt), j in 1:length(ret)-length(delt) |
|||
| ⚫ | |||
ret[j] = false |
ret[j] = false |
||
end |
end |
||
Revision as of 01:51, 1 May 2019
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
C#
<lang csharp>using System; using System.Collections.Generic; using static System.Linq.Enumerable;
public static class SuccessivePrimeDifferences {
public static void Main() {
var primes = GeneratePrimes(1_000_000).ToList();
foreach (var d in new[] {
new [] { 2 },
new [] { 1 },
new [] { 2, 2 },
new [] { 2, 4 },
new [] { 4, 2 },
new [] { 6, 4, 2 },
}) {
IEnumerable<int> first = null, last = null;
int count = 0;
foreach (var grp in FindDifferenceGroups(d)) {
if (first == null) first = grp;
last = grp;
count++;
}
Console.WriteLine($"{$"({string.Join(", ", first)})"}, {$"({string.Join(", ", last)})"}, {count}");
}
IEnumerable<IEnumerable<int>> FindDifferenceGroups(int[] diffs) {
for (int pi = diffs.Length; pi < primes.Count; pi++) {
if (Range(0, diffs.Length).All(di => primes[pi-diffs.Length+di+1] - primes[pi-diffs.Length+di] == diffs[di])) {
yield return Range(pi - diffs.Length, diffs.Length + 1).Select(i => primes[i]);
}
}
}
}
}</lang>
- Output:
(3, 5), (999959, 999961), 8169 (2, 3), (2, 3), 1 (3, 5, 7), (3, 5, 7), 1 (5, 7, 11), (999431, 999433, 999437), 1393 (7, 11, 13), (997807, 997811, 997813), 1444 (31, 37, 41, 43), (997141, 997147, 997151, 997153), 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
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
Julia
<lang julia>using Primes
function filterdifferences(deltas, N)
allprimes = primes(N)
differences = map(i -> allprimes[i + 1] - allprimes[i], 1:length(allprimes) - 1)
println("Diff Sequence Count First Last")
for delt in deltas
ret = trues(length(allprimes) - length(delt))
for (i, d) in enumerate(delt), j in 1:length(ret)
if ret[j] && differences[j - 1 + i] != d
ret[j] = false
end
end
count, p1, pn, n = sum(ret), findfirst(ret), findlast(ret), length(delt)
println(rpad(string(delt), 16), lpad(count, 4),
lpad(string(allprimes[p1:p1 + n]), 18), "...", rpad(allprimes[pn:pn+n], 15))
end
end
filterdifferences([[2], [1], [2, 2], [2, 4], [4, 2], [6, 4, 2]], 1000000)
</lang>
- Output:
Diff Sequence Count First Last [2] 8169 [3, 5]...[999959, 999961] [1] 1 [2, 3]...[2, 3] [2, 2] 1 [3, 5, 7]...[3, 5, 7] [2, 4] 1393 [5, 7, 11]...[999431, 999433, 999437] [4, 2] 1444 [7, 11, 13]...[997807, 997811, 997813] [6, 4, 2] 306 [31, 37, 41, 43]...[997141, 997147, 997151, 997153]
Perl
<lang perl>use 5.010; use strict; use warnings; no warnings 'experimental::smartmatch';
use List::EachCons; use ntheory 'primes';
my $limit = 1E6; my @primes = (2, @{ primes($limit) }); my @intervals = map { $primes[$_] - $primes[$_-1] } 1..$#primes;
say "Groups of successive primes <= $limit";
for my $diffs ([2], [1], [2,2], [2,4], [4,2], [6,4,2]) {
my $n = -1;
my @offsets = grep {$_} each_cons @$diffs, @intervals, sub { $n++; $n if @_ ~~ @$diffs };
printf "%10s has %5d sets: %15s … %s\n",
'(' . join(' ',@$diffs) . ')',
scalar @offsets,
join(' ', @primes[$offsets[ 0]..($offsets[ 0]+@$diffs)]),
join(' ', @primes[$offsets[-1]..($offsets[-1]+@$diffs)]);
}</lang>
- Output:
(2) has 8169 sets: 3 5 … 999959 999961
(1) has 1 sets: 2 3 … 2 3
(2 2) has 1 sets: 3 5 7 … 3 5 7
(2 4) has 1393 sets: 5 7 11 … 999431 999433 999437
(4 2) has 1444 sets: 7 11 13 … 997807 997811 997813
(6 4 2) has 306 sets: 31 37 41 43 … 997141 997147 997151 997153
Perl 6
Categorized by Successive
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
Precomputed Differences
<lang perl6>use Math::Primesieve;
constant $max = 1_000_000; constant @primes = Math::Primesieve.primes($max); constant @diffs = @primes.skip Z- @primes;
say "Given all ordered primes <= $max, sets with successive differences of:"; for (2,), (1,), (2,2), (2,4), (4,2), (6,4,2) -> @succ {
my $size = @succ.elems;
my @group_start_offsets = @diffs.rotor( $size => 1-$size )
.grep(:k, { $_ eqv @succ });
my ($first, $last) = @group_start_offsets[0, *-1]
.map: { @primes.skip($_).head($size + 1) };
say sprintf '%10s has %5d sets: %15s … %s',
@succ.gist, @group_start_offsets.elems, $first, $last;
}</lang>
- Output:
Given all ordered primes <= 1000000, sets with successive differences of:
(2) has 8169 sets: 3 5 … 999959 999961
(1) has 1 sets: 2 3 … 2 3
(2 2) has 1 sets: 3 5 7 … 3 5 7
(2 4) has 1393 sets: 5 7 11 … 999431 999433 999437
(4 2) has 1444 sets: 7 11 13 … 997807 997811 997813
(6 4 2) has 306 sets: 31 37 41 43 … 997141 997147 997151 997153
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
Ruby
<lang ruby>require 'prime' PRIMES = Prime.each(1_000_000).to_a difs = [[2], [1], [2,2], [2,4], [4,2], [6,4,2]]
difs.each do |ar|
res = PRIMES.each_cons(ar.size+1).select do |slice|
slice.each_cons(2).zip(ar).all? {|(a,b), c| a+c == b}
end
puts "#{ar} has #{res.size} sets. #{res.first}...#{res.last}"
end </lang>
- Output:
[2] has 8169 sets. [3, 5]...[999959, 999961] [1] has 1 sets. [2, 3]...[2, 3] [2, 2] has 1 sets. [3, 5, 7]...[3, 5, 7] [2, 4] has 1393 sets. [5, 7, 11]...[999431, 999433, 999437] [4, 2] has 1444 sets. [7, 11, 13]...[997807, 997811, 997813] [6, 4, 2] has 306 sets. [31, 37, 41, 43]...[997141, 997147, 997151, 997153]
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.
Treat this as a string search problem. <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("Successive primes (<=%,d) with deltas of %s (%,d groups):"
.fmt(PRIME_LIMIT,w.concat(","),r.len()));
println(" First group: %s; Last group: %s\n"
.fmt(r[0].concat(", "),r[-1].concat(", ")));
}</lang>
- Output:
Successive primes (<=1,000,000) with deltas of 2 (8,169 groups): First group: 3, 5; Last group: 999959, 999961 Successive primes (<=1,000,000) with deltas of 1 (1 groups): First group: 2, 3; Last group: 2, 3 Successive primes (<=1,000,000) with deltas of 2,2 (1 groups): First group: 3, 5, 7; Last group: 3, 5, 7 Successive primes (<=1,000,000) with deltas of 2,4 (1,393 groups): First group: 5, 7, 11; Last group: 999431, 999433, 999437 Successive primes (<=1,000,000) with deltas of 4,2 (1,444 groups): First group: 7, 11, 13; Last group: 997807, 997811, 997813 Successive primes (<=1,000,000) with deltas of 6,4,2 (306 groups): First group: 31, 37, 41, 43; Last group: 997141, 997147, 997151, 997153