|
| |
|
|
A000225
|
|
2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)
(Formerly M2655 N1059)
|
|
484
| |
|
|
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank-1 matroids over S_n.
Numbers n such that central binomial coefficient is odd : Mod[A001405[A000225(n)],2]=1 - Labos E. (labos(AT)ana.sote.hu), Mar 12 2003
This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922.
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
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 (amarnath_murthy(AT)yahoo.com), Oct 23 2003
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 (qntmpkt(AT)yahoo.com), Apr 28 2005
Numbers whose binary representation is 111...1. E.g. the 7th term is (2^7)-1=127=1111111 (in base 2). - Alexandre Wajnberg (alexandre.wajnberg(AT)ulb.ac.be), Jun 08 2005
a(n) = A099393(n-1) - A020522(n-1) for n>0. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 07 2006
Numbers n for which the expression 2^n/(n+1) is an integer. - Paolo P. Lava (paoloplava(AT)gmail.com), May 12 2006
Number of nonempty subsets of a set with n elements. - Michael Somos Sep 03 2006
For n>=2, a(n) is the least Fibonacci n-step number that is not a power of 2. - Rick L. Shepherd (rshepherd2(AT)hotmail.com), Nov 19 2007
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 (rlahaye(AT)new.rr.com), Jan 10 2008
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.
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
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 (ctibor.zizka(AT)seznam.cz), Mar 03 2008
a(n) is also a Mersenne prime A000668 when n is a prime number A000043. [From Omar E. Pol (info(AT)polprimos.com), Aug 31 2008]
a(n) is also a Mersenne number A001348 when n is prime. [From Omar E. Pol (info(AT)polprimos.com), Sep 05 2008]
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). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 10 2008]
Numbers n such that A000120(n)/A070939(n) = 1 [From Ctibor O.Zizka (c.zizka(AT)email.cz), Oct 15 2008]
a(n) = A024036(n)/A000051(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 14 2009]
For n > 0, sequence is equal to partial sums of A000079 ; a(n) = A000203(A000079(n-1)). [From Lekraj Beedassy (blekraj(AT)yahoo.com), May 02 2009]
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 23 2009: (Start)
Starting with offset 1 = the Jacobsthal sequence, A001045,
(1, 1, 3, 5, 11, 21,...) convolved with (1, 2, 2, 2,...). (End)
Numbers n such that n=2*phi(n+1)-1. [From Farideh Firoozbakht (mymontain(AT)yahoo.com), Jul 23 2009]
a(n) = (a(n-1)+1) th odd numbers = A005408(a(n-1)) for n >= 1. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Sep 11 2009]
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). [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Oct 16 2009]
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.) [From W. Bomfim (webonfim(AT)bol.com.br), Oct 31 2009]
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). [From Milan R. Janjic (agnus(AT)blic.net), Jan 26 2010]
a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 28 2010]
For n>0: A179857(a(n))=A024036(n) and A179857(m)<A024036(n) for m<a(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jul 31 2010]
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. [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Oct 18 2010]
a(n)=S(n+1,2), a Stirling number of the second kind.
See the example below. [From Dennis Walsh (dwalsh(AT)mtsu.edu), Mar 29 2011]
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.
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
A159780(a(n)) = n and A159780(m) < n for m < a(n). [Reinhard Zumkeller, Oct 21 2011]
This sequence is also the number of proper subsets of a set with n elements. -Mohammad K. Azarian, Oct 27 2011
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
|
|
|
REFERENCES
| P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178; http://www.combinatorics.org/Volume_18/PDF/v18i1p178.pdf.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Michael Boardman, "The Egg-Drop Numbers", Mathematics Magazine, 77 (2004), 368-372.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.
A. Hardt and J. M. Troyka, Restricted symmetric signed permutations, pre-print. [For more information, email troykaj(AT)carleton.edu.]
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
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).
A. Umar, Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations, Journal of Integer Sequences, 14 (2011), #11.7.5.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", pp. 112-3, Penguin Books 1987.
K. Zsigmondy, Zur Theorie der Potenreste, Monatsh. Math., 3 (1892), 265-284.
|
|
|
LINKS
| Franklin T. Adams-Watters, Table of n, a(n) for n = 0..1000
Anonymous, The Tower of Hanoi
J. Bernheiden, Mersenne Numbers (Text in German)
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 =< a < 100
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of a^n +- 1, 13 =< a < 100 :Update 2
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations Of Cunningham Numbers With Bases 13 To 99. Millennium Edition
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of Cunningham numbers with bases 13 to 99: Millennium edition
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 =< a <100
John Brillhart et al., Cunningham Project [Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers]
J. Britton, The Tower of Hanoi
C. K. Caldwell, The Prime Glossary, Mersenne number
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
W. M. B. Dukes, On the number of matroids on a finite set
W. Edgington, Mersenne Page
T. Eveilleau, Animated solution to the Tower of Hanoi problem
G. Everest, S. Stevens, D. Tamsett and T. Ward, Primitive divisors of quadratic polynomial sequences
G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 138
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 345
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 371
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 880
W. Lang, Notes on certain inhomogeneous three term recurrences.
J. Loy, The Tower of Hanoi
Mathforum, Tower of Hanoi
Mathforum, Problem of the Week, The Tower of Hanoi Puzzle
NationMaster.com, Tower of Hanoi
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. R. Snapp, The Tower of Hanoi
Thesaurus.maths.org, Mersenne Number
Thinks.com, Tower of Hanoi, A classic puzzle game
Eric Weisstein's World of Mathematics, Coin Tossing
Eric Weisstein's World of Mathematics, Digit
Eric Weisstein's World of Mathematics, Mersenne Number
Eric Weisstein's World of Mathematics, Repunit
Eric Weisstein's World of Mathematics, Towers of Hanoi
Eric Weisstein's World of Mathematics, Run
Eric Weisstein's World of Mathematics, Rule 222
Wikipedia, Tower of Hanoi
K. K. Wong, Tower Of Hanoi:Online Game
Index entries for "core" sequences
Index entries for sequences related to linear recurrences with constant coefficients, signature (3,-2).
Index to divisibility sequences
|
|
|
FORMULA
| G.f.: x/((1-2*x)*(1-x)). E.g.f.: exp(2*x)-exp(x).
E.g.f. if offset 1: ((exp(x)-1)^2)/2.
a(n)=sum{k=0..n-1, 2^k} - Paul Barry (pbarry(AT)wit.ie), May 26 2003
a(n)=a(n-1)+2a(n-2)+2, a(0)=0, a(1)=1. - Paul Barry (pbarry(AT)wit.ie), Jun 06 2003
Let b(n)=(-1)^(n-1)a(n). Then b(n)=Sum(i!i Stirling2(n, i)(-1)^(i-1), i=1, .., n). E.g.f. of b(n): (exp(x)-1)/exp(2x). - Mario Catalani (mario.catalani(AT)unito.it), Dec 19 2003
a(n+1) = 2*a(n) + 1, a(0) = 0.
Sum_{k=1..n} C(n, k).
a(n) = n + sum(i=0, n-1, a(i)); a(0) = 0. - Rick L. Shepherd (rshepherd2(AT)hotmail.com), Aug 04 2004
a(n+1)=(n+1)sum{k=0..n, binomial(n, k)/(k+1)} - Paul Barry (pbarry(AT)wit.ie), Aug 06 2004
a(n+1)=sum{k=0..n, binomial(n+1, k+1)} - Paul Barry (pbarry(AT)wit.ie), Aug 23 2004
Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2). - Ross La Haye (rlahaye(AT)new.rr.com), Feb 07 2005
a(n) = A119258(n,n-1) for n>0. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), May 11 2006
a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0,a(1)=1 - Lekraj Beedassy (blekraj(AT)yahoo.com), Jun 07 2006
Sum_{n=1..inf}1/a(n) = 1.606695152...(Erdos-Borwein constant;see A065442, A038631) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 27 2006
Stirling_2[n-k,2] starting from n=k+1. - Artur Jasinski (grafix(AT)csl.pl), Nov 18 2006
a(n) = A125118(n,1) for n>0. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Nov 21 2006
a(n) = StirlingS2(n+1,2) - Ross La Haye (rlahaye(AT)new.rr.com), Jan 10 2008
a(n) = A024088(n)/A001576(n). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 15 2009]
Contribution from Enrique Perez Herrero (psychgeometry(AT)gmail.com), Aug 21 2010: (Start)
a(n)=J_n(2), where J_n is the nth Jordan Totient function: (A007434, is J_2)
a(n)=sum(d|2, d^n*mu(2/d)) (End)
|
|
|
EXAMPLE
| 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,
{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}. [From Dennis Walsh (dwalsh(AT)mtsu.edu), Mar 29 2011]
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:
(+1,+2,-3,-4),
(+1,+3,-2,-4),
(+1,-3,+2,-4),
(+2,+4,-1,-3),
(+3,+4,-1,-2),
(-3,+1,-4,+2),
(-3,-4,+1,+2).
- Justin M. Troyka, Aug 13 2011.
|
|
|
MAPLE
| A000225 := n->2^n-1; [ seq(2^n-1, n=0..50) ];
seq(add(binomial(n, k)*(bell(k-n)), k=1..n), n=0..32); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 01 2006
a:=n->sum (2^j, j=0..n): seq(a(n), n=-1..31); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 27 2007
A000225:=1/(2*z-1)/(z-1); [S. Plouffe in his 1992 dissertation, sequence starting at a(1).]
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+1 od: seq(a[n], n=0..32); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 20 2008
|
|
|
MATHEMATICA
| a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] - Stefan Steinerberger (stefan.steinerberger(AT)gmail.com), Mar 30 2006
Array[2^# - 1 &, 50, 0] - Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006
Table[Sum[ Binomial[n + 1, k + 1], {k, 0, n}], {n, -1, 31}] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 08 2009]
NestList[2# + 1 &, 0, 32] (* RGWv *)
|
|
|
PROG
| (Other) sage: [gaussian_binomial(n, 1, 2) for n in xrange(1, 33)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 24 2009]
(PARI) A000225(n) = 2^n-1 [From Michael Porter (michael_b_porter(AT)yahoo.com), Oct 27 2009]
|
|
|
CROSSREFS
| Cf. A000079, A016189.
Cf. a(n)=A112492(n, 2). Rightmost column of A008969.
a(n) = A118654(n, 1) = A118654(n-1, 3), for n > 0.
Subsequence of A132781.
Cf. A000043, A000668. [From Omar E. Pol (info(AT)polprimos.com), Aug 31 2008]
Cf. A000040, A001348. [From Omar E. Pol (info(AT)polprimos.com), Sep 05 2008]
A009545, A144081, [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 10 2008]
A001045 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 23 2009]
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).
Sequence in context: A060152 A168604 A126646 * A123121 A117060 A178460
Adjacent sequences: A000222 A000223 A000224 * A000226 A000227 A000228
|
|
|
KEYWORD
| nonn,easy,core,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional links provided by Lekraj Beedassy (blekraj(AT)yahoo.com), Dec 20 2003
|
| |
|
|
