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

%I #59 Jun 14 2021 11:54:44

%S 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,

%T 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,

%U 8,10,8,5,31,20,18,16,15,12,7,5,8,49,8,12,16,2,8,16,5,27,40

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

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

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

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

%H Thomas Scheuerle, <a href="/A344583/b344583.txt">Table of n, a(n) for n = 0..5000</a>

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

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

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

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

%e We may see this sequence as a sequence of functions:

%e 0 -> f_0(k) = k/2 ; (3*k+1)/2.

%e 1 -> f_1(k) = k/2 ; (3*k+3)/2.

%e 2 -> f_2(k) = k/2 ; (3*k+5)/2.

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

%e This shows that f_2(f_2(f_2(f_2(f_2(58))))) = 58.

%e a(58) is not < 2 because no such loop which includes 58 exists for f_0 and f_1.

%o (MATLAB)

%o function a = A344583 ( max_n )

%o for n = 1:max_n

%o a_n = 0; stop = 0;

%o while stop == 0

%o v = [n]; k = n;

%o while length(v) == length(unique(v)) %run until results repeat

%o % Caution: If orbits without cycles exist, this may become

%o % an endless loop.

%o k = f( k,a_n );

%o v = [v k];

%o if k == n

%o a(n) = a_n;

%o stop = 1; break;

%o end

%o end

%o a_n = a_n+1;

%o end

%o end

%o end

%o function [ out ] = f( k,a_n )

%o if mod(k,2) == 0

%o out = k/2;

%o else

%o out = ((k*3) + (1+ 2*a_n))/2;

%o end

%o end

%o (PARI) isperiodic(v, z) = for (k=1, #v, if (v[k] == z, return(1)));

%o f(x, k) = if (x%2, (3*x+2*k+1)/2, x/2);

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

%o a(n) = {my(k=0); while (!isok(k, n), k++); k;} \\ _Michel Marcus_, Jun 14 2021

%K nonn

%O 0,5

%A _Thomas Scheuerle_, May 24 2021