EKG sequence convergence

EKG sequence convergence 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.

This task is under review and the task goals may change in coming days. Be advised. Check the talk page

The sequence is from the natural numbers and is defined by:

• a(1) = 1;
• a(2) = Start = 2;
• for n > 2, a(n) shares at least one prime factor with a(n-1) and is the smallest such natural number not already used.

The sequence is called the EKG sequence (after its visual similarity to an electrocardiogram when graphed).

Variants of the sequence can be generated starting 1, N where N is any natural number larger than one. For the purposes of this task let us call:

• The sequence described above , starting 1, 2, ... the EKG(2) sequence;
• the sequence starting 1, 3, ... the EKG(3) sequence;
• ... the sequence starting 1, N, ... the EKG(N) sequence.

Convergence
If an algorithm that keeps track of the minimum amount of numbers and their corresponding prime factors used to generate the next term is used, then this may be known as the generators essential state. Two EKG generators with differing starts can converge to produce the same sequence after initial differences.
EKG(N1) and EKG(N2) are said to to have converged at and after generation a(c) if state_of(EKG(N1).a(c)) == state_of(EKG(N2).a(c)).

Task

1. Calculate and show here the first 30 members of EKG(2).
2. Calculate and show here the first 30 members of EKG(5).
3. Calculate and show here the first 30 members of EKG(7).
4. Calculate and show here the first 30 members of EKG(9).
5. Calculate and show here the first 30 members of EKG(10).
6. Stretch goal: Calculate and show here at which term EKG(5) and EKG(7) converge.

Reference

• The EKG Sequence and the Tree of Numbers. (Video).

C

Translation of: Go

<lang c>#include <stdio.h>

1. include <stdlib.h>

1. define TRUE 1
2. define FALSE 0
3. define LIMIT 100

typedef int bool;

int compareInts(const void *a, const void *b) {

   int aa = *(int *)a;
   int bb = *(int *)b;
   return aa - bb;

}

bool contains(int a[], int b, size_t len) {

   int i;
   for (i = 0; i < len; ++i) {
       if (a[i] == b) return TRUE;
   }
   return FALSE;

}

int gcd(int a, int b) {

   while (a != b) {
       if (a > b)
           a -= b;
       else
           b -= a;
   }
   return a;

}

bool areSame(int s[], int t[], size_t len) {

   int i;
   qsort(s, len, sizeof(int), compareInts);    
   qsort(t, len, sizeof(int), compareInts);
   for (i = 0; i < len; ++i) {
       if (s[i] != t[i]) return FALSE;
   }
   return TRUE;

}

int main() {

   int s, n, i;
   int starts[5] = {2, 5, 7, 9, 10};
   int ekg[5][LIMIT];
   for (s = 0; s < 5; ++s) {
       ekg[s][0] = 1;
       ekg[s][1] = starts[s];
       for (n = 2; n < LIMIT; ++n) {
           for (i = 2; ; ++i) {
               // a potential sequence member cannot already have been used
               // and must have a factor in common with previous member
               if (!contains(ekg[s], i, n) && gcd(ekg[s][n - 1], i) > 1) {
                   ekg[s][n] = i;
                   break;
               }
           }
       }
       printf("EKG(%2d): [", starts[s]);
       for (i = 0; i < 30; ++i) printf("%d ", ekg[s][i]);
       printf("\b]\n");
   }
   
   // now compare EKG5 and EKG7 for convergence
   for (i = 2; i < LIMIT; ++i) {
       if (ekg[1][i] == ekg[2][i] && areSame(ekg[1], ekg[2], i)) {
           printf("\nEKG(5) and EKG(7) converge at term %d\n", i + 1);
           return 0;
       }
   }
   printf("\nEKG5(5) and EKG(7) do not converge within %d terms\n", LIMIT);
   return 0;

}</lang>

Output:

