%I M1129 N0432 #831 Jul 28 2024 09:17:37

%S 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,

%T 131072,262144,524288,1048576,2097152,4194304,8388608,16777216,

%U 33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592

%N Powers of 2: a(n) = 2^n.

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

%C Number of subsets of an n-set.

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

%C This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 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.]

%C 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

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

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

%C With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - _David W. Wilson_

%C Not the sum of two or more consecutive numbers. - _Lekraj Beedassy_, May 14 2004

%C 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 that is not a power of 2.]

%C 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.

%C 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.

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

%C The only hailstone sequence which doesn't rebound (except "on the ground"). - _Alexandre Wajnberg_, Jan 29 2005

%C With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - _Thomas Wieder_, May 18 2005

%C 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.

%C The first differences are the sequence itself. - _Alexandre Wajnberg_ and _Eric Angelini_, Sep 07 2005

%C a(n) is the largest number with shortest addition chain involving n additions. - _David W. Wilson_, Apr 23 2006

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

%C 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

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

%C a(n) is 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

%C a(n) is the 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

%C 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

%C 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

%C Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - _Artur Jasinski_, Nov 07 2008

%C 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

%C This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - _John W. Layman_, Jan 23 2009

%C a(n) = a(n-1)-th even natural number (A005843) for n > 1. - _Jaroslav Krizek_, Apr 25 2009

%C 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

%C 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

%C Catalan transform of A099087. - _R. J. Mathar_, Jun 29 2009

%C 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

%C Or, phi(n) is equal to the number of perfect partitions of n. - _Juri-Stepan Gerasimov_, Oct 10 2009

%C These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - _Michael B. Porter_, Oct 04 2009

%C A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - _Reinhard Zumkeller_, Feb 08 2010

%C a(n) is 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

%C a(n) is the smallest proper multiple of a(n-1). - _Dominick Cancilla_, Aug 09 2010

%C 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

%C Records in the number of prime factors. - _Juri-Stepan Gerasimov_, Mar 12 2011

%C Row sums of A152538. - _Gary W. Adamson_, Dec 10 2008

%C A078719(a(n)) = 1; A006667(a(n)) = 0. - _Reinhard Zumkeller_, Oct 08 2011

%C 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

%C 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

%C 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_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - _Dennis P. Walsh_, Dec 15 2011

%C a(n) is the 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 A007318 and A047999). (The result of putting together A001316 and A000120.) - _Marcus Jaiclin_, Jan 31 2012

%C A204455(k) = 1 if and only if k is in this sequence. - _Wolfdieter Lang_, Feb 04 2012

%C 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

%C First differences of A000225. - _Omar E. Pol_, Feb 19 2013

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

%C 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

%C 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

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

%C Number of symmetric Ferrers diagrams that fit into an n X n box. - _Graham H. Hawkes_, Oct 18 2013

%C Numbers n such that sigma(2n) = 2n + sigma(n). - _Jahangeer Kholdi_, Nov 23 2013

%C 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

%C 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

%C A072219(a(n)) = 1. - _Reinhard Zumkeller_, Feb 20 2014

%C a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - _Derek Orr_, May 22 2014

%C If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - _Vincenzo Librandi_, Jun 09 2014

%C The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - _Derek Orr_, Jun 14 2014

%C The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - _Derek Orr_, Jul 03 2014

%C a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - _Manda Riehl_, Aug 05 2014

%C Numbers n such that sigma(n) = sigma(2n) - phi(4n). - _Farideh Firoozbakht_, Aug 14 2014

%C This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - _Thomas Ordowski_, Sep 23 2014

%C a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - _David Neil McGrath_, Dec 11 2014

%C a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - _David Neil McGrath_, Jan 01 2015

%C b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - _Derek Orr_, Jan 15 2015

%C a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - _Ran Pan_, Apr 17 2015

%C a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - _Charles R Greathouse IV_, Sep 03 2015

%C Subsequence of A028982 (the squares or twice squares sequence). - _Timothy L. Tiffin_, Jul 18 2016

%C A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - _Juri-Stepan Gerasimov_, Aug 16 2016

%C Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - _Noam Zeilberger_, Dec 11 2016

%C Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - _Anton Zakharov_, Dec 31 2016

