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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000244 Powers of 3.
(Formerly M2807 N1129)
496
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Same as Pisot sequences E(1,3), L(1,3), P(1,3), T(1,3). Essentially same as Pisot sequences E(3,9), L(3,9), P(3,9), T(3,9). See A008776 for definitions of Pisot sequences.

Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2n + 2, s(0) = 1, s(2n+2) = 3. - Herbert Kociemba, Jun 10 2004

a(1) = 1, a(n+1) is the least number so that there are a(n) even numbers between a(n) and a(n+1). Generalization for the sequence of powers of k: 1, k, k^2, k^3, k^4,... There are a(n) multiples of k-1 between a(n) and a(n+1). - Amarnath Murthy, Nov 28 2004

a(n) = sum of (n+1)-th row in Triangle A105728. - Reinhard Zumkeller, Apr 18 2005

With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, sum_{i=1}^{p(n)} = sum over i and prod_{j = 1}^{d(i)} = product over j one has: a(n) = sum_{i = 1}^{p(n)} (p(i)!/(prod_{j = 1}^{d(i)} m(i, j)!))*2^(p(i) - 1) - Thomas Wieder, May 18 2005

For any k > 1 in the sequence, k is the first prime power appearing in the prime decomposition of repunit R_k, i.e., of A002275(k). - Lekraj Beedassy, Apr 24 2006

a(n-1) is the number of compositions of compositions. In general, (k+1)^(n-1) is the number of k-levels nested compositions (e.g., 4^(n-1) is the number of compositions of compositions of compositions, etc.). Each of the n - 1 spaces between elements can be a break for one of the k levels, or not a break at all. - Franklin T. Adams-Watters, Dec 06 2006

Let S be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xSy if x is a subset of y. Then a(n) = |S|. - Ross La Haye, Dec 22 2006

If X_1, X_2, ..., X_n is a partition of the set {1, 2, ..., 2*n} into blocks of size 2 then, for n >= 1, a(n) is equal to the number of functions f : {1, 2, ..., 2*n} -> {1, 2} such that for fixed y_1, y_2, ..., y_n in {1, 2} we have f(X_i) <> {y_i}, (i = 1, 2, ..., n). - Milan Janjic, May 24 2007

This is a general comment on all sequences of the form a(n) = [(2^k)-1]^n for all positive integers k. Example 1.1.16 of Stanley's "Enumerative Combinatorics" offers a slightly different version. a(n) in the number of functions f:[n] into P([k]) - {}. a(n) is also the number of functions f:[k] into P([n]) such that the generalized intersection of f(i) for all i in [k] is the empty set. Where [n] = {1, 2, ..., n}, P([n]) is the power set of [n] and {} is the empty set. - Geoffrey Critzer, Feb 28 2009

a(n) = A064614(A000079(n)) and A064614(m)<a(n) for m < A000079(n). - Reinhard Zumkeller, Feb 08 2010

3^(n+1) = (1, 2, 2, 2,...) dot (1, 1, 3, 9, ..., 3^n); e.g., 3^3 = 27 = (1, 2, 2, 2) dot (1, 1, 3, 9) = (1 + 2 + 6 + 18). - Gary W. Adamson, May 17 2010

a(n) is the number of generalized compositions of n when there are 3*2^i different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010

For n >= 1, a(n-1) is the number of generalized compositions of n when there are 2^(i-1) different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010

The sequence in question ("Powers of 3") also describes the number of moves of the k-th disk solving the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower of Hanoi puzzle (cf. A183111 - A183125).

a(n) is the number of Stern polynomials of degree n. See A057526. - T. D. Noe, Mar 01 2011

Positions of records in the number of odd prime factors, A087436. - Juri-Stepan Gerasimov, Mar 17 2011

Sum of coefficients of the expansion of (1+x+x^2)^n. - Adi Dani, Jun 21 2011

a(n) is the number of compositions of n elements among {0, 1, 2}; e.g., a(2) = 9 since there are the 9 compositions 0 + 0, 0 + 1, 1 + 0, 0 + 2, 1 + 1, 2 + 0, 1 + 2, 2 + 1, and 2 + 2. [From Adi Dani, Jun 21 2011, modified by editors.]

Except the first two terms, these are odd numbers n such that no x with 2 <= x <= n - 2 satisfy x^(n-1) == 1 (mod n). - Arkadiusz Wesolowski, Jul 03 2011

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 3-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011

Also, first and least element of the matrix [1, sqrt(2); sqrt(2), 2]^(n+1). - M. F. Hasler, Nov 25 2011

One-half of the row sums of the triangular version of A035002. - J. M. Bergot, Jun 10 2013