EKG( 2): [1 2 4 6 3 9 12 8 10 5 15 18 14 7 21 24 16 20 22 11 33 27 30 25 35 28 26 13 39 36]
EKG( 5): [1 5 10 2 4 6 3 9 12 8 14 7 21 15 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32]
EKG( 7): [1 7 14 2 4 6 3 9 12 8 10 5 15 18 16 20 22 11 33 21 24 26 13 39 27 30 25 35 28 32]
EKG( 9): [1 9 3 6 2 4 8 10 5 15 12 14 7 21 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32]
EKG(10): [1 10 2 4 6 3 9 12 8 14 7 21 15 5 20 16 18 22 11 33 24 26 13 39 27 30 25 35 28 32]

EKG(5) and EKG(7) converge at term 21

Go

<lang go>package main

import (

   "fmt"
   "sort"

)

func contains(a []int, b int) bool {

   for _, j := range a {
       if j == b {
           return true
       }
   }
   return false

}

func gcd(a, b int) int {

   for a != b {
       if a > b {
           a -= b
       } else {
           b -= a
       }
   }
   return a

}

func areSame(s, t []int) bool {

   le := len(s)
   if le != len(t) {
       return false
   }
   sort.Ints(s)
   sort.Ints(t)
   for i := 0; i < le; i++ {
       if s[i] != t[i] {
           return false
       }
   }
   return true

}

func main() {

   const limit = 100
   starts := [5]int{2, 5, 7, 9, 10}
   var ekg [5][limit]int

   for s, start := range starts {
       ekg[s][0] = 1
       ekg[s][1] = start
       for n := 2; n < limit; n++ {
           for i := 2; ; i++ {
               // a potential sequence member cannot already have been used
               // and must have a factor in common with previous member
               if !contains(ekg[s][:n], i) && gcd(ekg[s][n-1], i) > 1 {
                   ekg[s][n] = i
                   break
               }
           }
       }
       fmt.Printf("EKG(%2d): %v\n", start, ekg[s][:30])
   }   

   // now compare EKG5 and EKG7 for convergence
   for i := 2; i < limit; i++ {
       if ekg[1][i] == ekg[2][i] && areSame(ekg[1][:i], ekg[2][:i]) {
           fmt.Println("\nEKG(5) and EKG(7) converge at term", i+1)
           return
       }
   }
   fmt.Println("\nEKG5(5) and EKG(7) do not converge within", limit, "terms")

}</lang>

Output:

EKG( 2): [1 2 4 6 3 9 12 8 10 5 15 18 14 7 21 24 16 20 22 11 33 27 30 25 35 28 26 13 39 36]
EKG( 5): [1 5 10 2 4 6 3 9 12 8 14 7 21 15 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32]
EKG( 7): [1 7 14 2 4 6 3 9 12 8 10 5 15 18 16 20 22 11 33 21 24 26 13 39 27 30 25 35 28 32]
EKG( 9): [1 9 3 6 2 4 8 10 5 15 12 14 7 21 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32]
EKG(10): [1 10 2 4 6 3 9 12 8 14 7 21 15 5 20 16 18 22 11 33 24 26 13 39 27 30 25 35 28 32]

EKG(5) and EKG(7) converge at term 21

Kotlin

Translation of: Go

<lang scala>// Version 1.2.60

fun gcd(a: Int, b: Int): Int {

   var aa = a
   var bb = b
   while (aa != bb) {
       if (aa > bb)
           aa -= bb
       else
           bb -= aa
   }
   return aa

}

const val LIMIT = 100

fun main(args: Array<String>) {

   val starts = listOf(2, 5, 7, 9, 10)
   val ekg = Array(5) { IntArray(LIMIT) }

   for ((s, start) in starts.withIndex()) {
       ekg[s][0] = 1
       ekg[s][1] = start
       for (n in 2 until LIMIT) {
           var i = 2
           while (true) {
               // a potential sequence member cannot already have been used
               // and must have a factor in common with previous member
               if (!ekg[s].slice(0 until n).contains(i) &&
                   gcd(ekg[s][n - 1], i) > 1) {
                       ekg[s][n] = i
                       break
               }
               i++
           }
       }
       System.out.printf("EKG(%2d): %s\n", start, ekg[s].slice(0 until 30))
   }   

   // now compare EKG5 and EKG7 for convergence
   for (i in 2 until LIMIT) {
       if (ekg[1][i] == ekg[2][i] &&
       ekg[1].slice(0 until i).sorted() == ekg[2].slice(0 until i).sorted()) {
           println("\nEKG(5) and EKG(7) converge at term ${i + 1}")
           return
       }
   }
   println("\nEKG5(5) and EKG(7) do not converge within $LIMIT terms")

}</lang>

