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

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.

Links

Thomas Scheuerle, Table of n, a(n) for n = 0..5000

Index entries for sequences related to 3x+1 (or Collatz) problem

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

Example

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.

Prog

(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

Crossrefs

Sequence in context: A303911 A205575 A368338 * A349414 A257006 A363565

Adjacent sequences: A344580 A344581 A344582 * A344584 A344585 A344586

Keyword

nonn

Author

Thomas Scheuerle, May 24 2021

Status

approved