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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000225 a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)
(Formerly M2655 N1059)
875

%I M2655 N1059

%S 0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,

%T 131071,262143,524287,1048575,2097151,4194303,8388607,16777215,

%U 33554431,67108863,134217727,268435455,536870911,1073741823,2147483647,4294967295

%N a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

%C This is the Gaussian binomial coefficient [n,1] for q=2.

%C Number of rank-1 matroids over S_n.

%C Numbers n such that central binomial coefficient is odd: A001405(A000225(n)) mod 2 = 1. - _Labos Elemer_, Mar 12 2003

%C This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922.

%C Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e., three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one. - Xavier Acloque, Oct 18 2003

%C a(0) = 0, a(1) = 1; a(n) = smallest number such that a(n)-a(m) == 0 (mod (n-m+1)), for all m. - _Amarnath Murthy_, Oct 23 2003

%C Binomial transform of [1, 1/2, 1/3, ...] = [1/1, 3/2, 7/3, ...]; (2^n - 1)/n, n=1,2,3, ... - _Gary W. Adamson_, Apr 28 2005

%C Numbers whose binary representation is 111...1. E.g., the 7th term is (2^7) - 1 = 127 = 1111111 (in base 2). - _Alexandre Wajnberg_, Jun 08 2005

%C a(n) = A099393(n-1) - A020522(n-1) for n > 0. - _Reinhard Zumkeller_, Feb 07 2006

%C Numbers n for which the expression 2^n/(n+1) is an integer. - _Paolo P. Lava_, May 12 2006

%C Number of nonempty subsets of a set with n elements. - _Michael Somos_, Sep 03 2006

%C For n >= 2, a(n) is the least Fibonacci n-step number that is not a power of 2. - _Rick L. Shepherd_, Nov 19 2007

%C Let P(A) be the power set of an n-element set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which either x is a subset of y or y is a subset of x. - _Ross La Haye_, Jan 10 2008

%C A simpler way to state this is that it is the number of pairs (x,y) where at least one of x and y is the empty set. - _Franklin T. Adams-Watters_, Oct 28 2011

%C 2^n-1 is the sum of the elements in a Pascal triangle of depth n. - Brian Lewis (bsl04(AT)uark.edu), Feb 26 2008

%C Sequence generalized : a(n)=(A^n -1)/(A-1), n>=1, A integer >=2. This sequence has A=2; A003462 has A=3; A002450 has A=4; A003463 has A=5; A003464 has A=6; A023000 has A=7; A023001 has A=8; A002452 has A=9; A002275 has A=10; A016123 has A=11; A016125 has A=12; A091030 has A=13; A135519 has A=14; A135518 has A=15; A131865 has A=16; A091045 has A=17; A064108 has A=20. - _Ctibor O. Zizka_, Mar 03 2008

%C a(n) is also a Mersenne prime A000668 when n is a prime number in A000043. - _Omar E. Pol_, Aug 31 2008

%C a(n) is also a Mersenne number A001348 when n is prime. - _Omar E. Pol_, Sep 05 2008

%C With offset 1, = row sums of triangle A144081; and INVERT transform of A009545 starting with offset 1; where A009545 = expansion of sin(x)*exp(x). - _Gary W. Adamson_, Sep 10 2008

%C Numbers n such that A000120(n)/A070939(n) = 1. - _Ctibor O. Zizka_, Oct 15 2008

%C a(n) = A024036(n)/A000051(n). - _Reinhard Zumkeller_, Feb 14 2009

%C For n > 0, sequence is equal to partial sums of A000079 ; a(n) = A000203(A000079(n-1)). - _Lekraj Beedassy_, May 02 2009

%C Starting with offset 1 = the Jacobsthal sequence, A001045, (1, 1, 3, 5, 11, 21, ...) convolved with (1, 2, 2, 2, ...). - _Gary W. Adamson_, May 23 2009

%C Numbers n such that n=2*phi(n+1)-1. - _Farideh Firoozbakht_, Jul 23 2009

%C a(n) = (a(n-1)+1) th odd numbers = A005408(a(n-1)) for n >= 1. - _Jaroslav Krizek_, Sep 11 2009

%C a(n) = sum of previous terms + n = (Sum_{i=0..n-1} a(i)) + n for n >= 1. Partial sums of a(n) for n >= 0 are A000295(n+1). Partial sums of a(n) for n >= 1 are A000295(n+1) and A130103(n+1). a(n) = A006127(n) - (n+1). - _Jaroslav Krizek_, Oct 16 2009

