A038754 a(2n) = 3^n, a(2n+1) = 2*3^n.

1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Author

Henry Bottomley, May 03 2000

Keywords

• easy
• nice
• nonn

Comments

In general, for the recurrence a(n) = a(n-1)*a(n-2)/a(n-3), all terms are integers iff a(0) divides a(2) and first three terms are positive integers, since a(2n+k) = a(k)*(a(2)/a(0))^n for all nonnegative integers n and k.

Equals eigensequence of triangle A070909; (1, 1, 2, 3, 6, 9, 18, ...) shifts to the left with multiplication by triangle A070909. - Gary W. Adamson, May 15 2010

The a(n) represent all paths of length (n+1), n >= 0, starting at the initial node on the path graph P_5, see the second Maple program. - Johannes W. Meijer, May 29 2010

a(n) is the difference between numbers of multiple of 3 evil (A001969) and odious (A000069) numbers in interval [0, 2^(n+1)). - Vladimir Shevelev, May 16 2012

A "half-geometric progression": to obtain a term (beginning with the third one) we multiply the before previous one by 3. - Vladimir Shevelev, May 21 2012

Pisano periods: 1, 2, 1, 4, 8, 2, 12, 4, 1, 8, 10, 4, 6, 12, 8, 8, 32, 2, 36, 8, ... . - R. J. Mathar, Aug 10 2012

Numbers k such that the k-th cyclotomic polynomial has a root mod 3. - Eric M. Schmidt, Jul 31 2013

Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, Jun 05 2014

Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 1. - Sean A. Irvine, Jun 03 2025

Examples

			In the interval [0,2^5) we have 11 multiples of 3 numbers, from which 10 are evil and only one (21) is odious. Thus a(4) = 10 - 1 = 9. - _Vladimir Shevelev_, May 16 2012
		

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..1500 (first 401 terms from T. D. Noe)
• S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Vol. 332 (2014), pp. 45-54.
• Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
• Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.
• Sean A. Irvine, Walks on Graphs.
• Richard L. Ollerton and Anthony G. Shannon, Some properties of generalized Pascal squares and triangles, Fib. Q., 36 (1998), 98-109. See pages 106-7.
• Vladimir Shevelev, On monotonic strengthening of Newman-like phenomenon on (2m+1)-multiples in base 2m, arXiv:0710.3177 [math.NT], 2007.
• M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]
• Index entries for linear recurrences with constant coefficients, signature (0,3).

Crossrefs

Cf. A000045, A000069, A000079, A000120, A000244, A001969, A006720, A006721.

Cf. A006722, A006723, A008776, A028495, A030436, A037124, A048328, A061551.

Cf. A068911, A070909, A087503, A124302, A128588, A133464, A140730, A140740.

Cf. A178381, A182751, A182752, A182753, A182754, A182755, A182756, A182757.

Fifth row of the array A094718.

Programs

Haskell

import Data.List (transpose)
a038754 n = a038754_list !! n
a038754_list = concat $ transpose [a000244_list, a008776_list]
-- Reinhard Zumkeller, Oct 19 2015

Magma

[n le 2 select n else 3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Aug 18 2016

Maple

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=3*a[n-2]+2 od: seq(a[n]+1, n=0..34); # Zerinvary Lajos, Mar 20 2008
with(GraphTheory): P:=5: G:=PathGraph(P): A:= AdjacencyMatrix(G): nmax:=35; for n from 1 to nmax do B(n):=A^n; a(n):=add(B(n)[1,k],k=1..P) od: seq(a(n),n=1..nmax); # Johannes W. Meijer, May 29 2010

Mathematica

LinearRecurrence[{0,3},{1,2},40] (* Harvey P. Dale, Jan 26 2014 *)
CoefficientList[Series[(1+2x)/(1-3x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 18 2016 *)
Module[{nn=20,c},c=3^Range[0,nn];Riffle[c,2c]] (* Harvey P. Dale, Aug 21 2021 *)

PARI

a(n)=(1/6)*(5-(-1)^n)*3^floor(n/2)

PARI

a(n)=3^(n>>1)<
				

SageMath

[2^(n%2)*3^((n-(n%2))/2) for n in range(61)] # G. C. Greubel, Oct 10 2022

Formula

a(n) = a(n-1)*a(n-2)/a(n-3) with a(0)=1, a(1)=2, a(2)=3.

a(2*n) = (3/2)*a(2*n-1) = 3^n, a(2*n+1) = 2*a(2*n) = 2*3^n.

From Benoit Cloitre, Apr 27 2003: (Start)

a(1)=1, a(n)= 2*a(n-1) if a(n-1) is odd, or a(n)= (3/2)*a(n-1) if a(n-1) is even.

a(n) = (1/6)*(5-(-1)^n)*3^floor(n/2).

a(2*n) = a(2*n-1) + a(2*n-2) + a(2*n-3).

a(2*n+1) = a(2*n) + a(2*n-1). (End)

G.f.: (1+2*x)/(1-3*x^2). - Paul Barry, Aug 25 2003

From Reinhard Zumkeller, Sep 11 2003: (Start)

a(n) = (1 + n mod 2) * 3^floor(n/2).

a(n) = A087503(n) - A087503(n-1). (End)

a(n) = sqrt(3)*(2+sqrt(3))*(sqrt(3))^n/6 - sqrt(3)*(2-sqrt(3))*(-sqrt(3))^n/6. - Paul Barry, Sep 16 2003

From Reinhard Zumkeller, May 26 2008: (Start)

a(n) = A140740(n+2,2).

a(n+1) = a(n) + a(n - n mod 2). (End)

If p(i) = Fibonacci(i-3) and if A is the Hessenberg matrix of order n defined by A(i,j) = p(j-i+1), (i<=j), A(i,j)=-1, (i=j+1), and A(i,j)=0 otherwise. Then, for n>=1, a(n-1) = (-1)^n det A. - Milan Janjic, May 08 2010

a(n) = A182751(n) for n >= 2. - Jaroslav Krizek, Nov 27 2010

a(n) = Sum_{i=0..2^(n+1), i==0 (mod 3)} (-1)^A000120(i). - Vladimir Shevelev, May 16 2012

a(0)=1, a(1)=2, for n>=3, a(n)=3*a(n-2). - Vladimir Shevelev, May 21 2012

Sum_(n>=0) 1/a(n) = 9/4. - Alexander R. Povolotsky, Aug 24 2012

a(n) = sqrt(3*a(n-1)^2 + (-3)^(n-1)). - Richard R. Forberg, Sep 04 2013

a(n) = 2^((1-(-1)^n)/2)*3^((2*n-1+(-1)^n)/4). - Luce ETIENNE, Aug 11 2014

From Reinhard Zumkeller, Oct 19 2015: (Start)

a(2*n) = A000244(n), a(2*n+1) = A008776(n).

For n > 0: a(n+1) = a(n) + if a(n) odd then min{a(n), a(n-1)} else max{a(n), a(n-1)}, see also A128588. (End)

E.g.f.: (7*cosh(sqrt(3)*x) + 4*sqrt(3)*sinh(sqrt(3)*x) - 4)/3. - Stefano Spezia, Feb 17 2022

Sum_{n>=0} (-1)^n/a(n) = 3/4. - Amiram Eldar, Dec 02 2022