%C Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - _N. J. A. Sloane_, Feb 07 2017

%C Also the number of independent vertex sets and vertex covers in the n-empty graph. - _Eric W. Weisstein_, Sep 21 2017

%C Also the number of maximum cliques in the n-halved cube graph for n > 4. - _Eric W. Weisstein_, Dec 04 2017

%C Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - _Nick Mayers_, Jun 25 2018

%C The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - _Jianing Song_, Jun 27 2018

%C k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - _Tony Foster III_, May 12 2019

%C Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - _M. Farrokhi D. G._, Jan 03 2020

%C a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - _Enrique Navarrete_, Nov 21 2020

%C a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - _Yuchun Ji_, Feb 26 2021

%C For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - _Greg Dresden_ and Bora Bursalı, Aug 31 2023

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

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

%D Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.

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

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

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

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

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

%H N. J. A. Sloane, <a href="/A000079/b000079.txt">Table of n, 2^n for n = 0..1000</a>

%H Milton Abramowitz and Irene A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/2003.11533">Wilf equivalences between vincular patterns in inversion sequences</a>, arXiv:2003.11533 [math.CO], 2020.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Jonathan Beagley and Lara Pudwell, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Pudwell/pudwell13.html">Colorful Tilings and Permutations</a>, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.

%H Arno Berger and Theodore P. Hill, <a href="http://www.ams.org/publications/journals/notices/201702/rnoti-p132.pdf">What is Benford's Law?</a>, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.

%H Tobias Boege and Thomas Kahle, <a href="https://arxiv.org/abs/1902.11260">Construction Methods for Gaussoids</a>, arXiv:1902.11260 [math.CO], 2019.

%H Anicius Manlius Severinus Boethius, <a href="http://www.e-codices.unifr.ch/en/vad/0296/6r/medium">De arithmetica</a>, Book 1, section 9.

%H Henry Bottomley, <a href="/A000079/a000079.gif">Illustration of initial terms</a>

%H Douglas Butler, <a href="https://web.archive.org/web/20191202164323/http://www.tsm-resources.com:80/alists/pow2.html">Powers of Two up to 2^222</a>

%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Peter J. Cameron, <a href="https://cameroncounts.wordpress.com/2017/05/15/notes-on-counting/">Notes on Counting</a>, Peter Cameron's Blog, 15/05/2017.

%H CDLI, <a href="http://cdli.ucla.edu/search/search_results.php?SearchMode=Text&amp;ObjectID=P390441">M 08613</a>.

%H Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.

%H V. Coll, M. Hyatt, C. Magnant, and H. Wang, <a href="http://dx.doi.org/10.4172/1736-4337.1000227">Meander graphs and Frobenius seaweed Lie algebras II</a>, Journal of Generalized Lie Theory and Applications 9 (1) (2015) 227.

%H M. Coons and H. Winning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Coons/coons2.html">Powers of Two Modulo Powers of Three</a>, J. Int. Seq. 18 (2015) # 15.6.1.

%H Keneth Adrian P. Dagal and Jose Arnaldo B. Dris, <a href="http://arxiv.org/abs/1308.6767">A Criterion for Almost Perfect Numbers in Terms of the Abundancy Index</a>, arXiv:1308.6767v1 [math.NT], Aug 14 2013.

%H V. Dergachev and A. Kirillov, <a href="https://www.emis.de/journals/JLT/vol.10_no.2/6.html">Index of Lie algebras of seaweed type</a>, J. Lie Theory 10 (2) (2000) 331-343.

%H Persi Diaconis, <a href="https://doi.org/10.1214/aop/1176995891">The distribution of leading digits and uniform distribution mod 1</a>, Ann. Probability, 5, 1977, 72--81.

%H Kenneth Edwards and Michael A. Allen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Allen/edwards2.html">New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile</a>, J. Int. Seq. 24 (2021) Article 21.3.8.

%H David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 18

%H Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.

%H Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors of oligomorphic permutation groups</a>, J. Integer Seqs., Vol. 6, 2003.

%H Hermann Gruber, Jonathan Lee and Jeffrey Shallit, <a href="http://arxiv.org/abs/1204.4982">Enumerating regular expressions and their languages</a>, arXiv:1204.4982v1 [cs.FL], 2012.

