cp's OEIS Frontend

A096773 a(n) = 4*a(n-2) + 1 with a(1) = 0, a(2) = 3.

%I A096773 #117 Mar 19 2025 15:48:14
%S A096773 0,3,1,13,5,53,21,213,85,853,341,3413,1365,13653,5461,54613,21845,
%T A096773 218453,87381,873813,349525,3495253,1398101,13981013,5592405,55924053,
%U A096773 22369621,223696213,89478485,894784853,357913941,3579139413,1431655765
%N A096773 a(n) = 4*a(n-2) + 1 with a(1) = 0, a(2) = 3.
%C A096773 Remainders for classes m of integers n (mod 2^(m+1)). After applying one Collatz (3x+1)-transformation to the so-classified integers the result can be written in two classes (mod 6) only.
%C A096773 This classifying scheme covers all positive integers.
%C A096773 With one 3x+1-transformation T(x;p) := x' = (3x+1)/2^p, all numbers x, described in the form, with the free parameter i >= 0, x = i*2^N + a(N) result in x', describable by the two classes with the same parameter i:
%C A096773 x' = i*6 + 1 (for odd N>2), or x' = i*6 + 5 (for even N). Thus
%C A096773 x =  4*i +  3 -> x' = 6*i + 5, x =   8*i +  1 -> x' = 6*i + 1,
%C A096773 x = 16*i + 13 -> x' = 6*i + 5, x =  32*i +  5 -> x' = 6*i + 1,
%C A096773 x = 64*i + 53 -> x' = 6*i + 5, x = 128*i + 21 -> x' = 6*i + 1,
%C A096773 ....
%C A096773 all with "i" as a free parameter >= 0 covering all positive integers.
%H A096773 Michael De Vlieger, <a href="/A096773/b096773.txt">Table of n, a(n) for n = 1..3323</a>
%H A096773 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%H A096773 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,4,-4).
%F A096773 a(2m) = (5*2^(2m-1) - 1)/3, a(2m-1) = (2^(2m-2)-1)/3.
%F A096773 From _Paul Curtz_, Jul 01 2008; corrected by _Bob Selcoe_, Jul 28 2018: (Start)
%F A096773 a(2n) = 10*a(2n-1) + 3.
%F A096773 a(n+1) - 2*a(n) = A001045(n+2), signed. (End)
%F A096773 a(n) = (2^(n-1)*(3 + 2*(-1)^n) - 1)/3. - _L. Edson Jeffery_, Jul 12 2015
%F A096773 a(2n) = A086893(2n), a(2n+1) = A086893(2n-1), n > 0. - _Yosu Yurramendi_, Jan 17 2017
%F A096773 G.f.: -x^2*(-3+2*x) / ( (x-1)*(2*x+1)*(2*x-1) ). - _R. J. Mathar_, Mar 07 2017
%F A096773 a(2n) = A072197(n-1), n > 0; a(2n+1) = A002450(n), n >= 0. - _Yosu Yurramendi_, Mar 07 2017
%F A096773 a(2n) = (A266753(n) + A004171(n-1))/2, a(2n+1) = (A266753(n) - A004171(n-1))/2, n > 0. - _Yosu Yurramendi_, Mar 07 2017
%F A096773 a(n) = least residue 2*3^(2^(n-4)-1) - 1 (mod 2^n), n >= 5. - _Bob Selcoe_, Jul 26 2018
%F A096773 a(n) = 2*A176965(n-1) + 1 for n > 1. - _Loren M. Pearson_, Dec 06 2024
%e A096773 a(1) = (2^0-1)/3 =  0, a(2) = (5*2^1 - 1) / 3 =  3,
%e A096773 a(3) = (2^2-1)/3 =  1, a(4) = (5*2^3 - 1) / 3 = 13,
%e A096773 a(5) = (2^4-1)/3 =  5, a(6) = (5*2^5 - 1) / 3 = 53,
%e A096773 a(7) = (2^6-1)/3 = 21.
%e A096773 ....
%t A096773 a[1] = 0; a[2] = 3; a[n_] := a[n] = 4a[n - 2] + 1; Table[ a[n], {n, 35}] (* _Robert G. Wilson v_, Aug 20 2004 *)
%t A096773 Table[(2^(n - 1)*(3 + 2*(-1)^(n)) - 1)/3, {n, 10}] (* _L. Edson Jeffery_, Jul 12 2015 *)
%t A096773 nxt[{a_,b_}]:={b,4a+1}; NestList[nxt,{0,3},40][[;;,1]] (* or *) LinearRecurrence[{1,4,-4},{0,3,1},40] (* _Harvey P. Dale_, Mar 19 2025 *)
%o A096773 (Magma) [(2^(n-1)*(3 + 2*(-1)^n) - 1)/3: n in [1..40]]; // _Vincenzo Librandi_, Jul 12 2015
%o A096773 (Perl) # To map any (odd) v to its (r,c):
%o A096773 use bigint; $v=149; $r=$c=0; while(1){ $b=($v&1); $v>>=1; if ($b==($v&1)){ $c=($v>>1); last} $r++} $r&=1; # this splits the binary representation into two parts, at the first repeated digit from the right: the number of bits on the right is the row value, and the binary value on the left is the column value. Example: 149 => 1.00.10101 => (r,c)=(5,1). _Ruud H.G. van Tol_, Sep 23 2021
%o A096773 (PARI) apply( {A096773(n) = if(n%2, 1, 5)<<(n-1)\3}, [1..55]) \\ _M. F. Hasler_, May 28 2024
%o A096773 (Python) A096773=lambda n:((1 if n&1 else 5)<<n-1)//3 # _M. F. Hasler_, May 28 2024
%Y A096773 Bisections are A002450 & A072197.
%Y A096773 After the initial 0, column 1 of A257852.
%Y A096773 Cf. A176965.
%K A096773 easy,nonn
%O A096773 1,2
%A A096773 _Gottfried Helms_, Aug 15 2004