cp's OEIS Frontend

A033539 a(0)=1, a(1)=1, a(2)=1, a(n) = 2*a(n-1) + a(n-2) + 1.

%I A033539 #77 Feb 21 2022 02:18:16
%S A033539 1,1,1,4,10,25,61,148,358,865,2089,5044,12178,29401,70981,171364,
%T A033539 413710,998785,2411281,5821348,14053978,33929305,81912589,197754484,
%U A033539 477421558,1152597601,2782616761,6717831124,16218279010,39154389145
%N A033539 a(0)=1, a(1)=1, a(2)=1, a(n) = 2*a(n-1) + a(n-2) + 1.
%C A033539 a(n) or a(n+1) gives the number of times certain simple recursive procedures are called to effect a reversal of a sequence of n elements (including both the top-level call and any subsequent recursive calls). See example and program lines.
%H A033539 T. D. Noe, <a href="/A033539/b033539.txt">Table of n, a(n) for n = 0..300</a>
%H A033539 Antti Karttunen, <a href="http://www.iki.fi/~kartturi/software/stacks.lsp">More information</a>
%H A033539 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1).
%F A033539 a(n) = (3/4)*(1+sqrt(2))^(n-1) + 3/4*(1-sqrt(2))^(n-1) - 1/2 + 3*0^n, with n >= 0. - _Jaume Oliver Lafont_, Sep 10 2009
%F A033539 G.f.: (1 - 2*x - x^2 + 3*x^3)/((1-x)*(1-2*x-x^2)). - _Jaume Oliver Lafont_, Sep 09 2009
%F A033539 a(n) = 3*a(n-1) - a(n-2) - a(n-3), a(0)=1, a(1)=1, a(2)=1, a(3)=4. - _Harvey P. Dale_, Nov 20 2011
%F A033539 a(n) = (3*A001333(n-1) - 1)/2. - _R. J. Mathar_, Mar 04 2013
%F A033539 a(n) = -1/2 - (3/4)*(1+sqrt(2))^n - (3/4)*sqrt(2)*(1-sqrt(2))^n - (3/4)*(1-sqrt(2))^n + (3/4)*(1+sqrt(2))^n*sqrt(2) for n >= 1. - _Alexander R. Povolotsky_, Mar 05 2013
%F A033539 E.g.f.: 3 + (1/2)*exp(x)*(-1 - 3*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x)). - _Stefano Spezia_, Oct 13 2019
%e A033539 See the Python, Erlang (myrev), PARI (rev) and Forth definitions (REV3) given at Program section.
%e A033539 PARI, Python and Erlang functions are called a(n+1) times for the list of length n, while Forth word REV3 is called a(n) times if there are n elements in the parameter stack.
%p A033539 seq(coeff(series((1 -2*x -x^2 +3*x^3)/((1-x)*(1-2*x-x^2)), x, n+1), x, n), n = 0..30); # _G. C. Greubel_, Oct 13 2019
%t A033539 Join[{1},RecurrenceTable[{a[0]==a[1]==1,a[n]==2a[n-1]+a[n-2]+1},a,{n,30}]] (* or *) LinearRecurrence[{3,-1,-1},{1,1,1,4},30] (* _Harvey P. Dale_, Nov 20 2011 *)
%t A033539 Table[If[n==0, 1, (3*LucasL[n-1, 2] -2)/4], {n, 0, 30}] (* _G. C. Greubel_, Oct 13 2019 *)
%o A033539 (Haskell)
%o A033539 a033539 n = a033539_list !! n
%o A033539 a033539_list =
%o A033539    1 : 1 : 1 : (map (+ 1) $ zipWith (+) (tail a033539_list)
%o A033539                                         (map (2 *) $ drop 2 a033539_list))
%o A033539 -- _Reinhard Zumkeller_, Aug 14 2011
%o A033539 (PARI)
%o A033539 /* needs version >= 2.5 */
%o A033539 /* function demonstrating the reversal of the lists and counting the function calls: */
%o A033539 rev( L )={ cnt++; if( #L>1, my(x,y); x=L[#L]; listpop(L); L=rev(L); y=L[#L]; listpop(L); L=rev(L); listput(L,x); L=rev(L); listput(L,y)); L }
%o A033539 for(n=0,50,cnt=0;print(n": rev(",L=List(vector(n,i,i)),")=",rev(L),",  cnt="cnt)) \\ _Antti Karttunen_, Mar 05 2013, partially based on previous PARI code from _Michael Somos_, 1999. Edited by _M. F. Hasler_, Mar 05 2013
%o A033539 (Python)
%o A033539 # function, demonstrating the reversal of the lists:
%o A033539 def myrev(lista):
%o A033539   '''Reverses a list, in cumbersome way.'''
%o A033539   if(len(lista) < 2): return(lista)
%o A033539   else:
%o A033539     tr = myrev(lista[1:])
%o A033539     return([tr[0]]+myrev([lista[0]]+myrev(tr[1:])))
%o A033539 (Erlang)
%o A033539 # definition, demonstrating the reversal of the lists:
%o A033539 myrev([]) -> [];
%o A033539 myrev([A]) -> [A];
%o A033539 myrev([X|Y]) ->
%o A033539    [A|B] = myrev(Y),
%o A033539    [A|myrev([X|myrev(B)])].
%o A033539 (Forth)
%o A033539 # definition, demonstrating how to turn a parameter stack upside down:
%o A033539 : REV3 DEPTH 0= IF ELSE DEPTH 1 = IF ELSE DEPTH 2 = IF SWAP ELSE >R RECURSE R> SWAP >R >R RECURSE R> RECURSE R> THEN THEN THEN ;
%o A033539 -- _Antti Karttunen_, Mar 04 2013
%o A033539 (PARI) concat([1], vector(30, n, (3*sum(k=0,(n-1)\2, binomial(n-1,2*k) * 2^k) - 1)/2 )) \\ _G. C. Greubel_, Oct 13 2019
%o A033539 (Magma) I:=[1,1,4]; [1] cat [n le 3 select I[n] else 3*Self(n-1) - Self(n-2) - Self(n-3): n in [1..30]]; // _G. C. Greubel_, Oct 13 2019
%o A033539 (Sage) [1]+[(3*lucas_number2(n-1,2,-1) -2)/4 for n in (1..30)] # _G. C. Greubel_, Oct 13 2019
%o A033539 (GAP) Concatenation([1], List([1..30], n-> (3*Lucas(2,-1,n-1)[2] -2)/4 )); # _G. C. Greubel_, Oct 13 2019
%o A033539 (Prolog)
%o A033539    rev([],[]).
%o A033539    rev([A],[A]).
%o A033539    rev([A|XB],[B|YA]) :-
%o A033539 rev(XB,[B|Y]), rev(Y,X), rev([A|X],YA). % _Lewis Baxter_, Jan 04 2021
%Y A033539 Cf. A002203, A033538.
%K A033539 nonn,easy,nice
%O A033539 0,4
%A A033539 _Antti Karttunen_