OFFSET
1,2
COMMENTS
b(i) is the odd part of b(i-1) + b(i-2) so that b(i) is odd for i >= 2 and b(i) <= (b(i-1) + b(i-2))/2 for i >= 4 (i.e. where b(i-1) and b(i-2) both odd).
The cyclic part is always of the form b(i) = b(i+1) = b(i+2) and T(n,k) = i for the place that first happens; and the term there is b(i) = A000265(gcd(n,k)) = G.
We prove the cycle's existence by contradiction. Suppose {b(i)} never enters a repeated cycle, i.e., b(i) = b(i+1) = b(i+2) never holds. Since b(i) <= (b(i-1) + b(i-2))/2 for i >= 4, b(i) < max(b(i-1), b(i-2)). b(i+1) < max(b(i), b(i-1)) <= max(b(i-1), b(i-2). Thus max(b(i), b(i+1) < max(b(i-2), b(i-1)) for i >= 4, implying that max(b(2),b(3)) > max(b(4), b(5)) > ..., with a decreasing sequence of positive integers, which is a contradiction.
If x and y are both odd, define sequence {c(n)} where c(n) = max(b(2*n), b(2*n+1)), c(0) = max(x,y). Since 2*G | c(n) - c(n+1), the sequence can sustain (max(x,y) - G)/(2*G) terms before going down to G (then {b(n)} enters a repeated cycle), hence T(x,y) <= (max(x,y) - G)/G;
If x is even and y is odd, T(x,y) = 1 + T(y,x+y) <= (x+y)/G;
If x is odd and y is even, T(x,y) = 2 + T(x+y,x+2*y) <= (x+2*y+G)/G;
If x and y are both even, T(x,y) = 2 + T(b(2),y+b(2)) <= (y+A000265(x+y)+G)/G.
EXAMPLE
Array begins:
n\k 1 2 3 4 5 6 7
+------------------------------
1 | 0, 6, 2, 5, 3, 7, 2, ...
2 | 3, 4, 5, 6, 7, 4, 6, ...
3 | 1, 8, 0, 11, 4, 6, 4, ...
4 | 4, 6, 5, 5, 4, 6, 10, ...
5 | 3, 7, 2, 9, 0, 9, 6, ...
6 | 3, 4, 3, 5, 5, 4, 6, ...
7 | 1, 7, 5, 8, 3, 7, 0, ...
...
PROG
(PARI) T(n, k)={my(i=-1, z=0); while(z != n || z != k, z=n; n=k; k=(z+n)/2^(valuation(z+n, 2)); i++); i; };
CROSSREFS
KEYWORD
AUTHOR
Yifan Xie, Feb 03 2024
STATUS
approved