%C If n is even a(n) mod 3 = 0. This follows from the congruences 2^(2k) - 1 ~ 2*2* ... *2 - 1 ~ 4*4* ... *4 - 1 ~ 1*1* ... *1 - 1 ~ 0 (mod 3). (Note that 2*2* ... *2 has an even number of terms.) - _Washington Bomfim_, Oct 31 2009

%C Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - _Milan Janjic_, Jan 26 2010

%C a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). - _Reinhard Zumkeller_, Feb 28 2010

%C For n>0: A179857(a(n))=A024036(n) and A179857(m)<A024036(n) for m<a(n). - _Reinhard Zumkeller_, Jul 31 2010

%C This is the sequence A(0,1;1,2;2) = A(0,1;3,-2;0) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - _Wolfdieter Lang_, Oct 18 2010

%C a(n)=S(n+1,2), a Stirling number of the second kind. See the example below. - _Dennis P. Walsh_, Mar 29 2011

%C Entries of row a(n) in Pascal's triangle are all odd, while entries of row a(n)-1 have alternating parities of the form odd, even, odd, even, ..., odd.

%C Define the bar operation as an operation on signed permutations that flips the sign of each entry. Then a(n+1) is the number of signed permutations of length 2n that are equal to the bar of their reverse-complements and avoid the set of patterns {(-2,-1), (-1,+2), (+2,+1)}. (See the Hardt and Troyka reference.) - _Justin M. Troyka_, Aug 13 2011

%C A159780(a(n)) = n and A159780(m) < n for m < a(n). - _Reinhard Zumkeller_, Oct 21 2011

%C This sequence is also the number of proper subsets of a set with n elements. - _Mohammad K. Azarian_, Oct 27 2011

%C a(n) is the number k such that the number of iterations of the map k -> (3k +1)/2 == 1 (mod 2) until reaching (3k +1)/2 == 0 (mod 2) equals n. (see the Collatz problem). - _Michel Lagneau_, Jan 18 2012

