A001146 - OEIS A001146 (Formerly M1297 N0497) 50 2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, 340282366920938463463374607431768211456, 115792089237316195423570985008687907853269984665640564039457584007913129639936 ( list ; graph ; refs ; listen ; history ; text ; internal format ) OFFSET COMMENTS Or, write previous term in base 2, read in base 4.

a(1) = 2, a(n) = smallest power of 2 which does not divide the product of all previous terms. Number of truth tables generated by boolean expressions of n variables. - C. Bradford Barber (bradb(AT)shore.net), Dec 27 2005 From Ross Drewe , Feb 13 2008: (Start) Or, number of distinct n-ary operators in a binary logic. The total number of n-ary operators in a k-valued logic is T = k^(k^n), i.e., if S is a set of k elements, there are T ways of mapping an ordered subset of n elements from S to an element of S. Some operators are "degenerate": the operator has arity p, if only p of the n input values influence the output. Therefore the set of operators can be partitioned into n+1 disjoint subsets representing arities from 0 to n. For n = 2, k = 2 gives the familiar Boolean operators or functions, C = F(A,B).

There are 2^2^2 = 16 operators, composed of: arity 0: 2 operators (C = 0 or 1), arity 1: 4 operators (C = A, B, not(A), not(B)), arity 2: 10 operators (including well-known pairs AND/NAND, OR/NOR, XOR/EQ). (End) From José María Grau Ribas , Jan 19 2012: (Start) Or, numbers that can be formed using the number 2, the power operator (^), and parenthesis. (End) [The paper by Guy and Selfridge (see also A003018 ) shows that this is the same as the current sequence. - N. J. A. Sloane , Jan 21 2012] a(n) is the highest value k such that A173419 (k) = n+1.

- Charles R Greathouse IV , Oct 03 2012 Let b(0) = 8 and b(n+1) = the smallest number not in the sequence such that b(n+1) - Product_{i=0..n} b(i) divides b(n+1)*Product_{i=0..n} b(i). Then b(n) = a(n) for n > 0. - Derek Orr , Jan 15 2015 Twice the number of distinct minimal toss sequences of a coin to obtain all sequences of length n, which is 2^(2^n-1). This derives from the 2^n ways to cut each of the De Bruijn sequences B(2,n). - Maurizio De Leo , Feb 28 2015 I conjecture that { a(n) ; n>1 } are the numbers such that n^4-1 divides 2^n-1, intersection of A247219 and A247165 . - M. F. Hasler , Jul 25 2015 REFERENCES D. E. Knuth, The Art of Computer Programming, Vol.

4A, Section 7.1.1, p. 79. 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 The powers of 2 The powers of 2 Each term is: Two to the power of the number Known as: The powers of 2 The first 50 terms (starting from n=0) are: 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 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1099511627776 2199023255552 4398046511104 8796093022208 17592186044416 35184372088832 70368744177664 140737488355328 281474976710656 562949953421312 Example To get the value for n=11: Raise two to this power, giving 20

48.

So the result is 2048. A000079 - OEIS A000079 Powers of 2: a(n) = 2^n.

(Formerly M1129 N0432) 1773 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, 42949

67296, 8589934592 ( list ; graph ; refs ; listen ; history ; text ; internal format ) OFFSET 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 analog of the preferential labelings sequence A000670 . 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 . 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 that is 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, 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 and 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 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 A152009 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 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 A007318 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 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 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 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 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 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 finite and full. - Derek Orr , Jul 03 2014 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 Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht , Aug 14 2014 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 a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath , Dec 11 2014 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 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 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 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 Subsequence of A028982 (the squares or twice squares sequence). - Timothy L.

Tiffin , Jul 18 2016 a(0) = 1; a(n) = 2*a(n-1). G.f.: 1/(1-2*x). E.g.f.: exp(2*x). a(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 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 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 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 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..=n} A201730 (n,k)*(-1)^k. - Philippe Deléham , Dec 06 2011 2^n = Sum_{k=1..floor(n/2 + 1/2)} C(n+1,2k-1). - 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 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

Question: What is the next number in this sequence: 4; 16; 256; 65,536?
Answer: 4,294,967,296