0,2

2^0 = 1 is the only odd power of 2.

Number of subsets of an n-set.

There are 2^(n-1) compositions (ordered partitions) of n - see for example Riordan. This is the unlabeled analogue of the preferential labelings sequence A000670.

This is also the number of weakly unimodal permutations of 1..n, that is, permutations with exactly one local maximum. E.g., a(5)=16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003. Proof: see next line! See also A087783.

Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26, 2003

a(n+1) = smallest number that is not the sum of any number of (distinct) earlier terms.

Same as Pisot sequences E(1,2), L(1,2), P(1,2), T(1,2). See A008776 for definitions of Pisot sequences.

With initial 1 omitted, same as Pisot sequences E(2,4), L(2,4), P(2,4), T(2,4). - David W. Wilson

Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004

Least deficient or near-perfect numbers (i.e., n such that sigma(n)=A000203(n)=2n-1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number not a power of 2.]

Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n-1) and quasi-perfect numbers (sigma(n) = 2n+1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.

The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.

The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).

The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 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)!). - Thomas Wieder, May 18 2005

a(n+1) = a(n) XOR 3a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005

The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.

The first differences are the sequence itself. - Alexandre Wajnberg & Eric Angelini, Sep 07 2005

a(n) = largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006

Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006

Smallest order of exactly p(n) nonisomorphic Abelian groups, where p(n)=A000041(n). (First occurrence of p(n) in A000688(n).) - Lekraj Beedassy, Jul 11 2006

For n>=1, a(n) is equal to the number of functions f:{1,2...,n}->{1,2} such that for a fixed x in {1,2,...,n} and a fixed y in {1,2]} we have f(x)<>y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008

a(n)= the number of different ways to run up a staircase with n steps, taking steps of sizes 1,2,3,... and r (r<=n), where the order IS important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian, May 21 2008

a(n)=number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008

2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008

a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008

Successive k such that EulerPhi[k]/k = 1/2. - Artur Jasinski, Nov 07 2008

A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n)=A000079 leads to 2,1,8,4,32,16,...=A135520. - Paul Curtz, Jan 05 2009

This is also the (L)-sieve transform of {2,4,6,8,...,2n,...}=A005843. (See A152079 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009

a(n) = a(n-1)-th even natural numbers (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009

For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009

Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009

Catalan transform of A099087. - R. J. Mathar, Jun 29 2009

a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009

Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009

These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009

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

a(n) = the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010

a(n) = A173786(n,n)/2 = A173787(n+1,n). - Reinhard Zumkeller, Feb 28 2010

a(n) is the smallest multiple of a(n-1). - Dominick Cancilla, Aug 09 2010

The powers-of-2 triangle T(n,k), n>=0 and 0<=k<=n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n,0) = A006125(n+1), the first right hand diagonal T(n,n) = A036442(n+1) and the center diagonal T(2*n,n) = A053765(n+1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n+1) = 2*A181175(2*n+1). - Johannes W. Meijer, Oct 10 2010

Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011

Row sums of A152538. - _Gary W. Adamson, Dec 10 2008

A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 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 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011

Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011

The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1,2,3,4}, namely {1}, {2}, {3}, {4}, {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}. Also, note that 2^n=sum(C(n+1,2k-1),k=1..floor(n/2+1/2)). - Dennis P. Walsh, Dec 15 2011

a(n) = number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A07318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012

A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012

A209229(a(n)) = 1. - Reinhard Zumkeller, Mar 07 2012

A001227(a(n)) = 1. - Reinhard Zumkeller, May 01 2012

For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012

First differences of A000225. - Omar E. Pol, Feb 19 2013

This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013

a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013

Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013

More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013

Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013

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

a(1),...,a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013.

Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013

A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.

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

V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)

N. J. A. Sloane, Table of n, 2^n for n = 0..1000

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Anicius Manlius Severinus Boethius, De arithmetica, Book 1, section 9.

Henry Bottomley, Illustration of initial terms

D. Butler, Powers of Two up to 2^222

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

Keneth Adrian P. Dagal and Jose Arnaldo B. Dris, A Criterion for Almost Perfect Numbers in Terms of the Abundancy Index, arXiv:1308.6767v1 [math.NT], Aug 14, 2013 [Jonathan Vos Post, Sep 01 2013]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.

Hermann Gruber, Jonathan Lee and Jeffrey Shallit: Enumerating regular expressions and their languages, arXiv:1204.4982v1 [cs.FL]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 6

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 68

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 72

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 267

Marcus Jaiclin, David DiRico, Christopher O'Sullivan and Stephen Tetreault, Pascal's Triangle Mod 2,3,5

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

R. Ondrejka, Exact values of 2^n, n=1(1)4000, Math. Comp., 23 (1969), 456.

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

G. Villemin's Almanac of Numbers, Puissances de 2

Sage Weil, 1058 powers of two

Eric Weisstein's World of Mathematics, Fractional Part

Eric Weisstein's World of Mathematics, PowerFractional Parts

Eric Weisstein's World of Mathematics, Subset

Eric Weisstein's World of Mathematics, Binomial Sums

Eric Weisstein's World of Mathematics, Binomial Transform

Eric Weisstein's World of Mathematics, Hypercube

Eric Weisstein's World of Mathematics, Least Deficient Number

Eric Weisstein's World of Mathematics, Hailstone Number (Collatz Problem)