%C For integers a, b, denote by a<+>b the least c >= a, such that Hd(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then a(n+1)=a(n)<+>1. Thus this sequence is the Hamming analog of nonnegative integers. - _Vladimir Shevelev_, Feb 13 2012

%C A036987(a(n)) = 1. - _Reinhard Zumkeller_, Mar 06 2012

%C a(n+1) = A044432(n) + A182028(n). - _Reinhard Zumkeller_, Apr 07 2012

%C Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... apparently A007733. - _R. J. Mathar_, Aug 10 2012

%C Start with n. Each n generates a sublist {n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Take the sum of all. E.g., 3->{2,1} and 2->{1}, so a(3)=3+2+1+1=7. - _Jon Perry_, Sep 02 2012

%C This is the Lucas U(P=3,Q=2) sequence. - _R. J. Mathar_, Oct 24 2012

%C a(n+1) = A001317(n) + A219843(n); A219843(a(n)) = 0. - _Reinhard Zumkeller_, Nov 30 2012

%C The Mersenne numbers >=7 are all Brazilian numbers, as repunits in base two. See Proposition 1 & 5.2 in Links: "Les nombres brésiliens". - _Bernard Schott_, Dec 26 2012

%C Number of line segments after n-th stage in the H tree. - _Omar E. Pol_, Feb 16 2013

%C Row sums of triangle in A162741. - _Reinhard Zumkeller_, Jul 16 2013

%C a(n) is the highest power of 2 such that 2^a(n) divides (2^n)!. - _Ivan N. Ianakiev_, Aug 17 2013

%C In computer programming, these are the only unsigned numbers such that k&(k+1)=0, where & is the bitwise AND operator and numbers are expressed in binary. - _Stanislav Sykora_, Nov 29 2013

%C Minimal number of moves needed to interchange n frogs in the frogs problem (see for example the NRICH 1246 link or the Britton link below). - _N. J. A. Sloane_, Jan 04 2014

%C a(n) != 4 (mod 5); a(n) != 10 (mod 11); a(n) != 2, 4, 5, 6 (mod 7). - _Carmine Suriano_, Apr 06 2014

%C After 0, antidiagonal sums of the array formed by partial sums of integers (1, 2, 3, 4, ...). - _Luciano Ancora_, Apr 24 2015

%C a(n+1) equals the number of ternary words of length n avoiding 01,02. - _Milan Janjic_, Dec 16 2015

%C With offset 0 and another initial 0, the n-th term of 0, 0, 1, 3, 7, 15, ... is the number of commas required in the fully-expanded von Neumann definition of the ordinal number n. For example, 4 := {0, 1, 2, 3} := {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}, which uses seven commas. Also, for n>0, a(n) is the total number of symbols required in the fully-expanded von Neumann definition of ordinal n - 1, where a single symbol (as usual) is always used to represent the empty set and spaces are ignored. E.g., a(5) = 31, the total such symbols for the ordinal 4. - _Rick L. Shepherd_, May 07 2016

%C With the quantum integers defined by [n+1]_q = (q^(n+1) - q^(-n-1)) / (q - q^(-1)), the Mersenne numbers are a(n+1) = q^n [n+1]_q with q = sqrt(2), whereas the signed Jacobsthal numbers A001045 are given by q = i * sqrt(2) for i^2 = -1. Cf. A239473. - _Tom Copeland_, Sep 05 2016

%C For n>1: numbers n such that n - 1 divides sigma(n + 1). - _Juri-Stepan Gerasimov_, Oct 08 2016

%C This is also the second column of the Stirling2 triangle A008277 (see also A048993). - _Wolfdieter Lang_, Feb 21 2017

%C Except for the initial terms, the decimal representation of the x-axis of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 659", "Rule 721" and "Rule 734", based on the 5-celled von Neumann neighborhood initialized with a single on cell. - _Robert Price_, Mar 14 2017

%C a(n), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving partial injective mappings on a set with n elements. - _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017

%D P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.

%D Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.

%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 D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", pp. 112-3, Penguin Books 1987.

%D K. Zsigmondy, Zur Theorie der Potenreste, Monatsh. Math., 3 (1892), 265-284.

%H Franklin T. Adams-Watters, <a href="/A000225/b000225.txt">Table of n, a(n) for n = 0..1000</a>

%H Omran Ahmadi, Robert Granger, <a href="https://arxiv.org/abs/1104.3882">An efficient deterministic test for Kloosterman sum zeros</a>, arXiv:1104.3882 [math.NT], 2011-2012. See 1st and 2nd column of Table 1 p. 9.

%H Anonymous, <a href="http://www.geider.net/eng/math/hanoi.htm">The Tower of Hanoi</a>

%H M. Baake, F. Gahler and U. Grimm, <a href="http://arxiv.org/abs/1211.5466">Examples of substitution systems and their factors</a>, arXiv:1211.5466 [math.DS], 2012-2013.

%H Michael Baake, Franz Gähler, and Uwe Grimm, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Baake/baake3.html">Examples of Substitution Systems and Their Factors</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.

%H J.-L. Baril, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p178">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.

%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 J. Bernheiden, <a href="http://www.mathe-schule.de/download/pdf/Primzahl/Mersenne.pdf">Mersenne Numbers (Text in German)</a>

%H Michael Boardman, <a href="http://www.jstor.org/stable/3219201">The Egg-Drop Numbers</a>, Mathematics Magazine, 77 (2004), 368-372.

%H R. P. Brent and H. J. J. te Riele, <a href="http://persistent-identifier.org/?identifier=urn:nbn:nl:ui:18-5423">Factorizations of a^n +- 1, 13 <= a < 100</a>, CWI Report 9212, 1992.

%H R. P. Brent, P. L. Montgomery and H. J. J. te Riele, <a href="http://citeseer.ifi.unizh.ch/correct/32644">Factorizations of a^n +- 1, 13 <= a < 100: Update 2</a>

%H R. P. Brent, P. L. Montgomery and H. J. J. te Riele, <a href="http://citeseer.ifi.unizh.ch/correct/467051">Factorizations Of Cunningham Numbers With Bases 13 To 99. Millennium Edition</a>

%H R. P. Brent, P. L. Montgomery and H. J. J. te Riele, <a href="http://wwwmaths.anu.edu.au/~brent/pub/pub200.html">Factorizations of Cunningham numbers with bases 13 to 99: Millennium edition</a>

%H R. P. Brent and H. J. J. te Riele, <a href="http://wwwmaths.anu.edu.au/~brent/pub/pub134.html">Factorizations of a^n +- 1, 13 <= a < 100</a>

%H John Brillhart et al., <a href="http://www.ams.org/online_bks/conm22">Cunningham Project</a> [Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers]

%H Jill Britton, <a href="http://britton.disted.camosun.bc.ca/hanoi.swf">The Tower of Hanoi</a>

%H Jill Britton, <a href="http://britton.disted.camosun.bc.ca/frog_puzzle.htm">The Frog Puzzle</a>

%H C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/page.php?sort=MersenneNumber">Mersenne number</a>

%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

%H P. 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 P. Catarino, H. Campos, P. Vasco, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_46_from37to53.pdf">On the Mersenne sequence</a>, Annales Mathematicae et Informaticae, 46 (2016) pp. 37-53.

%H W. M. B. Dukes, <a href="http://arXiv.org/abs/math.CO/0411557">On the number of matroids on a finite set</a>, arXiv:math/0411557 [math.CO], 2004.

%H James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]

%H W. Edgington, <a href="http://www.garlic.com/~wedgingt/mersenne.htm">Mersenne Page</a>

%H T. Eveilleau, <a href="http://perso.orange.fr/therese.eveilleau/pages/jeux_mat/textes/hanoi.html">Animated solution to the Tower of Hanoi problem</a>

%H G. Everest et al., <a href="http://www.jstor.org/stable/27642221">Primes generated by recurrence sequences</a>, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.

%H G. Everest, S. Stevens, D. Tamsett and T. Ward, <a href="http://arXiv.org/abs/math.NT/0412079">Primitive divisors of quadratic polynomial sequences</a>, arXiv:math/0412079 [math.NT], 2004-2006.

%H G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ward/ward2.html">Integer Sequences and Periodic Points</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3

%H Emmanuel Ferrand, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Ferrand/ferrand8.html">Deformations of the Taylor Formula</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

%H Robert Granger, <a href="https://arxiv.org/abs/1610.06878">On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients</a>, arXiv:1610.06878 [math.AG], 2016. See 1st and 2nd column of Table 1 p. 13.

%H A. Hardt and J. M. Troyka, <a href="http://www.mat.unisi.it/newsito/puma/public_html/23_3/hardt_troyka.pdf">Restricted symmetric signed permutations</a>, Pure Mathematics and Applications, Vol. 23 (No. 3, 2012), pp. 179--217.

%H A. Hardt and J. M. Troyka, <a href="https://apps.carleton.edu/curricular/math/assets/Andy_hardt_slides.pdf">Slides</a> (associated with the Hardt and Troyka reference above).

%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 11. <a href="http://tohbook.info">Book's website</a>

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

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H Wolfdieter Lang, <a href="/A000225/a000225.pdf">Notes on certain inhomogeneous three term recurrences.</a>

%H J. Loy, <a href="http://www.jimloy.com/puzz/hanoi.htm">The Tower of Hanoi</a>

%H Edouard Lucas, <a href="http://www.mathstat.dal.ca/FQ/Books/Complete/simply-periodic.pdf">The Theory of Simply Periodic Numerical Functions</a>, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.

%H Mathforum, <a href="http://mathforum.org/dr.math/faq/faq.tower.hanoi.html">Tower of Hanoi</a>

%H Mathforum, Problem of the Week, <a href="http://mathforum.org/midpow/solutions/solution.ehtml?puzzle=17">The Tower of Hanoi Puzzle</a>

%H R. Mestrovic, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012 - From _N. J. A. Sloane_, Jun 13 2012

%H N. Moreira and R. Reis, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Moreira/moreira8.html">On the Density of Languages Representing Finite Set Partitions</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.

%H N. Neumarker, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/">Realizability of Integer Sequences as Differences of Fixed Point Count Sequences< a>, JIS 12 (2009) 09.4.5, Example 11.

%H NRICH 1246, <a href="http://nrich.maths.org/1246">Frogs</a>

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

%H Bernard Schott, <a href="/A125134/a125134.pdf">Les nombres brésiliens</a>, Reprinted from Quadrature, no. 76, avril-juin 2010, pages 30-38, included here with permission from the editors of Quadrature.

%H R. R. Snapp, <a href="http://www.cs.uvm.edu/~snapp/teaching/CS5/lectures/hanoi.pdf">The Tower of Hanoi</a>

%H Thesaurus.maths.org, <a href="http://thesaurus.maths.org/dictionary/map/word/3371">Mersenne Number</a>

%H Thinks.com, <a href="http://thinks.com/java/hanoi/hanoi.htm">Tower of Hanoi, A classic puzzle game</a>

%H A. Umar, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Umar/umar2.html">Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations</a>, Journal of Integer Sequences, 14 (2011), #11.7.5.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>, <a href="http://mathworld.wolfram.com/Digit.html">Digit</a>, <a href="http://mathworld.wolfram.com/MersenneNumber.html">Mersenne Number</a>, <a href="http://mathworld.wolfram.com/Repunit.html">Repunit</a>, <a href="http://mathworld.wolfram.com/Rule222.html">Rule 222</a>, <a href="http://mathworld.wolfram.com/Run.html">Run</a>, and <a href="http://mathworld.wolfram.com/TowersofHanoi.html">Towers of Hanoi</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/H_tree">H tree</a>, <a href="http://en.wikipedia.org/wiki/Lucas_sequence">Lucas sequence</a>, and <a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi">Tower of Hanoi</a>

%H K. K. Wong, <a href="http://www.lhs.berkeley.edu/Java/Tower/Tower.html">Tower Of Hanoi:Online Game</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/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).

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

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

