proposed

approved

editing

proposed

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, and they can't be smaller than G. Hence this sequence can only last for (max(b(2),b(3)) - G) terms without going down to G, ending no later than max(b(2*max(b(2),b(3)) - 2*G + 1), b(2*max(b(2),b(3)) - 2*G + 2)) and the assumption never holds afterwards, meaning that the sequence enters which is a repeated cycle, so T(n,k) <= 2*max(b(3), b(4)) - 2*G + 2contradiction.

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.

T(n,k) <= 2*n + 4*k - 2*gcd(n,k) + 2.

proposed

editing

editing

proposed

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 >= 5, 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 >= 5, 4, implying that max(b(32), b(43)) > max(b(54), b(65)) > ..., with a decreasing sequence of positive integers, and they can't be smaller than G. Hence this sequence can only last for (max(b(32), b(43)) - G) terms without going down to G, ending no later than max(b(2*max(b(32), b(43)) - 2*G + 1), b(2*max(b(32), b(43)) - 2*G + 2)) and the assumption never holds afterwards, meaning that the sequence enters a repeated cycle, so T(n,k) <= 2*max(b(3), b(4)) - 2*G + 2.

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

b(i) is the odd part of b(i-1) + b(i-2). Thus, so that b(i) is odd for all i >= 3. 2 and b(i) <= (b(i-1) + b(i-2))/2 for i >= 54 (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) means and T(n,k) = i for the place that first happens; and the sequence b enters a repeated cycle, T(x, y) = i-1. gcd(b(i), term there is b(i+1) = A000265(gcd(x, y)) is the repeating part. Denote it as n,k)) = G.

We prove the cycle's existence by contradiction. Suppose {b(ni)} 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 >= 5, 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 >= 5, implying that max(b(3), b(4)) > max(b(5), b(6)) > ..., with a decreasing sequence of positive integers, and they can't be smaller than kG. Hence this sequence can only last for (max(b(3), b(4)) - kG) terms without going down to k, G, ending no later than max(b(2*max(b(3), b(4)) - 2*k G + 1), b(2*max(b(3), b(4)) - 2*k G + 2)) and the assumption never holds afterwards, meaning that the sequence enters a repeated cycle, so T(x, yn,k) <= 2*max(b(3), b(4)) - 2*k G + 2.

T(x,yn,k) <= 2*x n + 4*y k - 2*gcd(x, yn,k) + 2.

Square array T(x,y) begins:

Array begins:

x n\y 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 the its sequence b begins with b(10) = 1, b(21) = 2, b(32) = A000265(1+2) = 3, b(43) = A000265(2+3) = 5, b(54) = 1, b(65) = 3, b(6) = 1, b(7) = 1, b(8) = 1, which has reached b(9i) = b(i+1, and so on) = b(i+2) at i=6.

(PARI) T(x, yn, k)={my(i=0, -1, z=0); while(z != x n || z != y, k, z=xn; xn=yk; yk=(z+xn)/2^(valuation(z+x, n, 2)); i++); i-1; };

proposed

editing

editing

proposed

x\y 1 2 3 4 5 6 7 ...

[1] 0, 6, 2, 5, 3, 7, 2, ...

[1] 1, 7, 3, 0, 6, 4, 8, 2, 5, 3, 7, 2, ...

[2] 3, 4, 5, 6, 7, 8, 5, 7, 4, 6, ...

[3] 2, 9, 1, 12, 5, 7, 5, 8, 0, 11, 4, 6, 4, ...

[4] 5, 7, 6, 4, 6, 5, 7, 11, 5, 4, 6, 10, ...

[5] 4, 8, 3, 10, 1, 10, 7, 2, 9, 0, 9, 6, ...

[6] 3, 4, 3, 5, 5, 4, 6, 6, 5, 7, ...

[7] 2, 8, 6, 9, 4, 8, 1, 7, 5, 8, 3, 7, 0, ...

1, 7, 4, 0, 6, 3, 5, 2, 6, 6, 9, 5, 4, 7, 1, 7, 4, 8, 8, 12, 6, 5, 5, 8, 4, 3, 5, 5, 6, 0, 6, 3, 5, 2, 16, 7, 7, 11, 5, 10, 7, 3, 2, 4, 4, 8, 10, 9, 10, 5, 7, 2, 4, 1, 15, 6, 6, 4, 9, 5, 11, 3, 7, 15, 11, 10, 6, 9, 8, 9, 4, 6, 0, 5, 5, 8, 7, 7, 3, 4, 10, 6, 14, 10, 7, 9, 5, 8, 8, 5, 4, 7, 6, 6, 2, 7, 4, 12, 5, 9, 9, 9, 7, 8, 9, 6, 4, 3, 6, 1, 6, 3, 11, 4, 8, 8, 8, 6, 14, 7, 8, 5, 5, 13, 6