The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A033539 a(0)=1, a(1)=1, a(2)=1, a(n) = 2*a(n-1) + a(n-2) + 1. 5
 1, 1, 1, 4, 10, 25, 61, 148, 358, 865, 2089, 5044, 12178, 29401, 70981, 171364, 413710, 998785, 2411281, 5821348, 14053978, 33929305, 81912589, 197754484, 477421558, 1152597601, 2782616761, 6717831124, 16218279010, 39154389145 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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. LINKS T. D. Noe, Table of n, a(n) for n = 0..300 Antti Karttunen, More information Index entries for linear recurrences with constant coefficients, signature (3,-1,-1). FORMULA 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 G.f.: (1 - 2*x - x^2 + 3*x^3)/((1-x)*(1-2*x-x^2)). - Jaume Oliver Lafont, Sep 09 2009 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 a(n) = (3*A001333(n-1) - 1)/2. - R. J. Mathar, Mar 04 2013 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 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 EXAMPLE See the Python, Erlang (myrev), PARI (rev) and Forth definitions (REV3) given at Program section. 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. MAPLE 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 MATHEMATICA 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 *) Table[If[n==0, 1, (3*LucasL[n-1, 2] -2)/4], {n, 0, 30}] (* G. C. Greubel, Oct 13 2019 *) PROG (Haskell) a033539 n = a033539_list !! n a033539_list =    1 : 1 : 1 : (map (+ 1) \$ zipWith (+) (tail a033539_list)                                         (map (2 *) \$ drop 2 a033539_list)) -- Reinhard Zumkeller, Aug 14 2011 (PARI) /* needs version >= 2.5 */ /* function demonstrating the reversal of the lists and counting the function calls: */ 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 } 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 (Python) # function, demonstrating the reversal of the lists: def myrev(lista):   '''Reverses a list, in cumbersome way.'''   if(len(lista) < 2): return(lista)   else:     tr = myrev(lista[1:])     return([tr[0]]+myrev([lista[0]]+myrev(tr[1:]))) (Erlang) # definition, demonstrating the reversal of the lists: myrev([]) -> []; myrev([A]) -> [A]; myrev([X|Y]) ->    [A|B] = myrev(Y),    [A|myrev([X|myrev(B)])]. (Forth) # definition, demonstrating how to turn a parameter stack upside down: : 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 ; -- Antti Karttunen, Mar 04 2013 (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 (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 (Sage) [1]+[(3*lucas_number2(n-1, 2, -1) -2)/4 for n in (1..30)] # G. C. Greubel, Oct 13 2019 (GAP) Concatenation([1], List([1..30], n-> (3*Lucas(2, -1, n-1)[2] -2)/4 )); # G. C. Greubel, Oct 13 2019 (Prolog)    rev([], []).    rev([A], [A]).    rev([A|XB], [B|YA]) :- rev(XB, [B|Y]), rev(Y, X), rev([A|X], YA). % Lewis Baxter, Jan 04 2021 CROSSREFS Cf. A002203, A033538. Sequence in context: A276599 A281867 A298806 * A020748 A021004 A020709 Adjacent sequences:  A033536 A033537 A033538 * A033540 A033541 A033542 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 17 14:19 EDT 2022. Contains 353746 sequences. (Running on oeis4.)