%H R. K. Guy, <a href="/A000346/a000346.pdf">Letter to N. J. A. Sloane</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=6">Encyclopedia of Combinatorial Structures 6</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=68">Encyclopedia of Combinatorial Structures 68</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=72">Encyclopedia of Combinatorial Structures 72</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=267">Encyclopedia of Combinatorial Structures 267</a>

%H Marcus Jaiclin, et al. <a href="https://web.archive.org/web/20170823000349/http://pyrrho.wsc.ma.edu/math/faculty/jaiclin/writings/research/pascals_triangle/">Pascal's Triangle, Mod 2,3,5</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Enumerative Formulas for Some Functions on Finite Sets</a>

%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.

%H P. A. MacMahon, <a href="http://www.jstor.org/stable/90632">Memoir on the Theory of the Compositions of Numbers</a>, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.

%H Victor Meally, <a href="/A002868/a002868.pdf">Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.</a>

%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.

%H R. Ondrejka, <a href="http://www.jstor.org/stable/2004456">Exact values of 2^n, n=1(1)4000</a>, Math. Comp., 23 (1969), 456.

%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

%H Robert Price, <a href="/A000079/a000079.txt">Comments on A000079 concerning Elementary Cellular Automata</a>, Feb 26 2016.

%H S. Saito, T. Tanaka and N. Wakabayashi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Saito/saito22.html">Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values </a>, J. Int. Seq. 14 (2011) # 11.2.4, Table 1.

%H Michael Z. Spivey and Laura L. Steil, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

%H J. Tanton, <a href="http://www.jstor.org/stable/25678324">A Dozen Questions about the Powers of Two</a>, Math Horizons, Vol. 8, pp. 5-10, September 2001.

%H G. Villemin's Almanac of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Nombre/Puiss2.htm">Puissances de 2</a>

%H Sage Weil, <a href="https://web.archive.org/web/20090206092940/http://newdream.net:80/~sage/old/numbers/pow2.htm">1058 powers of two</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Abundance.html">Abundance</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinomialSums.html">Binomial Sums</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinomialTransform.html">Binomial Transform</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Hailstone Number (Collatz Problem)</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Composition.html">Composition</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EmptyGraph.html">Empty Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Erf.html">Erf</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FractionalPart.html">Fractional Part</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HalvedCubeGraph.html">Halved Cube Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Hypercube.html">Hypercube</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LeastDeficientNumber.html">Least Deficient Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumClique.html">Maximum Clique</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PowerFractionalParts.html">PowerFractional Parts</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Subset.html">Subset</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Almost_perfect_number">Almost perfect number</a>

%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>

%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (2).

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

%F a(n) = 2^n.

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

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

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

%F a(n)= Sum_{k = 0..n} binomial(n, k).

%F 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

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

%F a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - _Philippe Deléham_, Jun 19 2005

%F a(n) = StirlingS2(n + 1, 2) + 1. - _Ross La Haye_, Jan 09 2008

%F a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - _Yosu Yurramendi_, Aug 06 2008

%F 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

%F 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

%F a(0) = 1, a(1) = 2; a(n) = a(n-1)^2/a(n-2), n >= 2. - _Jaume Oliver Lafont_, Sep 22 2009

%F a(n) = A173786(n, n)/2 = A173787(n + 1, n). - _Reinhard Zumkeller_, Feb 28 2010

%F If p[i] = i - 1 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 02 2010

%F 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

%F The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - _Mohammad K. Azarian_, Dec 29 2010

%F a(n) = 2*A001045(n) + A078008(n) = 3*A001045(n) + (-1)^n. - _Paul Barry_, Feb 20 2003

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

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

%F a(n) = A131577(n) + A011782(n) = A024495(n) + A131708(n) + A024493(n) = A000749(n) + A038503(n) + A038504(n) + A038505(n) = A139761(n) + A139748(n) + A139714(n) + A133476(n) + A139398(n). - _Paul Curtz_, Jul 25 2011

%F a(n) = row sums of A007318. - _Susanne Wienand_, Oct 21 2011

%F a(n) = Hypergeometric([-n], [], -1). - _Peter Luschny_, Nov 01 2011

%F G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - _Vladimir Kruchinin_, Nov 10 2011