%F E.g.f. if offset 1: ((exp(x)-1)^2)/2.

%F a(n) = Sum_{k=0..n-1} 2^k. - _Paul Barry_, May 26 2003

%F a(n) = a(n-1)+2a(n-2)+2, a(0)=0, a(1)=1. - _Paul Barry_, Jun 06 2003

%F Let b(n)=(-1)^(n-1)a(n). Then b(n) = Sum_{i=1..n} i!*i*Stirling2(n,i)*(-1)^(i-1). E.g.f. of b(n): (exp(x)-1)/exp(2x). - Mario Catalani (mario.catalani(AT)unito.it), Dec 19 2003

%F a(n+1) = 2*a(n) + 1, a(0) = 0.

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

%F a(n) = n + Sum_{i=0..n-1} a(i); a(0) = 0. - _Rick L. Shepherd_, Aug 04 2004

%F a(n+1) = (n+1)*Sum_{k=0..n} binomial(n, k)/(k+1). - _Paul Barry_, Aug 06 2004

%F a(n+1) = Sum_{k=0..n} binomial(n+1, k+1). - _Paul Barry_, Aug 23 2004

%F Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2). - _Ross La Haye_, Feb 07 2005

%F a(n) = A119258(n,n-1) for n>0. - _Reinhard Zumkeller_, May 11 2006

