A344583 Let f(k) = k/2 if k is even, otherwise (3*k+2*a(n)+1)/2, a(n) is the smallest integer greater than -1, where n = f^j(n) for j > 0 exists. f^j(n) means j times recursion into f(n).

0, 0, 0, 1, 2, 2, 1, 3, 5, 4, 2, 3, 7, 5, 3, 7, 5, 8, 4, 2, 3, 10, 5, 2, 16, 5, 5, 13, 9, 2, 7, 2, 20, 10, 8, 5, 22, 2, 2, 16, 11, 11, 10, 5, 12, 22, 2, 11, 16, 2, 8, 25, 5, 14, 13, 8, 9, 7, 2, 8, 10, 8, 5, 31, 20, 18, 16, 15, 12, 7, 5, 8, 49, 8, 12, 16, 2, 8, 16, 5, 27, 40

Offset: 0

Author

Thomas Scheuerle, May 24 2021

Keywords

• nonn

Comments

This sequence is self-similar under multiplication by factor 3.

If Collatz conjecture is true, the only zeros in this sequence are a(0), a(1) and a(2).

This sequence could be extended to all non-integer numbers of the form n = a/3. This requires a generalization of "odd" and "even" such that if n is of the form n = m/(2*b+1), n will be considered as even when m is even. In this case the formula (a(3*n)-1)/a(n) = 3 will hold for fractional n too.

Examples

			We may see this sequence as a sequence of functions:
0 -> f_0(k) =  k/2 ; (3*k+1)/2.
1 -> f_1(k) =  k/2 ; (3*k+3)/2.
2 -> f_2(k) =  k/2 ; (3*k+5)/2.
a(58) = 2 because: f_2(58) = 58/2 = 29, f_2(29) = (29*3+2*2+1)/2 = 46, f_2(46) = 46/2 = 23, f_2(23) = (23*3+2*2+1)/2 = 37, f_2(37) = (37*3+2*2+1)/2 = 58.
This shows that f_2(f_2(f_2(f_2(f_2(58))))) = 58.
a(58) is not < 2 because no such loop which includes 58 exists for f_0 and f_1.
		

Links

• Thomas Scheuerle, Table of n, a(n) for n = 0..5000
• Index entries for sequences related to 3x+1 (or Collatz) problem

Programs

MATLAB

function a = A344583 ( max_n )
    for n = 1:max_n
        a_n = 0; stop = 0;
        while stop == 0
            v = [n]; k = n;
            while length(v) == length(unique(v)) %run until results repeat
                % Caution: If orbits without cycles exist, this may become
                % an endless loop.
                k = f( k,a_n );
                v = [v k];
                if k == n
                    a(n) = a_n;
                    stop = 1; break;
                end
            end
            a_n = a_n+1;
        end
    end
end
function [ out ] = f( k,a_n )
    if mod(k,2) == 0
        out = k/2;
    else
        out = ((k*3) + (1+ 2*a_n))/2;
    end
end

PARI

isperiodic(v, z) = for (k=1, #v, if (v[k] == z, return(1)));
f(x, k) = if (x%2, (3*x+2*k+1)/2, x/2);
isok(k, n) = {my(v=[n], y=n); for (i=1, oo, my(z=f(y, k)); if (z == n, return (1)); if (isperiodic(v, z), return(0)); v = concat(v, z); y = z;);}
a(n) = {my(k=0); while (!isok(k, n), k++); k;} \\ Michel Marcus, Jun 14 2021

Formula

a(n) <= (n-1)/2 for all odd n > 0.

(a(3*n)-1)/a(n) = 3 if n > 2.

a(2*n) >= a(n).