Eric Weisstein's World of Mathematics, Erf

Eric Weisstein's World of Mathematics, Abundance

Wikipedia, Almost perfect number

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for sequences related to linear recurrences with constant coefficients, signature (2).

Index to divisibility sequences

a(n) = 2^n.

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

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

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

2^n = Sum_{k=0..n} binomial(n, k).

a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + sum_{k=0..(n-1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004

n such that phi(n) = n/2, for n > 1, where phi is Euler's totient (A000010). - Lekraj Beedassy, Sep 07 2004

This sequence can be generated by the following formula: a(n) = a(n-1) + 2*a(n-2) when n > 2; a(1) = 1, a(2) = 2 - Alex Vinokur (alexvn(AT)barak-online.net), Oct 24 2004

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

This sequence can be generated by a(n+2)=6a(n+1)-8a(n), n=1,2,3,... with a(1)=1, a(2)=2. - Yosu Yurramendi, Aug 06 2008

a(n) = ka(n-1) + (4-2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008

Equals the partition numbers A000041 convolved with A152537. - Gary W. Adamson, Dec 06 2008

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1} delta(l_1,l_2,...,l_i,...,l_n) where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) <> 0 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009

a(0) = 1, a(1)=2; a(n)=a(n-1)^2/a(n-2), n>=2. - Jaume Oliver Lafont, Sep 22 2009

If p[i]=i-1 and if A is 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 02 2010

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

The sum of reciprocals, 1/1+1/2+1/4+1/8+...+1/(2^n)+...=2. - Mohammad K. Azarian, Dec 29 2010

a(n) = 2*A001045(n)+A078008(n) = 3*A001045(n)+(-1)^n. - Paul Barry, Feb 20 2003

a(n) = A118654(n, 2).

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

a(n) = A131577(n) + A011782(n) = A024495(n) + A131708(n) + A024493(n) = A000749(n) + A038503(n) + A038504(n) + A038505(n-1) = A139761(n) + A139748(n) + A139714(n) + A133476(n) + A139398(n). - Paul Curtz, Jul 25 2011

a(n) = row sums of A007318. - Susanne Wienand, Oct 21 2011

a(n) = Hypergeometric([-n],[],-1). - Peter Luschny, Nov 01 2011

G.f.: A(x)=B(x)/x, B(x) satisfies B(B(x))=x/(1-x)^2. - Vladimir Kruchinin, Nov 10 2011

a(n) = Sum_{k, 0<=k<=n} A201730(n,k)*(-1)^k . - Philippe Deléham, Dec 06 2011

2^n = sum(C(n+1,2k-1),k=1..floor(n/2+1/2)). - Dennis P. Walsh, Dec 15 2011

sum_{n>=1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012

E.g.f.: 1+2*x/(U(0)-x) where U(k)=  6*k+1 + x^2/(6*k+3 + x^2/(6*k+5 + x^2/U(k+1) )) ;(continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012

a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013

a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind (A129467). - Mircea Merca, Apr 06 2013

G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013

a(n-1) = sum(t_1+2*t_2+...+n*t_n=n, multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)). - Mircea Merca, Dec 06 2013

a(n) = 5*a(n-1) - 6*a(n-2) for n > 1. - Vincenzo Librandi, Feb 17 2014

There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.

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

with(combstruct); SeqSetU := [S, {S=Sequence(U), U=Set(Z, card >= 1)}, unlabeled]; seq(count(SeqSetU, size=j), j=1..12);

G(x):=exp(x)*cosh(x): f[0]:=G(x): for n from 1 to 54 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=1..34 ); # Zerinvary Lajos, Apr 05 2009

Table[2^n, {n, 0, 50}]

(PARI) a(n)=if(n<0, 0, 2^n)

(PARI) { unimodal(n)=local(x, d, um, umc); umc=0; for (c=0, n!-1, x=numtoperm(n, c); d=0; um=1; for (j=2, n, if (x[j]<x[j-1], d=1); if (x[j]>x[j-1] && d==1, um=0); if (um==0, break)); if (um==1, print(x)); umc+=um); umc }

(PARI) { x=1; for (n=0, 1000, write("b000079.txt", n, " ", x); x+=x); } \\ Harry J. Smith, Apr 26 2009

(Haskell)

a000079 = (2 ^)

a000079_list = iterate (* 2) 1

-- Reinhard Zumkeller, Jan 22 2014, Mar 05 2012, Dec 29 2011

(Maxima) A000079(n):=2^n$ makelist(A000079(n), n, 0, 30); \\ Martin Ettl, Nov 05 2012

(MAGMA) [2^n: n in [0..40]] (* or *) [n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014

Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405.

This is the Hankel transform (see A001906 for the definition) of A000984, A002426, A026375, A026387, A026569, A026585, A026671 and A032351. - John W. Layman, Jul 31 2000

Euler transform of A001037, inverse binomial transform of A000244, binomial transform of A000012.

Complement of A057716.

Boustrophedon transforms: A000734, A000752.

Sequence in context: A120617 A131577 A155559 A171449 A122803 A050732 A138815

Adjacent sequences:  A000076 A000077 A000078 * A000080 A000081 A000082

nonn,core,easy,nice

N. J. A. Sloane

Clarified a comment T. D. Noe, Aug 30 2009

Edited by Daniel Forgues, May 12 2010

approved