login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%S 1,1,1,4,10,25,61,148,358,865,2089,5044,12178,29401,70981,171364,

%T 413710,998785,2411281,5821348,14053978,33929305,81912589,197754484,

%U 477421558,1152597601,2782616761,6717831124,16218279010,39154389145

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

%C 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 T. D. Noe, <a href="/A033539/b033539.txt">Table of n, a(n) for n = 0..300</a>

%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/software/stacks.lsp">More information</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1).

%F 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 G.f.: (1-2*x-x^2+3*x^3)/((x-1)*(x^2+2*x-1)). - _Jaume Oliver Lafont_, Sep 09 2009

%F 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 a(n) = (3*A001333(n-1) - 1)/2. - _R. J. Mathar_, Mar 04 2013

%F 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 See the Python, Erlang (myrev), Pari (rev) and Forth definitions (REV3) given at Program section.

%e 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.

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

%o (Haskell)

%o a033539 n = a033539_list !! n

%o a033539_list =

%o 1 : 1 : 1 : (map (+ 1) $ zipWith (+) (tail a033539_list)

%o (map (2 *) $ drop 2 a033539_list))

%o -- _Reinhard Zumkeller_, Aug 14 2011

%o (PARI) /* needs version >= 2.5 */

%o /* function demonstrating the reversal of the lists and counting the function calls: */

%o 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 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 (Python) # function, demonstrating the reversal of the lists:

%o def myrev(lista):

%o '''Reverses a list, in cumbersome way.'''

%o if(len(lista) < 2): return(lista)

%o else:

%o tr = myrev(lista[1:])

%o return([tr[0]]+myrev([lista[0]]+myrev(tr[1:])))

%o (Erlang) # definition, demonstrating the reversal of the lists:

%o myrev([]) -> [];

%o myrev([A]) -> [A];

%o myrev([X|Y]) ->

%o [A|B] = myrev(Y),

%o [A|myrev([X|myrev(B)])].

%o (Forth) # definition, demonstrating how to turn a parameter stack upside down:

%o : 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 -- _Antti Karttunen_, Mar 04 2013

%Y Cf. A033538.

%K nonn,easy,nice

%O 0,4

%A _Antti Karttunen_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 20 07:27 EDT 2019. Contains 321345 sequences. (Running on oeis4.)