Form an array with m(0, n) = m(n, 0) = 2^n; m(i, j) equals the sum of the terms to the left of m(i, j) and the sum of the terms above m(i, j), which is m(i, j) = sum[m(i, k) {k = 0...j-1}] + sum[m(k, j) {k = 0...i-1}].  The sum of the terms in antidiagonal(n+1) = 4*a(n). - J. M. Bergot, Jul 10 2013

a(n) = A007051(n+1) - A007051(n), and A007051 are the antidiagonal sums of an array defined by m(0, k) = 1 and m(n, k) = sum_{c = 0..k-1} m(n, c) + sum_{r = 0..n-1} m(r, k), which is the sum of the terms to left of m(n, k) plus those above m(n, k). m(1, k) = A000079(k); m(2, k) = A045623(k+1); m(k+1, k) = A084771(k). - J. M. Bergot, Jul 16 2013

Define an array to have m(0, k) = 2^k and m(n,k) = sum{c = 0..k-1} m(n, c) + sum{r = 0...n-1} m(r, k), which is the sum of the terms to the left of m(n, k) plus those above m(n, k). Row n = 0 of the array comprises A000079, column k = 0 comprises A011782, row n = 1 comprises A001792. Antidiagonal sums of the array are a(n): 1 = 3^0, 1 + 2 = 3^1, 2 + 3 + 4 = 3^2, 4 + 7 + 8 + 8 = 3^3. - J. M. Bergot, Aug 02 2013

The sequence with interspersed zeros and o.g.f. x/(1- 3*x^2), A(2*k) = 0, A(2*k+1) = 3^k = a(k), k >= 0, can be called hexagon numbers. This is because the algebraic number rho(6) = 2*cos(Pi/6) = sqrt(3) of degree 2, with minimal polynomial C(6, x) = x^2 - 3 (see A187360, n = 6), is the length ratio of the smaller diagonal and the side in the hexagon. Hence rho(6)^n = A(n-1)*1 + A(n)*rho(6), in the power basis of the quadratic number field Q(rho(6)). One needs also A(-1) = 1. See also a Dec 02 2010 comment and the P. Steinbach reference given in A049310. - Wolfdieter Lang, Oct 02 2013

Numbers n such that sigma(3n) = 3n + sigma(n). - Jahangeer Kholdi, Nov 23 2013

All powers of 3 are perfect totient numbers (A082897), since phi(3^n) = 2 * 3^(n - 1) for n > 0, and thus sum(i = 0..n phi(3^i)) = 3^n. - Alonso del Arte, Apr 20 2014

The least number k > 0 such that 3^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 13, 93}. The consecutive increasing digits are {3, 23, 123}. There are 100 different 3-digit endings for 3^k. There are no k-values such that 3^k ends in '012', '234', '345', '456', '567', '678', or '789'. The k-values for which 3^k ends in '123' are given by 93 mod 100. For k = 93 + 100*x, the digit immediately before the run of '123' is {9, 5, 1, 7, 3, 9, 5, 1, 3, 7, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '123' will never be a 0. So, this sequence is finite and full. - Derek Orr, Jul 03 2014

All elements of A^n where A=(1,1,1;1,1,1;1,1,1). - David Neil McGrath, Jul 23 2014

Counts all walks of length n (open or closed) on the vertices of a triangle containing a loop at each vertex starting from any given vertex. - David Neil McGrath, Oct 03 2014

a(n) counts walks (closed) on the graph G(1-vertex;1-loop,1-loop,1-loop). - David Neil McGrath, Dec 11 2014

2*a(n-2) counts all permutations of a solitary closed walk of length (n) from the vertex of a triangle that contains 2 loops on each of the remaining vertices. In addition, C(m,k)=2*(2^m)*B(m+k-2,m) counts permutations of walks that contain (m) loops and (k) arcs. - David Neil McGrath, Dec 11 2014

a(n) is the number of all elements (m-dimensional faces) in an n-dimensional cube or in an n-dimensional orthoplex (or cross-polytope) (m>=0, m<=n). - Sergey Pavlov, 15 Aug 2015

a(n) is the sum of the coefficients of the n-th layer of Pascal's pyramid (a.k.a., Pascal's tetrahedron - see A046816). - Bob Selcoe, Apr 02 2016

Numbers n such that the trinomial x^(2*n) + x^n + 1 is irreducible over GF(2). Of these only the trinomial for n=1 is primitive. - Joerg Arndt, May 16 2016

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, Mar 28 2013.

Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 7

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 268

Milan Janjic, Enumerative Formulae for Some Functions on Finite Sets

