A369876 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)}.

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, 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, 11, 4, 8, 8, 8, 6, 7, 8, 5, 5, 13, 6

Offset: 1

Author

Yifan Xie, Feb 03 2024

Keywords

• nonn
• easy
• tabl

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.

Examples

			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.
		

Crossrefs

Cf. A000265.

Programs

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