

A000225


a(n) = 2^n  1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)
(Formerly M2655 N1059)


1264



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, 8589934591
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank1 matroids over S_n.
Numbers k such that the kth central binomial coefficient is odd: A001405(k) mod 2 = 1.  Labos Elemer, Mar 12 2003
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 (nm+1)), for all m.  Amarnath Murthy, 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, 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, Jun 08 2005
Number of nonempty subsets of a set with n elements.  Michael Somos, Sep 03 2006
For n >= 2, a(n) is the least Fibonacci nstep number that is not a power of 2.  Rick L. Shepherd, Nov 19 2007
Let P(A) be the power set of an nelement 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
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. AdamsWatters, Oct 28 2011
2^n1 is the sum of the elements in a Pascal triangle of depth n.  Brian Lewis (bsl04(AT)uark.edu), Feb 26 2008
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
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
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i1]=1, and A[i,j]=0 otherwise. Then, for n >= 1, a(n)=det(A).  Milan Janjic, Jan 26 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.  Wolfdieter Lang, Oct 18 2010
a(n) = S(n+1,2), a Stirling number of the second kind. See the example below.  Dennis P. Walsh, 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 reversecomplements and avoid the set of patterns {(2,1), (1,+2), (+2,+1)}. (See the Hardt and Troyka reference.)  Justin M. Troyka, Aug 13 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
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
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
Start with n. Each n generates a sublist {n1,n2,...,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
This is the Lucas U(P=3,Q=2) sequence.  R. J. Mathar, Oct 24 2012
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
Number of line segments after nth stage in the H tree.  Omar E. Pol, Feb 16 2013
a(n) is the highest power of 2 such that 2^a(n) divides (2^n)!.  Ivan N. Ianakiev, Aug 17 2013
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
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
a(n) !== 4 (mod 5); a(n) !== 10 (mod 11); a(n) !== 2, 4, 5, 6 (mod 7).  Carmine Suriano, Apr 06 2014
After 0, antidiagonal sums of the array formed by partial sums of integers (1, 2, 3, 4, ...).  Luciano Ancora, Apr 24 2015
a(n+1) equals the number of ternary words of length n avoiding 01,02.  Milan Janjic, Dec 16 2015
With offset 0 and another initial 0, the nth term of 0, 0, 1, 3, 7, 15, ... is the number of commas required in the fullyexpanded 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 fullyexpanded 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
With the quantum integers defined by [n+1]_q = (q^(n+1)  q^(n1)) / (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
Except for the initial terms, the decimal representation of the xaxis of the nth stage of growth of the twodimensional cellular automaton defined by "Rule 659", "Rule 721" and "Rule 734", based on the 5celled von Neumann neighborhood initialized with a single on cell.  Robert Price, Mar 14 2017
a(n), n > 1, is the number of maximal subsemigroups of the monoid of orderpreserving partial injective mappings on a set with n elements.  James Mitchell and Wilf A. Wilson, Jul 21 2017
Also the number of independent vertex sets and vertex covers in the complete bipartite graph K_{n1,n1}.  Eric W. Weisstein, Sep 21 2017
Sum_{k=0..n} p^k is the determinant of n X n matrix M_(i, j) = binomial(i + j  1, j)*p + binomial(i+j1, i), in this case p=2 (empirical observation).  Tony Foster III, May 11 2019
The rational numbers r(n) = a(n+1)/2^(n+1) = a(n+1)/A000079(n+1) appear also as root of the nth iteration f^{[n]}(c; x) = 2^(n+1)*x  a(n+1)*c of f(c; x) = f^{[0]}(c; x) = 2*x  c as r(n)*c. This entry is motivated by a riddle of Johann Peter Hebel (1760  1826): Erstes Rechnungsexempel(Ein merkwürdiges RechnungsExempel) from 1803, with c = 24 and n = 2, leading to the root r(2)*24 = 21 as solution. See the link and reference. For the second problem, also involving the present sequence, see a comment in A130330.  Wolfdieter Lang, Oct 28 2019
a(n) is the sum of the smallest elements of all subsets of {1,2,..,n} that contain n. For example, a(3)=7; the subsets of {1,2,3} that contain 3 are {3}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 7.  Enrique Navarrete, Aug 21 2020
a(n1) is the number of nonempty subsets of {1,2,..,n} which don't have an element that is the size of the set. For example, for n = 4, a(3) = 7 and the subsets are {2}, {3}, {4}, {1,3}, {1,4}, {3,4}, {1,2,4}.  Enrique Navarrete, Nov 21 2020
Also the number of dominating sets in the complete graph K_n.
Also the number of minimum dominating sets in the nhelm graph for n >= 3. (End)
Conjecture: except for a(2)=3, numbers m such that 2^(m+1)  2^j  2^k  1 is composite for all 0 <= j < k <= m.  Chai Wah Wu, Sep 08 2021
a(n) is the number of threeinarows passing through a corner cell in ndimensional tictactoe.  Ben Orlin, Mar 15 2022
a(n) == 1 (mod 30) for n == 1 (mod 4);
a(n) == 7 (mod 120) for n == 3 (mod 4);
(a(n)  1)/30 = (a(n+2)  7)/120 for n odd;
(a(n)  1)/30 = (a(n+2)  7)/120 = A131865(m) for n == 1 (mod 4) and m >= 0 with A131865(0) = 0. (End)
a(n) is the number of ndigit numbers whose smallest decimal digit is 8.  Stefano Spezia, Nov 15 2023
Also, number of nodes in a perfect binary tree of height n1, or: number of squares (or triangles) after the nth step of the construction of a Pythagorean tree: Start with a segment. At each step, construct squares having the most recent segment(s) as base, and isoceles right triangles having the opposite side of the squares as hypotenuse ("on top" of each square). The legs of these triangles will serve as the segments which are the bases of the squares in the next step.  M. F. Hasler, Mar 11 2024


REFERENCES

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, AddisonWesley, 2004, p. 134.
Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg SchmidtBergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 2021, Loesung, S. 3637. See also the link below.
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).
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", Penguin Books, 1987, pp. 112113.


LINKS

John Brillhart et al., Cunningham Project [Factorizations of b^n + 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers] [Subscription required].
P. Catarino, H. Campos, and P. Vasco, On the Mersenne sequence, Annales Mathematicae et Informaticae, 46 (2016) pp. 3753.
A. Hardt and J. M. Troyka, Slides (associated with the Hardt and Troyka reference above).
Bernard Schott, Les nombres brésiliens, Reprinted from Quadrature, no. 76, avriljuin 2010, pages 3038, included here with permission from the editors of Quadrature.
Eric Weisstein's World of Mathematics, Complete


FORMULA

G.f.: x/((12*x)*(1x)).
E.g.f.: exp(2*x)  exp(x).
E.g.f. if offset 1: ((exp(x)1)^2)/2.
a(n) = Sum_{k=0..n1} 2^k.  Paul Barry, May 26 2003
a(n) = a(n1) + 2*a(n2) + 2, a(0)=0, a(1)=1.  Paul Barry, Jun 06 2003
Let b(n) = (1)^(n1)*a(n). Then b(n) = Sum_{i=1..n} i!*i*Stirling2(n,i)*(1)^(i1). 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.
a(n) = Sum_{k=1..n} binomial(n, k).
a(n+1) = (n+1)*Sum_{k=0..n} binomial(n, k)/(k+1).  Paul Barry, Aug 06 2004
a(n+1) = Sum_{k=0..n} binomial(n+1, k+1).  Paul Barry, Aug 23 2004
Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2).  Ross La Haye, Feb 07 2005
a(n) = J_n(2), where J_n is the nth Jordan Totient function: (A007434, is J_2).
a(n) = Sum_{d2} d^n*mu(2/d). (End)
a(n) = det(s(i+2,j+1), 1 <= i,j <= n1), where s(n,k) are Stirling numbers of the first kind.  Mircea Merca, Apr 06 2013
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
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).
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
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
Sum_{n>=0} a(n)/n! = A090142. (End)
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
a(n) = n + Sum_{j=1..n1} (nj)*2^(j1). See a Jun 14 2017 formula for A000918(n+1) with an interpretation.  Wolfdieter Lang, Jun 14 2017
a(n+m) = a(n)*a(m) + a(n) + a(m).  Yuchun Ji, Jul 27 2018
a(n+m) = a(n+1)*a(m)  2*a(n)*a(m1).  Taras Goy, Dec 23 2018
a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(i + j  1, j)*2 + binomial(i+j1, i) (empirical observation).  Tony Foster III, May 11 2019


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}.  Dennis P. Walsh, Mar 29 2011
Since a(3) = 7, there are 7 signed permutations of 4 that are equal to the bar of their reversecomplements 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). (End)
G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...


MAPLE

A000225 := n>2^n1; [ seq(2^n1, n=0..50) ];


MATHEMATICA

Array[2^#  1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
CoefficientList[Series[1/(1  3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)


PROG

(Haskell)
a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
(PARI) concat(0, Vec(x/((12*x)*(1x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015
(SageMath)
def isMersenne(n): return n == sum([(1  b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019
(Python)


CROSSREFS

Cf. A001348 (Mersenne numbers with n prime).


KEYWORD

nonn,easy,core,nice


AUTHOR



EXTENSIONS



STATUS

approved



