1,2

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.

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, ...

...

T(1,2) = 6 because its sequence b begins with b(0) = 1, b(1) = 2, b(2) = A000265(1+2) = 3, b(3) = A000265(2+3) = 5, b(4) = 1, b(5) = 3, b(6) = 1, b(7) = 1, b(8) = 1, which has reached b(i) = b(i+1) = b(i+2) at i=6.

(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; };

Cf. A000265.

Sequence in context: A254593 A356070 A153607 * A010494 A333239 A078333

Adjacent sequences: A369873 A369874 A369875 * A369877 A369878 A369879

nonn,easy,tabl

Yifan Xie, Feb 03 2024

approved