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.
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