Successive prime differences

Successive prime differences is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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:

1. Differences of 2.
2. Differences of 1.
3. Differences of 2, 2.
4. Differences of 2, 4.
5. Differences of 4, 2.
6. Differences of 6, 4, 2.

• 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

1. https://pdfs.semanticscholar.org/78a1/7349819304863ae061df88dbcb26b4908f03.pdf
2. https://www.primepuzzles.net/puzzles/puzz_011.htm

Factor

Works with: Factor version 0.99

<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

Works with: Rakudo version 2019.03

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]