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

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

Offset: 0

Author

Antti Karttunen

Keywords

• nonn
• easy
• nice

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.

Examples

			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.
		

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

Crossrefs

Cf. A002203, A033538.

Programs

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

GAP

Concatenation([1], List([1..30], n-> (3*Lucas(2,-1,n-1)[2] -2)/4 )); # G. C. Greubel, Oct 13 2019

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

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

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 *)

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

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

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

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:])))

Sage

[1]+[(3*lucas_number2(n-1,2,-1) -2)/4 for n in (1..30)] # G. C. Greubel, Oct 13 2019

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