Output:

EKG( 2): [1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27, 30, 25, 35, 28, 26, 13, 39, 36]
EKG( 5): [1, 5, 10, 2, 4, 6, 3, 9, 12, 8, 14, 7, 21, 15, 18, 16, 20, 22, 11, 33, 24, 26, 13, 39, 27, 30, 25, 35, 28, 32]
EKG( 7): [1, 7, 14, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 16, 20, 22, 11, 33, 21, 24, 26, 13, 39, 27, 30, 25, 35, 28, 32]
EKG( 9): [1, 9, 3, 6, 2, 4, 8, 10, 5, 15, 12, 14, 7, 21, 18, 16, 20, 22, 11, 33, 24, 26, 13, 39, 27, 30, 25, 35, 28, 32]
EKG(10): [1, 10, 2, 4, 6, 3, 9, 12, 8, 14, 7, 21, 15, 5, 20, 16, 18, 22, 11, 33, 24, 26, 13, 39, 27, 30, 25, 35, 28, 32]

EKG(5) and EKG(7) converge at term 21

Perl 6

Works with: Rakudo Star version 2018.04.1

<lang perl6>sub infix:<shares-divisors-with> { ($^a gcd $^b) > 1 }

sub next-EKG ( *@s ) {

   return first {
       @s ∌ $_  and  @s.tail shares-divisors-with $_
   }, 2..*;

}

sub EKG ( Int $start ) { 1, $start, &next-EKG … * }

say "EKG($_): ", .&EKG.head(30) for 2, 5, 7, 9, 10;</lang>

Output:

EKG(2): (1 2 4 6 3 9 12 8 10 5 15 18 14 7 21 24 16 20 22 11 33 27 30 25 35 28 26 13 39 36)
EKG(5): (1 5 10 2 4 6 3 9 12 8 14 7 21 15 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32)
EKG(7): (1 7 14 2 4 6 3 9 12 8 10 5 15 18 16 20 22 11 33 21 24 26 13 39 27 30 25 35 28 32)
EKG(9): (1 9 3 6 2 4 8 10 5 15 12 14 7 21 18 16 20 22 11 33 24 26 13 39 27 30 25 35 28 32)
EKG(10): (1 10 2 4 6 3 9 12 8 14 7 21 15 5 20 16 18 22 11 33 24 26 13 39 27 30 25 35 28 32)

Python

This example is incorrect. Please fix the code and remove this message. Details: EKG(10) produces: EKG(10): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5

Python: Using prime factor generation

<lang python>from itertools import count, islice, takewhile from functools import lru_cache

primes = [2, 3, 5, 7, 11, 13, 17] # Will be extended

@lru_cache(maxsize=2000) def pfactor(n):

   # From; http://rosettacode.org/wiki/Count_in_factors
   if n == 1:
       return [1]
   n2 = n // 2 + 1
   for p in primes:
       if p <= n2:
           d, m = divmod(n, p)
           if m == 0:
               if d > 1:
                   return [p] + pfactor(d)
               else:
                   return [p]
       else:
           if n > primes[-1]:
               primes.append(n)
           return [n]

def next_pfactor_gen():

   "Generate (n, set(pfactor(n))) pairs for n == 2, ..."
   for n in count(2):
       yield n, set(pfactor(n))

