Not that anyone cares, but there is an error in the code above. Here is the fixed code and table. The last value (in parentheses) indicates how many values are in sequence from that point until the next line of the table. For instance, for n=1560 the value is 4680 and continues in sequence for 1559 steps. Presumably this fact can be used to make very large jumps as n gets bigger and bigger.
Code:
#include <stdio.h>
typedef long Int;
Int gcd(Int a, Int b) {
while (b) { Int t = a % b; a = b; b = t; }
return a;
}
int main() {
Int n = 4, g = 13, start = g;
Int cnt = 1;
for (++n; n <= 5000; ++n) {
Int g_prev = g;
g = g_prev + gcd(n, g_prev);
if (g == g_prev + 1)
++cnt;
else {
printf("%4ld. %5ld (%4ld)\n",
n - cnt, start, cnt);
cnt = 1;
start = g;
}
}
}
Code:
. 4. 13 ( 2)
6. 16 ( 3)
9. 27 ( 8)
17. 51 ( 1)
18. 54 ( 2)
20. 60 ( 1)
21. 63 ( 20)
41. 123 ( 1)
42. 126 ( 41)
83. 249 ( 1)
84. 252 ( 83)
167. 501 ( 1)
168. 504 ( 2)
170. 510 ( 1)
171. 513 ( 5)
176. 528 ( 1)
177. 531 ( 176)
353. 1059 ( 1)
354. 1062 ( 3)
357. 1071 ( 11)
368. 1104 ( 1)
369. 1107 ( 5)
374. 1122 ( 1)
375. 1125 ( 3)
378. 1134 ( 2)
380. 1140 ( 1)
381. 1143 ( 380)
761. 2283 ( 1)
762. 2286 ( 761)
1523. 4569 ( 1)
1524. 4572 ( 5)
1529. 4587 ( 1)
1530. 4590 ( 3)
1533. 4599 ( 2)
1535. 4605 ( 1)
1536. 4608 ( 18)
1554. 4662 ( 6)
1560. 4680 (1559)
3119. 9357 ( 1)
3120. 9360 ( 8)
3128. 9384 ( 1)