login
Square array read by descending antidiagonals: For T(n,k), define sequence {b(i)} where b(0) = n, b(1) = k, b(i) = A000265(b(i-1) + b(i-2)). T(n,k) is the number of steps until reaching the cyclic part of {b(i)}.
1

%I #45 Feb 20 2024 13:27:57

%S 0,6,3,2,4,1,5,5,8,4,3,6,0,6,3,7,7,11,5,7,3,2,4,4,5,2,4,1,15,6,6,4,9,

%T 3,7,9,8,9,4,6,0,5,5,8,4,10,6,14,10,9,5,8,8,5,7,6,6,2,9,6,4,3,6,1,6,3,

%U 11,4,8,8,8,6,7,8,5,5,13,6

%N Square array read by descending antidiagonals: For T(n,k), define sequence {b(i)} where b(0) = n, b(1) = k, b(i) = A000265(b(i-1) + b(i-2)). T(n,k) is the number of steps until reaching the cyclic part of {b(i)}.

%C 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).

%C 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.

%C 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.

%C 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;

%C If x is even and y is odd, T(x,y) = 1 + T(y,x+y) <= (x+y)/G;

%C If x is odd and y is even, T(x,y) = 2 + T(x+y,x+2*y) <= (x+2*y+G)/G;

%C If x and y are both even, T(x,y) = 2 + T(b(2),y+b(2)) <= (y+A000265(x+y)+G)/G.

%e Array begins:

%e n\k 1 2 3 4 5 6 7

%e +------------------------------

%e 1 | 0, 6, 2, 5, 3, 7, 2, ...

%e 2 | 3, 4, 5, 6, 7, 4, 6, ...

%e 3 | 1, 8, 0, 11, 4, 6, 4, ...

%e 4 | 4, 6, 5, 5, 4, 6, 10, ...

%e 5 | 3, 7, 2, 9, 0, 9, 6, ...

%e 6 | 3, 4, 3, 5, 5, 4, 6, ...

%e 7 | 1, 7, 5, 8, 3, 7, 0, ...

%e ...

%e 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.

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

%Y Cf. A000265.

%K nonn,easy,tabl

%O 1,2

%A _Yifan Xie_, Feb 03 2024