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

A. 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)/((x-1)*(x^2+2*x-1)). - 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

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.

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

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

CROSSREFS

Cf. A033538.

Sequence in context: A276599 A281867 A298806 * A020748 A021004 A020709

Adjacent sequences:  A033536 A033537 A033538 * A033540 A033541 A033542

KEYWORD

nonn,easy,nice

AUTHOR

Antti Karttunen

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 09:28 EDT 2018. Contains 316339 sequences. (Running on oeis4.)