def EKG_gen(start=2):

   """\
   Generate the next term of the EKG together with the minimum cache of 
   numbers left in its production; (the "state" of the generator).
   """
   def min_share_pf_so_far(pf, so_far):
       "searches the unused smaller number prime factors"
       nonlocal found
       for index, (num, pfs) in enumerate(so_far):
           if pf & pfs:
               found = so_far.pop(index)
               break
       else:
           found = ()
       return found

   yield 1, []
   last, last_pf = start, set(pfactor(start))
   pf_gen = next_pfactor_gen()
   # minimum list of prime factors needed so far
   so_far = list(islice(pf_gen, start))
   found = ()
   while True:
       while not min_share_pf_so_far(last_pf, so_far):
           so_far.append(next(pf_gen))
       yield found[0], [n for n, _ in so_far]
       last, last_pf = found

1. %%

def find_convergence(ekgs=(5,7), limit=1_000):

   "Returns the convergence point or zero if not found within the limit"
   ekg = [EKG_gen(n) for n in ekgs]
   for e in ekg:
       next(e)    # skip initial 1 in each sequence
   differ = list(takewhile(lambda state: not all(state[0] == s for  s in state[1:]),
                           islice(zip(*ekg), limit-1)))
   ldiff = len(differ)
   return ldiff + 2 if ldiff < limit-1 else 0

1. %%

if __name__ == '__main__':

   for start in 2, 5, 7:
       print(f"EKG({start}):", str([n[0] for n in islice(EKG_gen(start), 10)])[1: -1])
   print(f"\nEKG(5) and EKG(7) converge at term {find_convergence(ekgs=(5,7))}!")</lang>

Output:

EKG(2): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5
EKG(5): 1, 5, 10, 2, 4, 6, 3, 9, 12, 8
EKG(7): 1, 7, 14, 2, 4, 6, 3, 9, 12, 8

EKG(5) and EKG(7) converge at term 21!

Python: Using math.gcd

If this alternate definition of function EKG_gen is used then the output would be the same as above. Instead of keeping a cache of prime factors this calculates the gretest common divisor as needed. <lang python>from itertools import count, islice, takewhile from math import gcd

def EKG_gen(start=2):

   """\
   Generate the next term of the EKG together with the minimum cache of 
   numbers left in its production; (the "state" of the generator).
   Using math.gcd
   """
   c = count(start + 1)
   last, so_far = start, list(range(2, start))
   yield 1, []
   yield last, []
   while True:
       for index, sf in enumerate(so_far):
           if gcd(last, sf) > 1:
               last = so_far.pop(index)
               yield last, so_far[::]
               break
       else:
           so_far.append(next(c))

def find_convergence(ekgs=(5,7)):

   "Returns the convergence point or zero if not found within the limit"
   ekg = [EKG_gen(n) for n in ekgs]
   for e in ekg:
       next(e)    # skip initial 1 in each sequence
   return 2 + len(list(takewhile(lambda state: not all(state[0] == s for  s in state[1:]),
                                 zip(*ekg))))

if __name__ == '__main__':

   for start in 2, 5, 7:
       print(f"EKG({start}):", str([n[0] for n in islice(EKG_gen(start), 10)])[1: -1])
   print(f"\nEKG(5) and EKG(7) converge at term {find_convergence(ekgs=(5,7))}!")</lang>

Output:

(Same as above).

EKG(2): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5
EKG(5): 1, 5, 10, 2, 4, 6, 3, 9, 12, 8
EKG(7): 1, 7, 14, 2, 4, 6, 3, 9, 12, 8

EKG(5) and EKG(7) converge at term 21!

Note

Despite EKG(5) and EKG(7) seeming to converge earlier, as seen above; their hidden states differ.
Here is those series out to 21 terms where you can see them diverge again before finally converging. The state is also shown. <lang python># After running the above, in the terminal: from pprint import pprint as pp

for start in 5, 7:

   print(f"EKG({start}):\n[(<next>, [<state>]), ...]")
   pp(([n for n in islice(EKG_gen(start), 21)]))</lang>

Generates:

