EKG sequence convergence: Difference between revisions
Added C
m (→Python: Using math.gcd: Whoops.) |
(Added C) |
||
Line 25:
;Reference:
* [https://www.youtube.com/watch?v=yd2jr30K2R4 The EKG Sequence and the Tree of Numbers]. (Video).
=={{header|C}}==
{{trans|Go}}
<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[3] = {2, 5, 7};
int ekg[3][LIMIT];
for (s = 0; s < 3; ++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(%d): [", starts[s]);
for (i = 0; i < 10; ++i) printf("%d ", ekg[s][i]);
printf("\b]\n");
}
// now compare EKG5 and EKG7 for convergence
for (i = 2; i < LIMIT; ++i) {
if (ekg[1][i] == ekg[2][i] && areSame(ekg[1], ekg[2], i)) {
printf("\nEKG(5) and EKG(7) converge at term %d\n", i + 1);
return 0;
}
}
printf("\nEKG5(5) and EKG(7) do not converge within %d terms\n", LIMIT);
return 0;
}</lang>
{{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(5) and EKG(7) converge at term 21
</pre>
=={{header|Go}}==
| |||