EKG sequence convergence

From Rosetta Code
Task
EKG sequence convergence
You are encouraged to solve this task according to the task description, using any language you may know.

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 10 members of EKG(2).
  2. Calculate and show here the first 10 members of EKG(5).
  3. Calculate and show here the first 10 members of EKG(7).
  4. Calculate and show here the first 10 members of EKG(9).
  5. Calculate and show here the first 10 members of EKG(10).
  6. Calculate and show here at which term EKG(5) and EKG(7) converge   (stretch goal).
Related Tasks
  1. Greatest common divisor
  2. Sieve of Eratosthenes
  3. Yellowstone sequence


Reference



11l

Translation of: Nim
F ekg(n, limit)
   Set[Int] values
   assert(n >= 2)
   V r = [(1, 1), (2, n)]
   values.add(n)
   V i = 3
   V prev = n
   L i <= limit
      V val = 2
      L
         I val !C values & gcd(val, prev) != 1
            values.add(val)
            r [+]= (i, val)
            prev = val
            L.break
         val++
      i++
   R r

L(n) [2, 5, 7, 9, 10]
   [Int] result
   L(i, val) ekg(n, 10)
      result [+]= val
   print((‘EKG(’n‘):’).ljust(8)‘ ’result.join(‘, ’))

V ekg5 = [0] * 101
V ekg7 = [0] * 101
L(i, val) ekg(5, 100) {ekg5[i] = val}
L(i, val) ekg(7, 100) {ekg7[i] = val}
V convIndex = 0
L(i) 2..100
   I ekg5[i] == ekg7[i] & sorted(ekg5[1 .< i]) == sorted(ekg7[1 .< i])
      convIndex = i
      L.break
print(‘EKG(5) and EKG(7) converge at index ’convIndex‘.’)
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(9):  1, 9, 3, 6, 2, 4, 8, 10, 5, 15
EKG(10): 1, 10, 2, 4, 6, 3, 9, 12, 8, 14
EKG(5) and EKG(7) converge at index 21.

Action!

INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit

BYTE FUNC Contains(BYTE ARRAY a BYTE len,b)
  BYTE i

  IF len=0 THEN
    RETURN (0)
  FI
  FOR i=0 TO len-1
  DO
    IF a(i)=b THEN
      RETURN (1)
    FI
  OD
RETURN (0)

BYTE FUNC Gcd(BYTE a,b)
  BYTE tmp

  IF a<b THEN
    tmp=a a=b b=tmp
  FI

  WHILE b#0
  DO
    tmp=a MOD b
    a=b b=tmp
  OD
RETURN (a)

BYTE FUNC AreSame(BYTE ARRAY a,b BYTE len)
  BYTE i

  IF len=0 THEN
    RETURN (1)
  FI

  SortB(a,len,0)
  SortB(b,len,0)
  FOR i=0 TO len-1
  DO
    IF a(i)#b(i) THEN
      RETURN (0)
    FI
  OD
RETURN (1)

PROC CalcEkg(BYTE start,limit BYTE ARRAY ekg)
  BYTE len,i

  ekg(0)=1 ekg(1)=start
  FOR len=2 TO limit-1
  DO
    i=2
    DO
      IF Contains(ekg,len,i)=0 AND Gcd(ekg(len-1),i)>1 THEN
        ekg(len)=i
        EXIT
      FI
      i==+1
    OD
  OD
RETURN

BYTE FUNC CalcConvergence(BYTE ARRAY a,b BYTE len)
  BYTE i

  FOR i=2 TO len-1
  DO
    IF a(i)=b(i) AND AreSame(a,b,i)=1 THEN
      RETURN (i+1)
    FI
  OD
RETURN (0)

PROC PrintSeq(BYTE start BYTE ARRAY ekg BYTE len)
  BYTE i

  PrintF("EKG(%B)=",start)
  FOR i=0 TO len-1
  DO
    IF i>0 THEN Put(32) FI
    PrintB(ekg(i))
  OD
  PrintE("...")
RETURN

PROC Main()
  DEFINE PTR="CARD"
  DEFINE LIMIT="100"
  DEFINE SEQCOUNT="5"
  DEFINE PART="10"
  DEFINE EKG1="1"
  DEFINE EKG2="2"
  BYTE ARRAY buf(500),starts=[2 5 7 9 10]
  PTR ARRAY ekg(SEQCOUNT)
  BYTE i,conv

  Put(125) PutE() ;clear the screen

  FOR i=0 TO SEQCOUNT-1
  DO
    ekg(i)=buf+LIMIT*i
    CalcEkg(starts(i),LIMIT,ekg(i))
    PrintSeq(starts(i),ekg(i),PART)
  OD

  conv=CalcConvergence(ekg(EKG1),ekg(EKG2),LIMIT)
  PrintF("%EEKG(%B) and EKG(%B) ",starts(EKG1),starts(EKG2))
  IF conv=0 THEN
    PrintF("do not converge within %B items",LIMIT)
  ELSE
    PrintF("converge at index %B",conv)
  FI
RETURN
Output:

Screenshot from Atari 8-bit computer

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(9)=1 9 3 6 2 4 8 10 5 15...
EKG(10)=1 10 2 4 6 3 9 12 8 14...

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

Ada

Translation of: Go
with Ada.Text_IO;
with Ada.Containers.Generic_Array_Sort;