%F a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0,a(1)=1. - _Lekraj Beedassy_, Jun 07 2006

%F Sum_{n>0} 1/a(n) = 1.606695152...(Erdős-Borwein constant;see A065442, A038631). - _Philippe Deléham_, Jun 27 2006

%F Stirling_2(n-k,2) starting from n=k+1. - _Artur Jasinski_, Nov 18 2006

%F a(n) = A125118(n,1) for n>0. - _Reinhard Zumkeller_, Nov 21 2006

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

%F a(n) = A024088(n)/A001576(n). -_Reinhard Zumkeller_, Feb 15 2009

%F From _Enrique Pérez Herrero_, Aug 21 2010: (Start)

%F a(n) = J_n(2), where J_n is the n-th Jordan Totient function: (A007434, is J_2)

%F a(n) = Sum_{d|2} d^n*mu(2/d) (End)

%F a(n) = (A007283(n)/3)-1. - _Martin Ettl_, Nov 11 2012

%F a(n) = det(|s(i+2,j+1)|, 1 <= i,j <= n-1), where s(n,k) are Stirling numbers of the first kind. - _Mircea Merca_, Apr 06 2013

%F G.f.: Q(0), where Q(k)= 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 - 1/(2*4^k - 8*x*16^k/(4*x*4^k - 1/Q(k+1)))))); (continued fraction). - _Sergei N. Gladkovskii_, May 22 2013

%F E.g.f.: Q(0), where Q(k)= 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - (k+1)/Q(k+1))); (continued fraction).

%F G.f.: Q(0), where Q(k)= 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - 1/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 23 2013

%F a(n) = A000203(2^(n-1)), n>=1. - _Ivan N. Ianakiev_, Aug 17 2013