Tanya Khovanova, Recursive Sequences

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Eric Weisstein's World of Mathematics, Hanoi Graph, and Sierpiński Sieve Graph

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for linear recurrences with constant coefficients, signature (3).

FORMULA

a(n) = 3^n.

a(0) = 1; a(n) = 3*a(n-1).

G.f.: 1/(1-3*x).

E.g.f.: exp(3*x).

a(n) = n!*Sum_{i + j + k = n, i, j, k >= 0} 1/(i!*j!*k!). - Benoit Cloitre, Nov 01 2002

a(n) = Sum_{k = 0..n} 2^k*binomial(n, k), binomial transform of A000079.

a(n) = A090888(n, 2). - Ross La Haye, Sep 21 2004

a(n) = 2^(2n) - A005061(n). - Ross La Haye, Sep 10 2005

a(n) = A112626(n, 0). - Ross La Haye, Jan 11 2006

Hankel transform of A007854 = [1, 3, 12, 51, 222, 978, 4338, ...]. - Philippe Deléham, Nov 26 2006

a(n) = 2*StirlingS2(n+1,3) + StirlingS2(n+2,2) = 2*(StirlingS2(n+1,3) + StirlingS2(n+1,2)) + 1. - Ross La Haye, Jun 26 2008

a(n) = 2*StirlingS2(n+1, 3) + StirlingS2(n+2, 2) = 2*(StirlingS2(n+1, 3) + StirlingS2(n+1, 2)) + 1. - Ross La Haye, Jun 09 2008

Sum_{n >= 0} 1/a(n) = 3/2. - Gary W. Adamson, Aug 29 2008

If p[i] = fibonacci(2i-2) 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) = det A. - Milan Janjic, May 08 2010

G.f. A(x) = M(x)/(1-M(x))^2, M(x) - o.g.f for Motzkin numbers (A001006). - Vladimir Kruchinin, Aug 18 2010

a(n) = A133494(n+1). - Arkadiusz Wesolowski, Jul 27 2011

2/3 + 3/3^2 + 2/3^3 + 3/3^4 + 2/3^5 + ... = 9/8. [Jolley, Summation of Series, Dover, 1961]

a(n) = Sum{k, 0 <= k <= n} A207543(n, k)*4^(n-k). - Philippe Deléham, Feb 25 2012

a(n) = Sum_{k, 0 <= k <= n} A125185(n,k). - Philippe Deléham, Feb 26 2012

Sum_{n > 0} mobius(n)/a(n) = 0.181995386702633887827... (see A238271). - Alonso del Arte, Aug 09 2012. See also the sodium 3s orbital energy in table V of J. Chem. Phys. 53 (1970) 348.

a(0) = 1, a(1) = 3; for n > 1, a(n) = (k+3)*a(n-1) - 3*k*a(n-2) for all k. - Vincenzo Librandi, Feb 16 2014

a(n) = 1/3 + Sum_{i=0..n} a(i) - a(i-1). - Wesley Ivan Hurt, Jul 04 2014

EXAMPLE

G.f. = 1 + 3*x + 9*x^2 + 27*x^3 + 81*x^4 + 243*x^5 + 729*x^6 + 2187*x^7 + ...

MAPLE

A000244 := n->3^n; [ seq(3^n, n=0..50) ];

A000244:=-1/(-1+3*z); # Simon Plouffe in his 1992 dissertation.

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 0), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=j), j=1..28); # Zerinvary Lajos, Apr 04 2009

MATHEMATICA

Table[3^n, {n, 0, 30}] (* Stefan Steinerberger, Apr 01 2006 *)

3^Range[0, 30] (* Wesley Ivan Hurt, Jul 04 2014 *)

PROG

(PARI) A000244(n) = 3^n \\ Michael B. Porter, Nov 03 2009

(Haskell)

a000244 = (3 ^)  -- Reinhard Zumkeller, Nov 14 2011

a000244_list = iterate (* 3) 1  -- Reinhard Zumkeller, Apr 04 2012

(Maxima) makelist(3^n, n, 0, 30); /* Martin Ettl, Nov 05 2012 */

(MAGMA) [ 3^n : n in [0..30] ]; // Wesley Ivan Hurt, Jul 04 2014

CROSSREFS

a(n) = A092477(n, 2) for n > 0.

a(n) = A159991(n) / A009964(n).

Cf. A100772, A035002. Row sums of A125076 and A153279.

a(n) = A217764(0, n).

Cf. A046816.

Sequence in context: A140429 A141413 * A133494 A050733 A238939 A079846

Adjacent sequences:  A000241 A000242 A000243 * A000245 A000246 A000247

KEYWORD

nonn,nice,easy,core

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 25 04:05 EDT 2016. Contains 275791 sequences.