procedure EKG_Sequences is

   type Element_Type is new Integer;

   type    Index_Type is new Integer range 1 .. 100;
   subtype Show_Range is Index_Type  range 1 .. 30;

   type Sequence is array (Index_Type range <>) of Element_Type;
   subtype EKG_Sequence is Sequence (Index_Type);

   function GCD (Left, Right : Element_Type) return Integer is
      A : Element_Type := Left;
      B : Element_Type := Right;
   begin
      while A /= B loop
         if A > B
         then A := A - B;
         else B := B - A;
         end if;
      end loop;
      return Integer (A);
   end GCD;

   function Contains (A    : Sequence;
                      B    : Element_Type;
                      Last : Index_Type) return Boolean
   is (for some Value of A (A'First .. Last) =>  Value = B);

   function Are_Same (S, T : EKG_Sequence; Last : Index_Type) return Boolean is
      S_Copy : Sequence := S (S'First .. Last);
      T_Copy : Sequence := T (T'First .. Last);
      procedure Sort is
        new Ada.Containers.Generic_Array_Sort (Index_Type   => Index_Type,
                                               Element_Type => Element_Type,
                                               Array_Type   => Sequence);
   begin
      Sort (S_Copy);
      Sort (T_Copy);
      return S_Copy = T_Copy;
   end Are_Same;

   function Create_EKG (Start : Element_Type) return EKG_Sequence is
      EKG : EKG_Sequence := (1 => 1, 2 => Start, others => 0);
   begin
      for N in 3 .. Index_Type'Last loop
         for I in 2 .. Element_Type'Last loop
            --  A potential sequence member cannot already have been used
            --  and must have a factor in common with previous member
            if not Contains (EKG, I, N)
              and then GCD (EKG (N - 1), I) > 1
            then
               EKG (N) := I;
               exit;
            end if;
         end loop;
      end loop;
      return EKG;
   end Create_EKG;

   procedure Converge (Seq_A, Seq_B : Sequence;
                       Term         : out Index_Type;
                       Do_Converge  : out Boolean) is
   begin
      for I in 3 .. Index_Type'Last loop
         if Seq_A (I) = Seq_B (I) and then Are_Same (Seq_A, Seq_B, I) then
            Do_Converge := True;
            Term        := I;
            return;
         end if;
      end loop;
      Do_Converge := False;
      Term        := Index_Type'Last;
   end Converge;

   procedure Put (Seq : Sequence) is
      use Ada.Text_IO;
   begin
      Put ("[");
      for E of Seq (Show_Range) loop
         Put (E'Image);
      end loop;
      Put ("]");
   end Put;

   use Ada.Text_IO;
   EKG_2  : constant EKG_Sequence := Create_EKG (2);
   EKG_5  : constant EKG_Sequence := Create_EKG (5);
   EKG_7  : constant EKG_Sequence := Create_EKG (7);
   EKG_9  : constant EKG_Sequence := Create_EKG (9);
   EKG_10 : constant EKG_Sequence := Create_EKG (10);
begin
   Put ("EKG( 2): ");  Put (EKG_2);  New_Line;
   Put ("EKG( 5): ");  Put (EKG_5);  New_Line;
   Put ("EKG( 7): ");  Put (EKG_7);  New_Line;
   Put ("EKG( 9): ");  Put (EKG_9);  New_Line;
   Put ("EKG(10): ");  Put (EKG_10); New_Line;

   --  Now compare EKG5 and EKG7 for convergence
   declare
      Term        : Index_Type;
      Do_Converge : Boolean;
   begin
      Converge (EKG_5, EKG_7, Term, Do_Converge);
      New_Line;
      if Do_Converge then
         Put_Line ("EKG(5) and EKG(7) converge at term "
                     & Term'Image);
      else
         Put_Line ("EKG5(5) and EKG(7) do not converge within "
                     & Term'Image & " terms");
      end if;
   end;
end EKG_Sequences;
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

C

Translation of: Go
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#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;
}
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

C++

#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

void print_vector(const std::vector<int32_t>& list) {
	std::cout << "[";
	for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
		std::cout << list[i] << ", ";
	}
	std::cout << list.back() << "]" << std::endl;
}

bool contains(const std::vector<int32_t>& list, const int32_t& n) {
	return std::find(list.begin(), list.end(), n) != list.end();
}

bool same_sequence(const std::vector<int32_t>& seq1, const std::vector<int32_t>& seq2, const int32_t& n) {
	for ( uint64_t i = n ; i < seq1.size() ; ++i ) {
		if ( seq1[i] != seq2[i] ) {
			return false;
		}
	}
	return true;
}

std::vector<int32_t> ekg(const int32_t& second_term, const uint64_t& term_count) {
	std::vector<int32_t> result = { 1, second_term };
	int32_t candidate = 2;
	while ( result.size() < term_count ) {
		if ( ! contains(result, candidate) && std::gcd(result.back(), candidate) > 1 ) {
			result.push_back(candidate);
			candidate = 2;
		} else {
			candidate++;
		}
	}
	return result;
}

int main() {
	std::cout << "The first 10 members of EKG[2], EKG[5], EKG[7], EKG[9] and EKG[10] are:" << std::endl;
	for ( int32_t i : { 2, 5, 7, 9, 10 } ) {
		std::cout << "EKG[" << std::setw(2) << i << "] = "; print_vector(ekg(i, 10));
	}
	std::cout << std::endl;

	std::vector<int32_t> ekg5 = ekg(5, 100);
	std::vector<int32_t> ekg7 = ekg(7, 100);
	int32_t i = 1;
	while ( ! ( ekg5[i] == ekg7[i] && same_sequence(ekg5, ekg7, i) ) ) {
		i++;
	}
	// Converting from 0-based to 1-based index
	std::cout << "EKG[5] and EKG[7] converge at index " << i + 1
			  << " with a common value of " << ekg5[i] << "." << std::endl;
}
Output:
The first 10 members of EKG[2], EKG[5], EKG[7], EKG[9] and EKG[10] are:
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[ 9] = [1, 9, 3, 6, 2, 4, 8, 10, 5, 15]
EKG[10] = [1, 10, 2, 4, 6, 3, 9, 12, 8, 14]

EKG[5] and EKG[7] converge at index 21 with a common value of 24.

F#

The Function

This task uses Extensible Prime Generator (F#)

// Generate EKG Sequences. Nigel Galloway: December 6th., 2018
let EKG            n=seq{
  let fN,fG=let    i=System.Collections.Generic.Dictionary<int,int>()
            let fN g=(if not (i.ContainsKey g) then i.[g]<-g);(g,i.[g]) 
            ((fun  e->i.[e]<-i.[e]+e), (fun  l->l|>List.map fN))
  let fU           l= pCache|>Seq.takeWhile(fun n->n<=l)|>Seq.filter(fun n->l%n=0)|>List.ofSeq
  let rec EKG l (α,β)=seq{let b=fU β in if (β=n||β<snd((fG b|>List.maxBy snd))) then fN α;        yield! EKG l (fG l|>List.minBy snd)
                                                                                else fN α;yield β;yield! EKG b (fG b|>List.minBy snd)}
  yield! seq[1;n]; let g=fU n in yield! EKG g (fG g|>Seq.minBy snd)}
let EKGconv n g=Seq.zip(EKG n)(EKG g)|>Seq.skip 2|>Seq.scan(fun(n,i,g,e)(l,β)->(Set.add l n,Set.add β i,l,β))(set[1;n],set[1;g],0,0)|>Seq.takeWhile(fun(n,i,g,e)->g<>e||n<>i)

The Task

EKG 2 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 3 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 5 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 7 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 9 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 10 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
printfn "%d" (let n,_,_,_=EKGconv 2 5|>Seq.last in ((Set.count n)+1)
Output:
 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,32,34,17,51,42,38,19,57,45,40,44,46,23,69,48
 1, 3, 6, 2, 4, 8,10, 5,15, 9,12,14, 7,21,18,16,20,22,11,33,24,26,13,39,27,30,25,35,28,32,34,17,51,36,38,19,57,42,40,44,46,23,69,45,48
 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,34,17,51,36,38,19,57,42,40,44,46,23,69,45,48
45

Extra Credit

prıntfn "%d" (EKG 2|>Seq.takeWhile(fun n->n<>104729) ((Seq.length n)+1)
Output:
203786
Real: 00:10:21.967, CPU: 00:10:25.300, GC gen0: 65296, gen1: 1

Factor

Works with: Factor version 0.99 2019-10-06
USING: combinators.short-circuit formatting fry io kernel lists
lists.lazy math math.statistics prettyprint sequences
sequences.generalizations ;

: ekg? ( n seq -- ? )
    { [ member? not ] [ last gcd nip 1 > ] } 2&& ;

: (ekg) ( seq -- seq' )
    2 lfrom over [ ekg? ] curry lfilter car suffix! ;

: ekg ( n limit -- seq )
    [ 1 ] [ V{ } 2sequence ] [ 2 - [ (ekg) ] times ] tri* ;

: show-ekgs ( seq n -- )
    '[ dup _ ekg "EKG(%d) = %[%d, %]\n" printf ] each ;

: converge-at ( n m max -- o )
    tuck [ ekg [ cum-sum ] [ rest-slice ] bi ] 2bi@
    [ swapd [ = ] 2bi@ and ] 4 nfind 4drop dup [ 2 + ] when ;

{ 2 5 7 9 10 } 20 show-ekgs nl
"EKG(5) and EKG(7) converge at term " write
5 7 100 converge-at .
Output:
EKG(2) = { 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 }
EKG(5) = { 1, 5, 10, 2, 4, 6, 3, 9, 12, 8, 14, 7, 21, 15, 18, 16, 20, 22, 11, 33 }
EKG(7) = { 1, 7, 14, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 16, 20, 22, 11, 33, 21 }
EKG(9) = { 1, 9, 3, 6, 2, 4, 8, 10, 5, 15, 12, 14, 7, 21, 18, 16, 20, 22, 11, 33 }
EKG(10) = { 1, 10, 2, 4, 6, 3, 9, 12, 8, 14, 7, 21, 15, 5, 20, 16, 18, 22, 11, 33 }

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

FreeBASIC

Translation of: XPL0

As can be seen, EKG(5) And EKG(7) converge at n = 21.

Const limite = 30
Dim Shared As Integer n, A(limite + 1)

Function Used(m As Integer) As Boolean      'Return 'True' if m is in array A
    For i As Integer = 1 To n - 1
        If m = A(i) Then Return True
    Next i
    Return False
End Function

Function MinFactor(num As Integer) As Integer   'Return minimum unused factor
    Dim As Integer factor, valor, min
    
    factor = 2
    min = &H7FFFFFFF
    Do
        If num Mod factor = 0 Then     'found a factor
            valor = factor
            Do
                If Used(valor) Then
                    valor+ = factor
                Else
                    If valor < min Then min = valor
                    Exit Do
                End If
            Loop
            num \= factor
        Else
            factor += 1
        End If
    Loop Until factor > num
    Return min
End Function

Sub EKG(m As Integer)               'Calculate and show EKG sequence
    A(1) = 1: A(2) = m
    For n = 3 To limite
        A(n) = MinFactor(A(n - 1))
    Next n
    Print Using "EKG(##):"; m;
    For i As Integer = 1 To limite
        Print Using "###"; A(i);
    Next i
    Print
End Sub

Dim starts(4) As Integer = {2, 5, 7, 9, 10}
For i As Integer = 0 To 4
    EKG(starts(i))
Next i

Sleep
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

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")
}
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

Haskell

import Data.List (findIndex, isPrefixOf, tails)
import Data.Maybe (fromJust)

----------------------- EKG SEQUENCE ---------------------

seqEKGRec :: Int -> Int -> [Int] -> [Int]
seqEKGRec _ 0 l = l
seqEKGRec k n [] = seqEKGRec k (n - 2) [k, 1]
seqEKGRec k n l@(h : t) =
  seqEKGRec
    k
    (pred n)
    ( head
        ( filter
            (((&&) . flip notElem l) <*> ((1 <) . gcd h))
            [2 ..]
        ) :
      l
    )

seqEKG :: Int -> Int -> [Int]
seqEKG k n = reverse (seqEKGRec k n [])


--------------------- CONVERGENCE TEST -------------------
main :: IO ()
main =
  mapM_
    ( \x ->
        putStr "EKG ("
          >> (putStr . show $ x)
          >> putStr ") is "
          >> print (seqEKG x 20)
    )
    [2, 5, 7, 9, 10]
    >> putStr "EKG(5) and EKG(7) converge at "
    >> print
      ( succ $
          fromJust $
            findIndex
              (isPrefixOf (replicate 20 True))
              ( tails
                  ( zipWith
                      (==)
                      (seqEKG 7 80)
                      (seqEKG 5 80)
                  )
              )
      )
Output:
EKG (2) is [1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11]
EKG (5) is [1,5,10,2,4,6,3,9,12,8,14,7,21,15,18,16,20,22,11,33]
EKG (7) is [1,7,14,2,4,6,3,9,12,8,10,5,15,18,16,20,22,11,33,21]
EKG (9) is [1,9,3,6,2,4,8,10,5,15,12,14,7,21,18,16,20,22,11,33]
EKG (10) is [1,10,2,4,6,3,9,12,8,14,7,21,15,5,20,16,18,22,11,33]
EKG(5) and EKG(7) converge at 21

J

Until =: 2 :'u^:(0-:v)^:_'  NB. unused but so fun
prime_factors_of_tail =: ~.@:q:@:{:
numbers_not_in_list =: -.~ >:@:i.@:(>./)


ekg =: 3 :0                             NB. return next sequence
 if. 1 = # y do. NB. initialize
  1 , y
  return.
 end.
 a =. prime_factors_of_tail y
 b =. numbers_not_in_list y
 index_of_lowest =. {. _ ,~ I. 1 e."1 a e."1 q:b
 if. index_of_lowest < _ do. NB. if the list doesn't need extension
  y , index_of_lowest { b
  return.
 end.
 NB. otherwise extend the list
 b =. >: >./ y
 while. 1 -.@:e. a e. q: b do.
  b =. >: b
 end.
 y , b
)

   ekg^:9&>2 5 7 9 10
1  2  4 6 3 9 12  8 10  5
1  5 10 2 4 6  3  9 12  8
1  7 14 2 4 6  3  9 12  8
1  9  3 6 2 4  8 10  5 15
1 10  2 4 6 3  9 12  8 14


assert 9 -: >:Until(>&8) 2
assert (,2) -: prime_factors_of_tail 6 8  NB. (nub of)
assert 3 4 5 -: numbers_not_in_list 1 2      6

Somewhat shorter is ekg2,

index_of_lowest =: [: {. _ ,~ [: I. 1 e."1 prime_factors_of_tail e."1 q:@:numbers_not_in_list

g =: 3 :0                             NB. return sequence with next term appended
 a =. prime_factors_of_tail y
 (, (index_of_lowest { numbers_not_in_list)`(([: >:Until(1 e. a e. q:) [: >: >./))@.(_ = index_of_lowest)) y
)

ekg2 =: (1&,)`g@.(1<#)

assert (3 -: index_of_lowest { numbers_not_in_list)1 2 4 6

assert (ekg^:9&> -: ekg2^:9&>) 2 5 7 9 10

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class EKGSequenceConvergence {

    public static void main(String[] args) {
        System.out.println("Calculate and show here the first 10 members of EKG[2], EKG[5], EKG[7], EKG[9] and EKG[10].");
        for ( int i : new int[] {2, 5, 7, 9, 10} ) {
            System.out.printf("EKG[%d] = %s%n", i, ekg(i, 10));
        }
        System.out.println("Calculate and show here at which term EKG[5] and EKG[7] converge.");
        List<Integer> ekg5 = ekg(5, 100);
        List<Integer> ekg7 = ekg(7, 100);
        for ( int i = 1 ; i < ekg5.size() ; i++ ) {
            if ( ekg5.get(i) == ekg7.get(i) && sameSeq(ekg5, ekg7, i)) {
                System.out.printf("EKG[%d](%d) = EKG[%d](%d) = %d, and are identical from this term on%n", 5, i+1, 7, i+1, ekg5.get(i));
                break;
            }
        }
    }
    
    //  Same last element, and all elements in sequence are identical
    private static boolean sameSeq(List<Integer> seq1, List<Integer> seq2, int n) {
        List<Integer> list1 = new ArrayList<>(seq1.subList(0, n));
        Collections.sort(list1);
        List<Integer> list2 = new ArrayList<>(seq2.subList(0, n));
        Collections.sort(list2);
        for ( int i = 0 ; i < n ; i++ ) {
            if ( list1.get(i) != list2.get(i) ) {
                return false;
            }
        }
        return true;
    }
    
    //  Without HashMap to identify seen terms, need to examine list.
    //    Calculating 3000 terms in this manner takes 10 seconds
    //  With HashMap to identify the seen terms, calculating 3000 terms takes .1 sec.
    private static List<Integer> ekg(int two, int maxN) {
        List<Integer> result = new ArrayList<>();
        result.add(1);
        result.add(two);
        Map<Integer,Integer> seen = new HashMap<>();
        seen.put(1, 1);
        seen.put(two, 1);
        int minUnseen = two == 2 ? 3 : 2;
        int prev = two;
        for ( int n = 3 ; n <= maxN ; n++ ) {
            int test = minUnseen - 1;
            while ( true ) {
                test++;
                if ( ! seen.containsKey(test) && gcd(test, prev) > 1 ) {
                    
                    result.add(test);
                    seen.put(test, n);
                    prev = test;
                    if ( minUnseen == test ) {
                        do {
                            minUnseen++;
                        } while ( seen.containsKey(minUnseen) );
                    }
                    break;
                }
            }
        }
        return result;
    }

    private static final int gcd(int a, int b) {
        if ( b == 0 ) {
            return a;
        }
        return gcd(b, a%b);
    }
        
}
Output:
Calculate and show here the first 10 members of EKG[2], EKG[5], EKG[7], EKG[9] and EKG[10].
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[9] = [1, 9, 3, 6, 2, 4, 8, 10, 5, 15]
EKG[10] = [1, 10, 2, 4, 6, 3, 9, 12, 8, 14]
Calculate and show here at which term EKG[5] and EKG[7] converge.
EKG[5](21) = EKG[7](21) = 24, and are identical from this term on

jq

Adapted from Wren

Works with: jq

Works with gojq, the Go implementation of jq

A very small point of interest is that the appropriate width for printing the results neatly is determined dynamically based on the entire set of sequences.

Preliminaries

# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
  def _gcd:
    if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
  [a,b] | _gcd ;

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

The Task

def areSame($s; $t):
  ($s|length) == ($t|length) and ($s|sort) == ($t|sort);

def task:

  # compare EKG5 and EKG7 for convergence, assuming . has been constructed appropriately:
  def compare:
    first( range(2; .limit) as $i
           | select(.ekg[1][$i] == .ekg[2][$i] and areSame(.ekg[1][0:$i]; .ekg[2][0:$i]))
           | "\nEKG(5) and EKG(7) converge at term \($i+1)." ) 
    // "\nEKG5(5) and EKG(7) do not converge within \(.limit) terms." ;

  { limit: 100,
    starts: [2, 5, 7, 9, 10],
    ekg: [],
    width: 0  # keep track of the number of characters required to print the results neatly
    }
  | reduce range(0;4) as $i (.; .ekg[$i] = [range(0; .limit) | 0] )
  | reduce range(0; .starts|length ) as $s (.;
      .starts[$s] as $start
      | .ekg[$s][0] = 1
      | .ekg[$s][1] = $start
      | reduce range( 2; .limit) as $n (.;
          .i = 2
	  | .stop = false
          | until( .stop;
              # a potential sequence member cannot already have been used
              # and must have a factor in common with previous member
	      .ekg[$s] as $ekg
              | if (.i | IN( $ekg[0:$n][]) | not) and gcd($ekg[$n-1]; .i) > 1
                then .ekg[$s][$n] = .i
		| .width = ([.width, (.i|tostring|length)] | max)
		| .stop = true
                else .
	        end
              | .i += 1) ) )

  # Read out the results of interest:
  | (range(0; .starts|length ) as $s
     | .width as $width
     | "EKG(\(.starts[$s]|lpad(2))): \(.ekg[$s][0:30]|map(lpad($width))|join(" "))" ),
     compare
    ;

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

Julia

Translation of: Perl
using Primes

function ekgsequence(n, limit)
    ekg::Array{Int,1} = [1, n]
    while length(ekg) < limit
        for i in 2:2<<18
            if all(j -> j != i, ekg) && gcd(ekg[end], i) > 1
                push!(ekg, i)
                break
            end
        end
    end
    ekg
end

function convergeat(n, m, max = 100)
    ekgn = ekgsequence(n, max)
    ekgm = ekgsequence(m, max)
    for i in 3:max
        if ekgn[i] == ekgm[i] && sum(ekgn[1:i+1]) == sum(ekgm[1:i+1])
            return i
        end
    end
    warn("no converge in $max terms")
end

[println(rpad("EKG($i): ", 9), join(ekgsequence(i, 30), " ")) for i in [2, 5, 7, 9, 10]]
println("EKGs of 5 & 7 converge at term ", convergeat(5, 7))
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 EKGs of 5 & 7 converge at term 21

Kotlin

Translation of: Go
// 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")
}
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

Mathematica/Wolfram Language

ClearAll[NextInSequence, EKGSequence]
NextInSequence[seq_List] := Module[{last, new = 1, holes, max, sel, found, i},
  last = Last[seq];
  max = Max[seq];
  holes = Complement[Range[max], seq];
  sel = SelectFirst[holes, Not[CoprimeQ[last, #]] &];
  If[MissingQ[sel],
   i = max;
   found = False; 
   While[! found,
    i++;
    If[Not[CoprimeQ[last, i]],
     found = True
     ]
    ];
   Append[seq, i]
   ,
   Append[seq, sel]
  ]
 ]
EKGSequence[start_Integer, n_] := Nest[NextInSequence, {1, start}, n - 2]

Table[EKGSequence[s, 10], {s, {2, 5, 7, 9, 10}}] // Grid

s = Reverse[Transpose[{EKGSequence[5, 1000], EKGSequence[7, 1000]}]];
len = LengthWhile[s, Apply[Equal]];
s //= Reverse[Drop[#, len]] &;
Length[s] + 1
Output:
1	2	4	6	3	9	12	8	10	5
1	5	10	2	4	6	3	9	12	8
1	7	14	2	4	6	3	9	12	8
1	9	3	6	2	4	8	10	5	15
1	10	2	4	6	3	9	12	8	14

21

MATLAB

Translation of: Julia
% Displaying EKG sequences and the convergence point
for i = [2, 5, 7, 9, 10]
    ekg = ekgsequence(i, 30);
    fprintf('EKG(%d): %s\n', i, num2str(ekg));
end

convergencePoint = convergeat(5, 7);
fprintf('EKGs of 5 & 7 converge at term %d\n', convergencePoint);



function ekg = ekgsequence(n, limit)
    ekg = [1, n];
    while length(ekg) < limit
        for i = 2:2^18
            if all(ekg ~= i) && gcd(ekg(end), i) > 1
                ekg = [ekg, i];
                break;
            end
        end
    end
end

function point = convergeat(n, m, max)
    if nargin < 3
        max = 100;
    end

    ekgn = ekgsequence(n, max);
    ekgm = ekgsequence(m, max);
    
    point = 0;
    for i = 3:max
        if ekgn(i) == ekgm(i) && sum(ekgn(1:i+1)) == sum(ekgm(1:i+1))
            point = i;
            return;
        end
    end
    
    if point == 0
        warning('No convergence in %d terms', max);
    end
end
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
EKGs of 5 & 7 converge at term 21


Nim

import algorithm, math, sets, strformat, strutils

#---------------------------------------------------------------------------------------------------

iterator ekg(n, limit: Positive): (int, int) =
  var values: HashSet[int]
  doAssert n >= 2
  yield (1, 1)
  yield (2, n)
  values.incl(n)
  var i = 3
  var prev = n
  while i <= limit:
    var val = 2
    while true:
      if val notin values and gcd(val, prev) != 1:
        values.incl(val)
        yield (i, val)
        prev = val
        break
      inc val
    inc i

#---------------------------------------------------------------------------------------------------

for n in [2, 5, 7, 9, 10]:
  var result: array[1..10, int]
  for i, val in ekg(n, 10): result[i] = val
  let title = fmt"EKG({n}):"
  echo fmt"{title:8} {result.join("", "")}"

var ekg5, ekg7: array[1..100, int]
for i, val in ekg(5, 100): ekg5[i] = val
for i, val in ekg(7, 100): ekg7[i] = val
var convIndex = 0
for i in 2..100:
  if ekg5[i] == ekg7[i] and sorted(ekg5[1..<i]) == sorted(ekg7[1..<i]):
    convIndex = i
    break
if convIndex > 0:
  echo fmt"EKG(5) and EKG(7) converge at index {convIndex}."
else:
  echo "No convergence found in the first {convIndex} terms."
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(9):  1, 9, 3, 6, 2, 4, 8, 10, 5, 15
EKG(10): 1, 10, 2, 4, 6, 3, 9, 12, 8, 14
EKG(5) and EKG(7) converge at index 21.

Perl

Translation of: Raku
use List::Util qw(none sum);

sub gcd { my ($u,$v) = @_; $v ? gcd($v, $u%$v) : abs($u) }
sub shares_divisors_with { gcd( $_[0], $_[1]) > 1 }

sub EKG {
    my($n,$limit) = @_;
    my @ekg = (1, $n);
    while (@ekg < $limit) {
        for my $i (2..1e18) {
            next unless none { $_ == $i } @ekg and shares_divisors_with($ekg[-1], $i);
            push(@ekg, $i) and last;
        }
    }
    @ekg;
}

sub converge_at {
    my($n1,$n2) = @_;
    my $max = 100;
    my @ekg1 = EKG($n1,$max);
    my @ekg2 = EKG($n2,$max);
    do { return $_+1 if $ekg1[$_] == $ekg2[$_] && sum(@ekg1[0..$_]) == sum(@ekg2[0..$_])} for 2..$max;
    return "(no convergence in $max terms)";
}

print "EKG($_): " . join(' ', EKG($_,10)) . "\n" for 2, 5, 7, 9, 10;
print "EKGs of 5 & 7 converge at term " . converge_at(5, 7) . "\n"
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(9): 1 9 3 6 2 4 8 10 5 15
EKG(10): 1 10 2 4 6 3 9 12 8 14
EKGs of 5 & 7 converge at term 21

Phix

Translation of: C
with javascript_semantics
constant LIMIT = 100
constant starts = {2, 5, 7, 9, 10}
sequence ekg = {}
string fmt = "EKG(%2d): ["&join(repeat("%d",min(LIMIT,30))," ")&"]\n"
for s=1 to length(starts) do
    ekg = append(ekg,{1,starts[s]}&repeat(0,LIMIT-2))
    for n=3 to LIMIT do
        -- a potential sequence member cannot already have been used
        -- and must have a factor in common with previous member
        integer i = 2
        while find(i,ekg[s])
           or gcd(ekg[s][n-1],i)<=1 do
            i += 1
        end while
        ekg[s][n] = i
    end for
    printf(1,fmt,starts[s]&ekg[s][1..min(LIMIT,30)])
end for
 
-- now compare EKG5 and EKG7 for convergence
constant EKG5 = find(5,starts),
         EKG7 = find(7,starts)
string msg = sprintf("do not converge within %d terms", LIMIT)
for i=3 to LIMIT do
    if ekg[EKG5][i]=ekg[EKG7][i]
    and sort(ekg[EKG5][1..i-1])=sort(ekg[EKG7][1..i-1]) then
        msg = sprintf("converge at term %d", i)
        exit
    end if
end for
printf(1,"\nEKG5(5) and EKG(7) %s\n", msg)
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]

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

Python

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.

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, 9, 10:
        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))}!")
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(9): 1, 9, 3, 6, 2, 4, 8, 10, 5, 15
EKG(10): 1, 10, 2, 4, 6, 3, 9, 12, 8, 14

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.

# 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)]))

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])]

Raku

(formerly Perl 6)

Works with: Rakudo Star version 2018.04.1
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 … *  }

sub converge-at ( @ints ) {
    my @ekgs = @ints.map: &EKG;

    return (2 .. *).first: -> $i {
        [==]  @ekgs.map(     *.[$i]     ) and
        [===] @ekgs.map( *.head($i).Set )
    }
}

say "EKG($_): ", .&EKG.head(10) for 2, 5, 7, 9, 10;

for [5, 7], [2, 5, 7, 9, 10] -> @ints {
    say "EKGs of (@ints[]) converge at term {$_+1}" with converge-at(@ints);
}
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(9): (1 9 3 6 2 4 8 10 5 15)
EKG(10): (1 10 2 4 6 3 9 12 8 14)
EKGs of (5 7) converge at term 21
EKGs of (2 5 7 9 10) converge at term 45

REXX

/*REXX program can  generate and display several  EKG  sequences  (with various starts).*/
parse arg nums start                             /*obtain optional arguments from the CL*/
if  nums=='' |  nums==","  then  nums= 50        /*Not specified?  Then use the default.*/
if start= '' | start= ","  then start=2 5 7 9 10 /* "      "         "   "   "     "    */

     do s=1  for words(start);   $=              /*step through the specified  STARTs.  */
     second= word(start, s);     say             /*obtain the second integer in the seq.*/

         do j=1  for nums
         if j<3  then do; #=1;  if j==2  then #=second;  end   /*handle 1st & 2nd number*/
                 else #= ekg(#)
         $= $ right(#,  max(2, length(#) ) )     /*append the EKG integer to the $ list.*/
         end   /*j*/                             /* [↑] the RIGHT BIF aligns the numbers*/
     say '(start'  right(second,  max(2, length(second) ) )"):"$      /*display EKG seq.*/
     end       /*s*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
add_:   do  while z//j == 0;    z=z%j;    _=_ j;    w=w+1;    end;         return strip(_)
/*──────────────────────────────────────────────────────────────────────────────────────*/
ekg: procedure expose $; parse arg x 1 z,,_
     w=0                                                        /*W:  number of factors.*/
             do k=1  to 11  by 2;     j=k;  if j==1  then j=2   /*divide by low primes. */
             if j==9  then iterate;   call add_                 /*skip ÷ 9; add to list.*/
             end   /*k*/
                                                                /*↓ skips multiples of 3*/
             do y=0  by 2;  j= j + 2 + y//4                     /*increment J by 2 or 4.*/
             parse var  j  ''  -1  r;  if r==5  then iterate    /*divisible by five ?   */
             if j*j>x | j>z  then leave                         /*passed the sqrt(x) ?  */
             _= add_()                                          /*add a factor to list. */
             end   /*y*/
     j=z;                    if z\==1  then _= add_()           /*Z¬=1? Then add──►list.*/
     if _=''  then _=x                                          /*Null? Then use prime. */
                 do   j=3;                          done=1
                   do k=1  for w
                   if j // word(_, k)==0  then do;  done=0;  leave;  end
                   end   /*k*/
                 if done  then iterate
                 if wordpos(j, $)==0  then return j             /*return an EKG integer.*/
                 end     /*j*/
output   when using the default inputs:
(start  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 32 34 17 51 42 38 19 57 45 40 44 46 23 69 48 50 52 54 56 49

(start  5):  1  5 10  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 34 17 51 36 38 19 57 42 40 44 46 23 69 45 48 50 52 54 56 49 63

(start  7):  1  7 14  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 34 17 51 36 38 19 57 42 40 44 46 23 69 45 48 50 52 54 56 49 63

(start  9):  1  9  3  6  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 34 17 51 36 38 19 57 42 40 44 46 23 69 45 48 50 52 54 56 49 63

(start 10):  1 10  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 34 17 51 36 38 19 57 42 40 44 46 23 69 45 48 50 52 54 56 49 63

Rust

Translation of: Perl
use gcd::Gcd;

fn ekg_sequence(n: u64, limit: usize) -> Vec<u64> {
    let mut ekg = [1_u64, n].to_vec();
    while ekg.len() < limit {
        for i in 2..2<<18 {
            if ekg.iter().all(|j| *j != i) && Gcd::gcd(ekg[ekg.len()-1], i) > 1 {
                ekg.push(i);
                break;
            }
        }
    }
    return ekg;
}


fn converge_at(n: u64, m: u64, tmax: usize) -> usize {
    let a = ekg_sequence(n, tmax);
    let b = ekg_sequence(m, tmax);
    for i in 2..tmax {
        if a[i] == b[i] && a[0..i+1].iter().sum::<u64>() == (b[0..i+1]).iter().sum::<u64>() {
            return i + 1;
        }
    }
    println!("Error: no convergence in {tmax} terms");
    return 0;
}

fn main() {
    for i in [2_u64, 5, 7, 9, 10] { 
        println!("EKG({i:2}): {:?}", ekg_sequence(i, 30_usize));
    }
    println!("EKGs of 5 & 7 converge after term {:?}", converge_at(5, 7, 50));
}
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]
EKGs of 5 & 7 converge after term 21

Sidef

Translation of: Raku
class Seq(terms, callback) {
    method next {
        terms += callback(terms)
    }

    method nth(n) {
        while (terms.len < n) {
            self.next
        }
        terms[n-1]
    }

    method first(n) {
        while (terms.len < n) {
            self.next
        }
        terms.first(n)
    }
}

func next_EKG (s) {
    2..Inf -> first {|k|
        !(s.contains(k) || s[-1].is_coprime(k))
    }
}

func EKG (start) {
    Seq([1, start], next_EKG)
}

func converge_at(ints) {
    var ekgs = ints.map(EKG)

    2..Inf -> first {|k|
        (ekgs.map { .nth(k)        }.uniq.len == 1) &&
        (ekgs.map { .first(k).sort }.uniq.len == 1)
    }
}

for k in [2, 5, 7, 9, 10] {
    say "EKG(#{k}) = #{EKG(k).first(10)}"
}

for arr in [[5,7], [2, 5, 7, 9, 10]] {
    var c = converge_at(arr)
    say "EKGs of #{arr} converge at term #{c}"
}
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(9) = [1, 9, 3, 6, 2, 4, 8, 10, 5, 15]
EKG(10) = [1, 10, 2, 4, 6, 3, 9, 12, 8, 14]
EKGs of [5, 7] converge at term 21
EKGs of [2, 5, 7, 9, 10] converge at term 45

V (Vlang)

Translation of: Go
fn gcd(aa int, bb int) int {
    mut a,mut b:=aa,bb
    for a != b {
        if a > b {
            a -= b
        } else {
            b -= a
        }
    }
    return a
}
 
fn are_same(ss []int, tt []int) bool {
    mut s,mut t:=ss.clone(),tt.clone()
    le := s.len
    if le != t.len {
        return false
    }
    s.sort()
    t.sort()
    for i in 0..le {
        if s[i] != t[i] {
            return false
        }
    }
    return true
}
const limit = 100
fn main() {
    starts := [2, 5, 7, 9, 10]
    mut ekg := [5][limit]int{}
 
    for s, start in starts {
        ekg[s][0] = 1
        ekg[s][1] = start
        for n in 2..limit {
            for i := 2; ; i++ {
                // a potential sequence member cannot already have been used
                // and must have a factor in common with previous member
                if !ekg[s][..n].contains(i) && gcd(ekg[s][n-1], i) > 1 {
                    ekg[s][n] = i
                    break
                }
            }
        }
        println("EKG(${start:2}): ${ekg[s][..30]}")
    }   
 
    // now compare EKG5 and EKG7 for convergence
    for i in 2..limit {
        if ekg[1][i] == ekg[2][i] && are_same(ekg[1][..i], ekg[2][..i]) {
            println("\nEKG(5) and EKG(7) converge at term ${i+1}")
            return
        }
    }
    println("\nEKG5(5) and EKG(7) do not converge within $limit terms")
}
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

Wren

Translation of: Go
Library: Wren-sort
Library: Wren-math
Library: Wren-fmt
import "./sort" for Sort
import "./math" for Int
import "./fmt" for Fmt

var areSame = Fn.new { |s, t|
    var le = s.count
    if (le != t.count) return false
    Sort.quick(s)
    Sort.quick(t)
    for (i in 0...le) if (s[i] != t[i]) return false
    return true
}

var limit = 100
var starts = [2, 5, 7, 9, 10]
var ekg = List.filled(5, null)
for (i in 0..4) ekg[i] = List.filled(limit, 0)
var s = 0
for (start in starts) {
    ekg[s][0] = 1
    ekg[s][1] = start
    for (n in 2...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].take(n).contains(i) && Int.gcd(ekg[s][n-1], i) > 1) {
                ekg[s][n] = i
                break
            }
            i = i + 1
        }
    }
    Fmt.print("EKG($2d): $2d", start, ekg[s].take(30).toList)
    s = s + 1
}

// now compare EKG5 and EKG7 for convergence
for (i in 2...limit) {
    if (ekg[1][i] == ekg[2][i] && areSame.call(ekg[1][0...i], ekg[2][0...i])) {
        System.print("\nEKG(5) and EKG(7) converge at term %(i+1).")
        return
    }
}
System.print("\nEKG5(5) and EKG(7) do not converge within %(limit) terms.")
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.

XPL0

As can be seen, EKG(5) and EKG(7) converge at N = 21.

int  N, A(1+30);

func Used; int M;       \Return 'true' if M is in array A
int  I;
[for I:= 1 to N-1 do
        if M = A(I) then return true;
return false;
];

func MinFactor; int Num; \Return minimum unused factor
int  Fac, Val, Min;
[Fac:= 2;
Min:= -1>>1;
repeat  if rem(Num/Fac) = 0 then \found a factor
                [Val:= Fac;
                loop    [if Used(Val) then Val:= Val+Fac
                        else    [if Val<Min then Min:= Val;
                                quit;
                                ];
                        ];
                Num:= Num/Fac;
                ]
        else    Fac:= Fac+1;
until   Fac > Num;
return Min;
];

proc EKG; int M;        \Calculate and show EKG sequence
[A(1):= 1;  A(2):= M;
for N:= 3 to 30 do
        A(N):= MinFactor(A(N-1));
Format(2, 0);
Text(0, "EKG(");  RlOut(0, float(M));  Text(0, "):");
Format(3, 0);
for N:= 1 to 30 do
        RlOut(0, float(A(N)));
CrLf(0);
];

int Tbl, I;
[Tbl:= [2, 5, 7, 9, 10];
for I:= 0 to 4 do EKG(Tbl(I));
]
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

zkl

Using gcd hint from Go.

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)
}
foreach n in (T(2,5,7,9,10)){ println("EKG(%2d): %s".fmt(n,ekgW(n).walk(10).concat(","))) }
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( 9): 1,9,3,6,2,4,8,10,5,15
EKG(10): 1,10,2,4,6,3,9,12,8,14
fcn convergeAt(n1,n2,etc){ ns:=vm.arglist;
   ekgWs:=ns.apply(ekgW); ekgWs.apply2("next");  // pop initial 1
   ekgNs:=List()*vm.numArgs;	  // ( (ekg(n1)), (ekg(n2)) ...)
   do(1_000){   // find convergence in this many terms or bail
      ekgN:=ekgWs.apply("next");  // (ekg(n1)[n],ekg(n2)[n] ...)
      ekgNs.zipWith(fcn(ns,n){ ns.merge(n) },ekgN);    // keep terms sorted
      // are all ekg[n]s == and both sequences have same terms?
      if(not ekgN.filter1('!=(ekgN[0])) and not ekgNs.filter1('!=(ekgNs[0])) ){
	 println("EKG(", ns.concat(","), ") converge at term ",ekgNs[0].len() + 1);
	 return();
      }
   }
   println(ns.concat(",")," don't converge");
}
convergeAt(5,7);
convergeAt(2,5,7,9,10);
Output:
EKG(5,7) converge at term 21
EKG(2,5,7,9,10) converge at term 45