EKG(5):
[(<next>, [<state>]), ...]
[(1, []),
 (5, []),
 (10, [2, 3, 4, 6, 7, 8, 9]),
 (2, [3, 4, 6, 7, 8, 9]),
 (4, [3, 6, 7, 8, 9]),
 (6, [3, 7, 8, 9]),
 (3, [7, 8, 9]),
 (9, [7, 8]),
 (12, [7, 8, 11]),
 (8, [7, 11]),
 (14, [7, 11, 13]),
 (7, [11, 13]),
 (21, [11, 13, 15, 16, 17, 18, 19, 20]),
 (15, [11, 13, 16, 17, 18, 19, 20]),
 (18, [11, 13, 16, 17, 19, 20]),
 (16, [11, 13, 17, 19, 20]),
 (20, [11, 13, 17, 19]),
 (22, [11, 13, 17, 19]),
 (11, [13, 17, 19]),
 (33, [13, 17, 19, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]),
 (24, [13, 17, 19, 23, 25, 26, 27, 28, 29, 30, 31, 32])]
EKG(7):
[(<next>, [<state>]), ...]
[(1, []),
 (7, []),
 (14, [2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]),
 (2, [3, 4, 5, 6, 8, 9, 10, 11, 12, 13]),
 (4, [3, 5, 6, 8, 9, 10, 11, 12, 13]),
 (6, [3, 5, 8, 9, 10, 11, 12, 13]),
 (3, [5, 8, 9, 10, 11, 12, 13]),
 (9, [5, 8, 10, 11, 12, 13]),
 (12, [5, 8, 10, 11, 13]),
 (8, [5, 10, 11, 13]),
 (10, [5, 11, 13]),
 (5, [11, 13]),
 (15, [11, 13]),
 (18, [11, 13, 16, 17]),
 (16, [11, 13, 17]),
 (20, [11, 13, 17, 19]),
 (22, [11, 13, 17, 19, 21]),
 (11, [13, 17, 19, 21]),
 (33, [13, 17, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]),
 (21, [13, 17, 19, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]),
 (24, [13, 17, 19, 23, 25, 26, 27, 28, 29, 30, 31, 32])]

zkl

Using gcd hint from Go. <lang zkl>fcn ekgW(N){ // --> iterator

  Walker.tweak(fcn(rp,buf,w){
     foreach n in (w){

if(rp.value.gcd(n)>1) { rp.set(n); w.push(buf.xplode()); buf.clear(); return(n); } buf.append(n); // save small numbers not used yet

     }
  }.fp(Ref(N),List(),Walker.chain([2..N-1],[N+1..]))).push(1,N)

}</lang> <lang zkl>foreach n in (T(2,5,7,9,10)){ println("EKG(%2d): %s".fmt(n,ekgW(n).walk(30).concat(","))) }</lang>

Output:

EKG( 2): 1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11,33,27,30,25,35,28,26,13,39,36
EKG( 5): 1,5,10,2,4,6,3,9,12,8,14,7,21,15,18,16,20,22,11,33,24,26,13,39,27,30,25,35,28,32
EKG( 7): 1,7,14,2,4,6,3,9,12,8,10,5,15,18,16,20,22,11,33,21,24,26,13,39,27,30,25,35,28,32
EKG( 9): 1,9,3,6,2,4,8,10,5,15,12,14,7,21,18,16,20,22,11,33,24,26,13,39,27,30,25,35,28,32
EKG(10): 1,10,2,4,6,3,9,12,8,14,7,21,15,5,20,16,18,22,11,33,24,26,13,39,27,30,25,35,28,32

<lang zkl>ekg5,ekg7, ekg5W,ekg7W := List(),List(), ekgW(5),ekgW(7); ekg5W.next(); ekg7W.next(); // pop initial 1 foreach e5,e7 in (ekg5W.zip(ekg7W)){

  ekg5.merge(e5); ekg7.merge(e7);	// keep terms sorted
  if(e5==e7 and ekg5==ekg7){ 	// a(n) are ==, both sequences have same terms
     println("EKG(5) and EKG(7) converge at term ",ekg7.len() + 1);
     break;
  }
  // should put limiter here

}</lang>

Output:

EKG(5) and EKG(7) converge at term 21