

A000079


Powers of 2: a(n) = 2^n.
(Formerly M1129 N0432)


1359



1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

2^0 = 1 is the only odd power of 2.
Number of subsets of an nset.
There are 2^(n1) 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^(n1) 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 nearperfect numbers (i.e., n such that sigma(n)=A000203(n)=2n1).  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.]
Almostperfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "nearperfect numbers" refer to both almostperfect numbers (sigma(n) = 2n1) and quasiperfect numbers (sigma(n) = 2n+1)? There are no known quasiperfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the nth 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 ith partition of n, d(i) = the number of different parts of the ith partition of n, m(i,j) = multiplicity of the jth part of the ith 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 nelement set that are both symmetric and antisymmetric. Also the number of binary relations on an nelement 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 nelement 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^(n1) 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(n1)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 ncube.  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.  JuriStepan Gerasimov, Oct 10 2009
These are the 2smooth 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(n1).  Dominick Cancilla, Aug 09 2010
The powersof2 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.  JuriStepan 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 pcolored compositions of n. For n>=1, a(n) equals the number of 2colored compositions of n such that no adjacent parts have the same color.  Milan Janjic, Nov 17 2011
Equals A001405 convolved with its rightshifted 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 oddsized subsets of an n+1set. For example, there are 2^3 oddsized 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,2k1),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(n2) 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 nth cyclotomic polynomial has a root mod 2; numbers n such that the nth cyclotomic polynomial has an even number of odd coefficients.  Eric M. Schmidt, Jul 31 2013
More is known now about nonpowerof2 "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 base2 expansion has exactly one bit set to 1, and thus has base2 sum of digits equal to one.  Stanislav Sykora, Nov 29 2013
A072219(a(n)) = 1.  Reinhard Zumkeller, Feb 20 2014


REFERENCES

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. 1217. 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. 2428, 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), 415. (Russian)


LINKS

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 kBinomial 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 partitioncounting sequences
Index entries for sequences related to linear recurrences with constant coefficients, signature (2).
Index to divisibility sequences


FORMULA

a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n1).
G.f.: 1/(12*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..(n1)} 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(n1) + 2*a(n2) when n > 2; a(1) = 1, a(2) = 2  Alex Vinokur (alexvn(AT)barakonline.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(n1) + (42k)a(n2) 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}^{ni}...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(n1)^2/a(n2), n>=2.  Jaume Oliver Lafont, Sep 22 2009
If p[i]=i1 and if A is Hessenberg matrix of order n defined by: A[i,j]=p[ji+1], (i<=j), A[i,j]=1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n1)=det A.  Milan Janjic, May 02 2010
If p[i]=fibonacci(i2) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[ji+1], (i<=j), A[i,j]=1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=2, a(n2)=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(n1) = 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/(1x)^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,2k1),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, 3step).  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 LegendreStirling 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(n1) = 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(n1)  6*a(n2) for n > 1.  Vincenzo Librandi, Feb 17 2014


EXAMPLE

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


MAPLE

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[n1], x) od: x:=0: seq(f[n], n=1..34 ); # Zerinvary Lajos, Apr 05 2009


MATHEMATICA

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


PROG

(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[j1], d=1); if (x[j]>x[j1] && 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(n1)6*Self(n2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014


CROSSREFS

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


KEYWORD

nonn,core,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Clarified a comment T. D. Noe, Aug 30 2009
Edited by Daniel Forgues, May 12 2010


STATUS

approved



