EKG sequence convergence: Difference between revisions
m (→{{header|Python}}: added zkl header) |
(Added FreeBASIC) |
||
(84 intermediate revisions by 28 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
The sequence is from the natural numbers and is defined by: |
The sequence is from the natural numbers and is defined by: |
||
* <code>a(1) = 1</code>; |
* <code>a(1) = 1</code>; |
||
Line 12: | Line 13: | ||
* ... the sequence starting <code>1, N, ...</code> the <code>EKG(N)</code> sequence. |
* ... the sequence starting <code>1, N, ...</code> the <code>EKG(N)</code> sequence. |
||
'''Convergence'''<br> |
|||
;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.<br> |
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.<br> |
||
<code>EKG(N1)</code> and <code>EKG(N2)</code> are said to to have converged at and after generation <code>a(c)</code> if <code>state_of(EKG(N1).a(c)) == state_of(EKG(N2).a(c))</code>. |
<code>EKG(N1)</code> and <code>EKG(N2)</code> are said to to have converged at and after generation <code>a(c)</code> if <code>state_of(EKG(N1).a(c)) == state_of(EKG(N2).a(c))</code>. |
||
;Task: |
;Task: |
||
# Calculate and show here the first 10 members of <code>EKG(2)</code>. |
|||
# Calculate and show here the first 10 members of <code>EKG(5)</code>. |
|||
# Calculate and show here the first 10 members of <code>EKG(7)</code>. |
|||
# Calculate and show here the first 10 members of <code>EKG(9)</code>. |
|||
# Calculate and show here the first 10 members of <code>EKG(10)</code>. |
|||
# Calculate and show here at which term <code>EKG(5)</code> and <code>EKG(7)</code> converge ('''stretch goal'''). |
|||
;Related Tasks: |
|||
# Calculate and show here the first ten members of <code>EKG(2)</code>. |
|||
# [[Greatest common divisor]] |
|||
# Calculate and show here the first ten members of <code>EKG(5)</code>. |
|||
# [[Sieve of Eratosthenes]] |
|||
# Calculate and show here the first ten members of <code>EKG(7)</code>. |
|||
# [[Yellowstone sequence]] |
|||
# '''Stretch goal''': Calculate and show here at which term EKG(5) and EKG(7) converge. |
|||
<br> |
|||
;Reference: |
;Reference: |
||
* [https://www.youtube.com/watch?v=yd2jr30K2R4 The EKG Sequence and the Tree of Numbers]. (Video). |
* [https://www.youtube.com/watch?v=yd2jr30K2R4 The EKG Sequence and the Tree of Numbers]. (Video). |
||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="11l">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‘.’)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
{{libheader|Action! Tool Kit}} |
|||
<syntaxhighlight lang="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</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/EKG_sequence_convergence.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="ada">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;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="c">#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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="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; |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
===The Function=== |
|||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)] |
|||
<syntaxhighlight lang="fsharp"> |
|||
// 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) |
|||
</syntaxhighlight> |
|||
===The Task=== |
|||
<syntaxhighlight lang="fsharp"> |
|||
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) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
===Extra Credit=== |
|||
<syntaxhighlight lang="fsharp"> |
|||
prıntfn "%d" (EKG 2|>Seq.takeWhile(fun n->n<>104729) ((Seq.length n)+1) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
203786 |
|||
Real: 00:10:21.967, CPU: 00:10:25.300, GC gen0: 65296, gen1: 1 |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
{{works with|Factor|0.99 2019-10-06}} |
|||
<syntaxhighlight lang="factor">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 .</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
{{trans|XPL0}} |
|||
As can be seen, EKG(5) And EKG(7) converge at n = 21. |
|||
<syntaxhighlight lang="vbnet">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 71: | Line 693: | ||
func main() { |
func main() { |
||
const limit = 100 |
const limit = 100 |
||
starts := [ |
starts := [5]int{2, 5, 7, 9, 10} |
||
var ekg [ |
var ekg [5][limit]int |
||
for s, start := range starts { |
for s, start := range starts { |
||
ekg[s][0] = 1 |
ekg[s][0] = 1 |
||
ekg[s][1] = start |
ekg[s][1] = start |
||
nextMember: |
|||
for n := 2; n < limit; n++ { |
for n := 2; n < limit; n++ { |
||
for i := 2; ; i++ { |
for i := 2; ; i++ { |
||
Line 84: | Line 705: | ||
if !contains(ekg[s][:n], i) && gcd(ekg[s][n-1], i) > 1 { |
if !contains(ekg[s][:n], i) && gcd(ekg[s][n-1], i) > 1 { |
||
ekg[s][n] = i |
ekg[s][n] = i |
||
break |
|||
} |
} |
||
} |
} |
||
} |
} |
||
fmt.Printf("EKG(% |
fmt.Printf("EKG(%2d): %v\n", start, ekg[s][:30]) |
||
} |
} |
||
// now compare EKG5 and EKG7 for convergence |
// now compare EKG5 and EKG7 for convergence |
||
for i := |
for i := 2; i < limit; i++ { |
||
if ekg[1][i] == ekg[2][i] && areSame(ekg[1][:i], ekg[2][: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) |
fmt.Println("\nEKG(5) and EKG(7) converge at term", i+1) |
||
Line 99: | Line 720: | ||
} |
} |
||
fmt.Println("\nEKG5(5) and EKG(7) do not converge within", limit, "terms") |
fmt.Println("\nEKG5(5) and EKG(7) do not converge within", limit, "terms") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
EKG(2): [1 2 4 6 3 9 12 8 10 5] |
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] |
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] |
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 |
EKG(5) and EKG(7) converge at term 21 |
||
</pre> |
</pre> |
||
=={{header| |
=={{header|Haskell}}== |
||
<syntaxhighlight lang="haskell">import Data.List (findIndex, isPrefixOf, tails) |
|||
<lang python>from itertools import count, islice, takewhile |
|||
import Data.Maybe (fromJust) |
|||
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] |
|||
----------------------- EKG SEQUENCE --------------------- |
|||
def next_pfactor_gen(): |
|||
"Generate (n, set(pfactor(n))) pairs for n == 2, ..." |
|||
seqEKGRec :: Int -> Int -> [Int] -> [Int] |
|||
for n in count(2): |
|||
seqEKGRec _ 0 l = l |
|||
yield n, set(pfactor(n)) |
|||
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) |
|||
) |
|||
) |
|||
)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|J}}== |
|||
<syntaxhighlight lang="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 |
|||
</syntaxhighlight> |
|||
Somewhat shorter is ekg2, |
|||
<syntaxhighlight lang="j"> |
|||
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 |
|||
</syntaxhighlight> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="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); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|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''' |
|||
<syntaxhighlight lang="jq"> |
|||
# 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] + .; |
|||
</syntaxhighlight> |
|||
'''The Task''' |
|||
<syntaxhighlight lang="jq"> |
|||
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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{trans|Perl}} |
|||
<syntaxhighlight lang="julia">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)) |
|||
</syntaxhighlight> |
|||
{{output}}<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight 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") |
|||
}</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|MATLAB}}== |
|||
{{trans|Julia}} |
|||
<syntaxhighlight lang="MATLAB"> |
|||
% 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 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="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."</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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.</pre> |
|||
=={{header|Perl}}== |
|||
{{trans|Raku}} |
|||
<syntaxhighlight lang="perl">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"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Phix}}== |
|||
{{trans|C}} |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">LIMIT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">starts</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ekg</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"EKG(%2d): ["</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">LIMIT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">)),</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"]\n"</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">starts</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">ekg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">starts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]}&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">LIMIT</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">LIMIT</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">-- a potential sequence member cannot already have been used |
|||
-- and must have a factor in common with previous member</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">or</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)<=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">starts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">LIMIT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">)])</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000080;font-style:italic;">-- now compare EKG5 and EKG7 for convergence</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">EKG5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">starts</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">EKG7</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">starts</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">msg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"do not converge within %d terms"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">LIMIT</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">LIMIT</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">EKG5</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">EKG7</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">EKG5</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])=</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ekg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">EKG7</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">msg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"converge at term %d"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nEKG5(5) and EKG(7) %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">msg</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|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. |
|||
<syntaxhighlight lang="python">from itertools import count, islice, takewhile |
|||
from math import gcd |
|||
def EKG_gen(start=2): |
def EKG_gen(start=2): |
||
Line 144: | Line 1,366: | ||
Generate the next term of the EKG together with the minimum cache of |
Generate the next term of the EKG together with the minimum cache of |
||
numbers left in its production; (the "state" of the generator). |
numbers left in its production; (the "state" of the generator). |
||
Using math.gcd |
|||
""" |
""" |
||
c = count(start + 1) |
|||
def min_share_pf_so_far(pf, so_far): |
|||
last, so_far = start, list(range(2, start)) |
|||
"searches the unused smaller number prime factors" |
|||
yield 1, [] |
|||
yield last, [] |
|||
for index, (num, pfs) in enumerate(so_far): |
|||
while True: |
|||
for index, sf in enumerate(so_far): |
|||
if gcd(last, sf) > 1: |
|||
last = so_far.pop(index) |
|||
yield last, so_far[::] |
|||
break |
break |
||
else: |
else: |
||
so_far.append(next(c)) |
|||
return found |
|||
def find_convergence(ekgs=(5,7)): |
|||
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(pf_gen.__next__()) |
|||
yield found[0], [n for n, _ in so_far] |
|||
last, last_pf = found |
|||
#%% |
|||
def find_convergence(ekgs=(5,7), limit=1_000): |
|||
"Returns the convergence point or zero if not found within the limit" |
"Returns the convergence point or zero if not found within the limit" |
||
ekg = [EKG_gen(n) for n in ekgs] |
ekg = [EKG_gen(n) for n in ekgs] |
||
for e in ekg: |
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)))) |
|||
ldiff = len(differ) |
|||
return ldiff + 2 if ldiff < limit-1 else 0 |
|||
#%% |
|||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
for start in 2, 5, 7: |
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"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))}!")</ |
print(f"\nEKG(5) and EKG(7) converge at term {find_convergence(ekgs=(5,7))}!")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
(Same as above). |
|||
<pre>EKG(2): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5 |
<pre>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(5): 1, 5, 10, 2, 4, 6, 3, 9, 12, 8 |
||
EKG(7): 1, 7, 14, 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!</pre> |
EKG(5) and EKG(7) converge at term 21!</pre> |
||
;Note: |
|||
Despite EKG(5) and EKG(7) seeming to converge earlier, as seen above; their hidden states differ.<br> |
|||
Here is those series out to 21 terms where you can see them diverge again before finally converging. The state is also shown. |
|||
<syntaxhighlight 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)]))</syntaxhighlight> |
|||
'''Generates:''' |
|||
<pre>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])]</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo Star|2018.04.1}} |
|||
<syntaxhighlight lang="raku" line>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); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|REXX}}== |
|||
<syntaxhighlight lang="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*/</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
|||
<!-- (output is shown '''<sup>5</sup>/<sub>6</sub>''' size.) !--> |
|||
<pre style="font-size:84%"> |
|||
(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 |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
{{trans|Perl}} |
|||
<syntaxhighlight lang="rust">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)); |
|||
} |
|||
</syntaxhighlight>{{out}} |
|||
<pre style="font-size:90%"> |
|||
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 |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Raku}} |
|||
<syntaxhighlight lang="ruby">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}" |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="v (vlang)">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") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-sort}} |
|||
{{libheader|Wren-math}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">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.") </syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
As can be seen, EKG(5) and EKG(7) converge at N = 21. |
|||
<syntaxhighlight lang="xpl0">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)); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using gcd hint from Go. |
|||
<lang zkl></lang> |
|||
<syntaxhighlight lang="zkl">fcn ekgW(N){ // --> iterator |
|||
<lang zkl></lang> |
|||
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) |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">foreach n in (T(2,5,7,9,10)){ println("EKG(%2d): %s".fmt(n,ekgW(n).walk(10).concat(","))) }</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
<syntaxhighlight lang="zkl">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);</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
EKG(5,7) converge at term 21 |
|||
EKG(2,5,7,9,10) converge at term 45 |
|||
</pre> |
</pre> |
Latest revision as of 08:23, 17 March 2024
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 witha(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, ...
theEKG(2)
sequence; - the sequence starting
1, 3, ...
theEKG(3)
sequence; - ... the sequence starting
1, N, ...
theEKG(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
- Calculate and show here the first 10 members of
EKG(2)
. - Calculate and show here the first 10 members of
EKG(5)
. - Calculate and show here the first 10 members of
EKG(7)
. - Calculate and show here the first 10 members of
EKG(9)
. - Calculate and show here the first 10 members of
EKG(10)
. - Calculate and show here at which term
EKG(5)
andEKG(7)
converge (stretch goal).
- Related Tasks
- Reference
- The EKG Sequence and the Tree of Numbers. (Video).
11l
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
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
#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
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
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 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
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
// 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
% 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
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
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)
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
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
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)
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
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