EKG sequence convergence: Difference between revisions
Added FreeBASIC
No edit summary |
(Added FreeBASIC) |
||
| (8 intermediate revisions by 7 users not shown) | |||
Line 30:
# [[Greatest common divisor]]
# [[Sieve of Eratosthenes]]
# [[Yellowstone sequence]]
<br>
;Reference:
Line 38 ⟶ 39:
{{trans|Nim}}
<
Set[Int] values
assert(n >= 2)
Line 72 ⟶ 73:
convIndex = i
L.break
print(‘EKG(5) and EKG(7) converge at index ’convIndex‘.’)</
{{out}}
Line 86 ⟶ 87:
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<
BYTE FUNC Contains(BYTE ARRAY a BYTE len,b)
Line 200 ⟶ 201:
PrintF("converge at index %B",conv)
FI
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/EKG_sequence_convergence.png Screenshot from Atari 8-bit computer]
Line 215 ⟶ 216:
=={{header|Ada}}==
{{trans|Go}}
<
with Ada.Containers.Generic_Array_Sort;
Line 330 ⟶ 331:
end if;
end;
end EKG_Sequences;</
{{out}}
<pre>
Line 344 ⟶ 345:
=={{header|C}}==
{{trans|Go}}
<
#include <stdlib.h>
Line 418 ⟶ 419:
printf("\nEKG5(5) and EKG(7) do not converge within %d terms\n", LIMIT);
return 0;
}</
{{out}}
Line 429 ⟶ 430:
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>
Line 434 ⟶ 510:
===The Function===
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<
// Generate EKG Sequences. Nigel Galloway: December 6th., 2018
let EKG n=seq{
Line 445 ⟶ 521:
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===
<
EKG 2 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
EKG 3 |> Seq.take 45 |> Seq.iter(printf "%2d, ")
Line 456 ⟶ 532:
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>
Line 465 ⟶ 541:
</pre>
===Extra Credit===
<
prıntfn "%d" (EKG 2|>Seq.takeWhile(fun n->n<>104729) ((Seq.length n)+1)
</syntaxhighlight>
{{out}}
<pre>
Line 476 ⟶ 552:
=={{header|Factor}}==
{{works with|Factor|0.99 2019-10-06}}
<
lists.lazy math math.statistics prettyprint sequences
sequences.generalizations ;
Line 498 ⟶ 574:
{ 2 5 7 9 10 } 20 show-ekgs nl
"EKG(5) and EKG(7) converge at term " write
5 7 100 converge-at .</
{{out}}
<pre>
Line 509 ⟶ 585:
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}}==
<
import (
Line 582 ⟶ 720:
}
fmt.Println("\nEKG5(5) and EKG(7) do not converge within", limit, "terms")
}</
{{out}}
Line 596 ⟶ 734:
=={{header|Haskell}}==
<
import Data.Maybe (fromJust)
Line 644 ⟶ 782:
)
)
)</
{{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]
Line 654 ⟶ 792:
=={{header|J}}==
<syntaxhighlight lang="j">
Until =: 2 :'u^:(0-:v)^:_' NB. unused but so fun
prime_factors_of_tail =: ~.@:q:@:{:
Line 691 ⟶ 829:
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
Line 706 ⟶ 844:
assert (ekg^:9&> -: ekg2^:9&>) 2 5 7 9 10
</syntaxhighlight>
=={{header|Java}}==
<
import java.util.ArrayList;
import java.util.Collections;
Line 789 ⟶ 927:
}
</syntaxhighlight>
{{out}}
<pre>
Line 812 ⟶ 950:
'''Preliminaries'''
<syntaxhighlight lang="jq">
# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
Line 821 ⟶ 959:
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);
Line 868 ⟶ 1,006:
;
task</
{{out}}
<pre>
Line 882 ⟶ 1,020:
=={{header|Julia}}==
{{trans|Perl}}
<
function ekgsequence(n, limit)
Line 910 ⟶ 1,048:
[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
Line 922 ⟶ 1,060:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun gcd(a: Int, b: Int): Int {
Line 970 ⟶ 1,108:
}
println("\nEKG5(5) and EKG(7) do not converge within $LIMIT terms")
}</
{{output}}
Line 984 ⟶ 1,122:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
NextInSequence[seq_List] := Module[{last, new = 1, holes, max, sel, found, i},
last = Last[seq];
Line 1,011 ⟶ 1,149:
len = LengthWhile[s, Apply[Equal]];
s //= Reverse[Drop[#, len]] &;
Length[s] + 1</
{{out}}
<pre>1 2 4 6 3 9 12 8 10 5
Line 1,020 ⟶ 1,158:
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}}==
<
#---------------------------------------------------------------------------------------------------
Line 1,064 ⟶ 1,260:
echo fmt"EKG(5) and EKG(7) converge at index {convIndex}."
else:
echo "No convergence found in the first {convIndex} terms."</
{{out}}
Line 1,076 ⟶ 1,272:
=={{header|Perl}}==
{{trans|Raku}}
<
sub gcd { my ($u,$v) = @_; $v ? gcd($v, $u%$v) : abs($u) }
Line 1,103 ⟶ 1,299:
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"</
{{out}}
<pre>EKG(2): 1 2 4 6 3 9 12 8 10 5
Line 1,114 ⟶ 1,310:
=={{header|Phix}}==
{{trans|C}}
<!--<
<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>
Line 1,147 ⟶ 1,343:
<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>
<!--</
{{out}}
<pre>
Line 1,163 ⟶ 1,359:
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 math import gcd
Line 1,196 ⟶ 1,392:
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))}!")</
{{out}}
Line 1,211 ⟶ 1,407:
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.
<
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:'''
Line 1,269 ⟶ 1,465:
(formerly Perl 6)
{{works with|Rakudo Star|2018.04.1}}
<syntaxhighlight lang="raku"
sub next-EKG ( *@s ) {
Line 1,292 ⟶ 1,488:
for [5, 7], [2, 5, 7, 9, 10] -> @ints {
say "EKGs of (@ints[]) converge at term {$_+1}" with converge-at(@ints);
}</
{{out}}
<pre>
Line 1,305 ⟶ 1,501:
=={{header|REXX}}==
<
parse arg nums start /*obtain optional arguments from the CL*/
if nums=='' | nums=="," then nums= 50 /*Not specified? Then use the default.*/
Line 1,343 ⟶ 1,539:
if done then iterate
if wordpos(j, $)==0 then return j /*return an EKG integer.*/
end /*j*/</
{{out|output|text= when using the default inputs:}}
<!-- (output is shown '''<sup>5</sup>/<sub>6</sub>''' size.) !-->
Line 1,356 ⟶ 1,552:
(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}}
<
method next {
terms += callback(terms)
Line 1,406 ⟶ 1,648:
var c = converge_at(arr)
say "EKGs of #{arr} converge at term #{c}"
}</
{{out}}
<pre>
Line 1,418 ⟶ 1,660:
</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 {
Line 1,476 ⟶ 1,718:
}
println("\nEKG5(5) and EKG(7) do not converge within $limit terms")
}</
{{out}}
Line 1,494 ⟶ 1,736:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./math" for Int
import "./fmt" for Fmt
var areSame = Fn.new { |s, t|
Line 1,538 ⟶ 1,780:
}
}
System.print("\nEKG5(5) and EKG(7) do not converge within %(limit) terms.") </
{{out}}
Line 1,553 ⟶ 1,795:
=={{header|XPL0}}==
As can be seen, EKG(5) and EKG(7) converge at N = 21.
<
func Used; int M; \Return 'true' if M is in array A
Line 1,595 ⟶ 1,837:
[Tbl:= [2, 5, 7, 9, 10];
for I:= 0 to 4 do EKG(Tbl(I));
]</
{{out}}
Line 1,608 ⟶ 1,850:
=={{header|zkl}}==
Using gcd hint from Go.
<
Walker.tweak(fcn(rp,buf,w){
foreach n in (w){
Line 1,616 ⟶ 1,858:
}
}.fp(Ref(N),List(),Walker.chain([2..N-1],[N+1..]))).push(1,N)
}</
<
{{out}}
<pre>
Line 1,626 ⟶ 1,868:
EKG(10): 1,10,2,4,6,3,9,12,8,14
</pre>
<
ekgWs:=ns.apply(ekgW); ekgWs.apply2("next"); // pop initial 1
ekgNs:=List()*vm.numArgs; // ( (ekg(n1)), (ekg(n2)) ...)
Line 1,641 ⟶ 1,883:
}
convergeAt(5,7);
convergeAt(2,5,7,9,10);</
{{out}}
<pre>
| |||