%F a(n) = Sum_{k = 0..n} A201730(n, k)*(-1)^k. - _Philippe Deléham_, Dec 06 2011

%F 2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - _Dennis P. Walsh_, Dec 15 2011

%F A209229(a(n)) = 1. - _Reinhard Zumkeller_, Mar 07 2012

%F A001227(a(n)) = 1. - _Reinhard Zumkeller_, May 01 2012

%F Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - _R. J. Mathar_, Aug 12 2012

%F 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

%F 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

%F 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

%F 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

%F 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

%F Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - _David Neil McGrath_, Jan 01 2015

%F a(n) = A000005(A002110(n)). - _Ivan N. Ianakiev_, May 23 2016

%F From _Ilya Gutkovskiy_, Jul 18 2016: (Start)

%F Exponential convolution of A000012 with themselves.

%F a(n) = Sum_{k=0..n} A011782(k).

%F Sum_{n>=0} a(n)/n! = exp(2) = A072334.

%F Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End)

%F G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - _Gary W. Adamson_, Sep 13 2016

%F a(n) = A000045(n + 1) + A000045(n) + Sum_{k = 0..n - 2} A000045(k + 1)*2^(n - 2 - k). - _Melvin Peralta_, Dec 22 2017

%F a(n) = 7*A077020(n)^2 + A077021(n)^2, n>=3. - _Ralf Steiner_, Aug 08 2021

%F a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - _Michael A. Allen_, Jan 12 2022

%F Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - _Stefano Spezia_, May 17 2023

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

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

%p isA000079 := proc(n)

%p local fs;

%p fs := numtheory[factorset](n) ;

%p if n = 1 then

%p true ;

%p elif nops(fs) <> 1 then

%p false;

%p elif op(1,fs) = 2 then

%p true;

%p else

%p false ;

%p end if;

%p end proc: # _R. J. Mathar_, Jan 09 2017

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

%t 2^Range[0, 50] (* _Wesley Ivan Hurt_, Jun 14 2014 *)

%t LinearRecurrence[{2}, {2}, {0, 20}] (* _Eric W. Weisstein_, Sep 21 2017 *)

%t CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 21 2017 *)

%t NestList[2# &, 1, 40] (* _Harvey P. Dale_, Oct 07 2019 *)

%o (PARI) A000079(n)=2^n \\ Edited by _M. F. Hasler_, Aug 27 2014

%o (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

%o (PARI) x=1; for (n=0, 1000, write("b000079.txt", n, " ", x); x+=x); \\ _Harry J. Smith_, Apr 26 2009

%o (Haskell)

%o a000079 = (2 ^)

%o a000079_list = iterate (* 2) 1

%o -- _Reinhard Zumkeller_, Jan 22 2014, Mar 05 2012, Dec 29 2011

%o (Maxima) A000079(n):=2^n$ makelist(A000079(n),n,0,30); /* _Martin Ettl_, Nov 05 2012 */

%o (Magma) [2^n: n in [0..40]] // _Vincenzo Librandi_, Feb 17 2014

%o (Magma) [n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Feb 17 2014

%o (Scheme) (define (A000079 n) (expt 2 n)) ;; _Antti Karttunen_, Mar 21 2017

%o (Scala) (List.fill(20)(2: BigInt)).scanLeft(1: BigInt)(_ * _) // _Alonso del Arte_, Jan 16 2020

%o (Python)

%o def a(n): return 1<<n

%o print([a(n) for n in range(34)]) # _Michael S. Branicky_, Jul 28 2022

%Y Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021.

%Y 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

%Y Euler transform of A001037, A209406 (multisets), inverse binomial transform of A000244, binomial transform of A000012.

%Y Complement of A057716.

%Y Boustrophedon transforms: A000734, A000752.

%Y Range of values of A006519, A007875, A011782, A030001, A034444, A037445, A053644, and A054243.

%Y Cf. A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (sum of 2, ..., 9 distinct powers of 2).

%Y Cf. A090129.

%Y The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).

%K nonn,core,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E Clarified a comment _T. D. Noe_, Aug 30 2009

%E Edited by _Daniel Forgues_, May 12 2010

%E Incorrect comment deleted by _Matthew Vandermast_, May 17 2014

%E Comment corrected to match offset by _Geoffrey Critzer_, Nov 28 2014