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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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. 3
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(0)=1, a(1)=1, a(2)=1, a(3)=4, a(n)=3*a(n-1)-a(n-2)-a(n-3) [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 number of 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: A279101 A276599 A281867 * 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 December 13 19:20 EST 2017. Contains 295976 sequences.