%F a(n) = Sum_{t_1+2*t_2+...+n*t_n=n} n*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)/(t_1+t_2 +...+t_n). - _Mircea Merca_, Dec 06 2013

%F a(0) = 0; a(n) = a(n-1) + 2^(n-1) for n>=1. - _Fred Daniel Kline_, Feb 09 2014

%F a(n) = A125128(n) - A000325(n) + 1. - _Miquel Cerda_, Aug 07 2016

%F From _Ilya Gutkovskiy_, Aug 07 2016: (Start)

%F Binomial transform of A057427.

%F Sum_{n>=0} a(n)/n! = A090142. (End)

%F a(n) = A000918(n) + 1. - _Miquel Cerda_, Aug 09 2016

%F a(n+1) = (A095151(n+1) - A125128(n))/2. - _Miquel Cerda_, Aug 12 2016

%F a(n) = (A079583(n) - A000325(n+1))/2. - _Miquel Cerda_, Aug 15 2016

%F Convolution of binomial coefficient C(n,a(k)) with itself is C(n,a(k+1)) for all k>=3. - _Anton Zakharov_, Sep 05 2016

%F a(n) = (A083706(n-1) + A000325(n))/2. - _Miquel Cerda_, Sep 30 2016

%F a(n) = A005803(n) + A005408(n-1). - _Miquel Cerda_, Nov 25 2016

%F a(n) = A279396(n+2,2). - _Wolfdieter Lang_, Jan 10 2017

%F a(n) = n + Sum_{j=1..n-1} (n-j)*2^(j-1). See a Jun 14 2017 formula for A000918(n+1) with an interpretation. - _Wolfdieter Lang_, Jun 14 2017

%e For n=3, a(3)=S(4,2)=7, a Stirling number of the second kind, since there are 7 ways to partition {a,b,c,d} into 2 nonempty subsets, namely,

%e {a}U{b,c,d}, {b}U{a,c,d}, {c}U{a,b,d}, {d}U{a,b,c}, {a,b}U{c,d}, {a,c}U{b,d}, and {a,d}U{b,c}. - _Dennis P. Walsh_, Mar 29 2011

%e Since a(3) = 7, there are 7 signed permutations of 4 that are equal to the bar of their reverse-complements and avoid {(-2,-1), (-1,+2), (+2,+1)}. These are:

%e (+1,+2,-3,-4),

%e (+1,+3,-2,-4),

%e (+1,-3,+2,-4),

%e (+2,+4,-1,-3),

%e (+3,+4,-1,-2),

%e (-3,+1,-4,+2),

%e (-3,-4,+1,+2).

%e - _Justin M. Troyka_, Aug 13 2011

%e G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...

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

%p A000225:=1/(2*z-1)/(z-1); # _Simon Plouffe_ in his 1992 dissertation, sequence starting at a(1)

%t a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* _Stefan Steinerberger_, Mar 30 2006 *)

%t Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)

%t NestList[2 # + 1 &, 0, 32] (* _Robert G. Wilson v_ *)

%t 2^Range[0, 20] - 1 (* _Eric W. Weisstein_, Jul 17 2017 *)

%o (PARI) A000225(n) = 2^n-1 \\ _Michael B. Porter_, Oct 27 2009

%o (Haskell)

%o a000225 = (subtract 1) . (2 ^)

%o a000225_list = iterate ((+ 1) . (* 2)) 0

%o -- _Reinhard Zumkeller_, Mar 20 2012

%o (PARI) concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ _Altug Alkan_, Oct 28 2015

%Y Cf. A000043, A000079, A000668, A001045, A001348, A009545, A016189, A052955, A083329, A085104, A144081.

%Y Cf. a(n)=A112492(n, 2). Rightmost column of A008969.

%Y a(n) = A118654(n, 1) = A118654(n-1, 3), for n > 0.

%Y Subsequence of A132781.

%Y Smallest number whose base b sum of digits is n: this sequence (b=2), A062318 (b=3), A180516 (b=4), A181287 (b=5), A181288 (b=6), A181303 (b=7), A165804 (b=8), A140576 (b=9), A051885 (b=10).

%Y Cf. A000203, A239473, A279396.

%Y Cf. A008277, A048993 (columns k=2), A000918.

%K nonn,easy,core,nice,changed

%O 0,3

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy .

Last modified July 22 03:22 EDT 2017. Contains 289648 sequences.