%I #44 Sep 06 2023 21:08:39
%S 2,1,7,3,27,11,107,43,427,171,1707,683,6827,2731,27307,10923,109227,
%T 43691,436907,174763,1747627,699051,6990507,2796203,27962027,11184811,
%U 111848107,44739243,447392427,178956971
%N a(n) = (1 + 2^n*(3 + 2*(-1)^n))/3.
%C Let N_1 be the set of odd natural numbers and v(y) the 2-adic valuation of y. Define the map F : N_1 -> N_1 by F(x) = (3*x+1)/2^v(3*x+1) (see A075677). Let F^(k)(x) denote k-fold iteration of F, with recurrence F^(k)(x) = F(F^(k-1)(x)), k > 0, and initial condition F^(0)(x) = x. Then, for n>0, a(n) is the least m such that F^(n)(4*m-3) == 1 (mod 4). Cf. A257499.
%C Let k == 1 mod 4, and k(r) be the r-th iteration at which k appears in a Collatz sequence. When n >= 2 and k(r) == [2^(n+1) - a(n)] mod 2^(n+1), then n is the number of halving steps following k(r+1). For instance, since a(5) = 11, there are 5 halving steps following k(r+1) when k(r) == 53 mod 64, because 2^(5+1) = 64 and 64-11 = 53; e.g., k(r) = 117: 117 -> 352 -> 176 -> 88 -> 44 -> 22 -> 11. - _Bob Selcoe_, Feb 09 2017
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,4,-4).
%F a(2*n) = A136412(n); a(2*n+1) = A007583(n).
%F G.f.: (2-x-2*x^2)/((x-1)*(2*x-1)*(2*x+1)). - _R. J. Mathar_, Jul 25 2015
%F a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3) for n > 2. - _Wesley Ivan Hurt_, Nov 05 2015
%F a(n) = 4*a(n-2) - 1. - _Bob Selcoe_, Feb 09 2017
%F a(n) = 2^(n+1) - A096773(n+1). - _Ruud H.G. van Tol_, Sep 04 2023
%p A255138:=n->(1 + 2^n*(3 + 2*(-1)^n))/3: seq(A255138(n), n=0..50); # _Wesley Ivan Hurt_, Nov 05 2015
%t a[n_] := (1 + 2^n*(3 + 2*(-1)^n))/3; Table[a[n], {n, 0, 29}]
%o (PARI) vector(30, n, n--; (1 + 2^n*(3 + 2*(-1)^n))/3) \\ _Altug Alkan_, Nov 05 2015
%o (Magma) [(1 + 2^n*(3 + 2*(-1)^n))/3: n in [0..50]]; // _Wesley Ivan Hurt_, Nov 05 2015
%Y Cf. A007583, A075677, A096773, A136412, A257499.
%K nonn,easy
%O 0,1
%A _L. Edson Jeffery_, May 04 2015
|