A024036 -id:A024036 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank-1 matroids over S_n.
Numbers k such that the k-th central binomial coefficient is odd: A001405(k) mod 2 = 1. - Labos Elemer, 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, 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 n-step number that is not a power of 2. - Rick L. Shepherd, 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, 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, Mar 03 2008
a(n) is also a Mersenne prime A000668 when n is a prime number in A000043. - Omar E. Pol, Aug 31 2008
a(n) is also a Mersenne number A001348 when n is prime. - Omar E. Pol, 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). - Gary W. Adamson, Sep 10 2008
Numbers n such that A000120(n)/A070939(n) = 1. - Ctibor O. Zizka, Oct 15 2008
For n > 0, sequence is equal to partial sums of A000079; a(n) = A000203(A000079(n-1)). - Lekraj Beedassy, May 02 2009
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
Numbers n such that n=2*phi(n+1)-1. - Farideh Firoozbakht, Jul 23 2009
a(n) = (a(n-1)+1)-th odd numbers = A005408(a(n-1)) for n >= 1. - Jaroslav Krizek, Sep 11 2009
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
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,i-1]=-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 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
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 {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
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 n-th stage in the H tree. - Omar E. Pol, Feb 16 2013
Row sums of triangle in A162741. - Reinhard Zumkeller, Jul 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 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
With the quantum integers defined by [n+1]A001045%20are%20given%20by%20q%20=%20i%20*%20sqrt(2)%20for%20i%5E2%20=%20-1.%20Cf.%20A239473.%20-%20_Tom%20Copeland">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
For n>1: numbers n such that n - 1 divides sigma(n + 1). - Juri-Stepan Gerasimov, Oct 08 2016
This is also the second column of the Stirling2 triangle A008277 (see also A048993). - Wolfdieter Lang, Feb 21 2017
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
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
Also the number of independent vertex sets and vertex covers in the complete bipartite graph K_{n-1,n-1}. - 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+j-1, 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 n-th 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 Rechnungs-Exempel) 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(n-1) 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
From Eric W. Weisstein, Sep 04 2021: (Start)
Also the number of dominating sets in the complete graph K_n.
Also the number of minimum dominating sets in the n-helm 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 three-in-a-rows passing through a corner cell in n-dimensional tic-tac-toe. - Ben Orlin, Mar 15 2022
From Vladimir Pletser, Jan 27 2023: (Start)
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 n-digit numbers whose smallest decimal digit is 8. - Stefano Spezia, Nov 15 2023
Also, number of nodes in a perfect binary tree of height n-1, or: number of squares (or triangles) after the n-th 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 isosceles 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
a(n) is the length of the longest path in the n-dimensional hypercube. - Christian Barrientos, Apr 13 2024
a(n) is the diameter of the n-Hanoi graph.  Equivalently, a(n) is the largest minimum number of moves between any two states of the Towers of Hanoi problem (aka problem of Benares Temple described above). - Allan Bickle, Aug 09 2024

			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
From _Justin M. Troyka_, Aug 13 2011: (Start)
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). (End)
G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...
For the Towers of Hanoi problem with 2 disks, the moves are as follows, so a(2) = 3.
12|_|_ -> 2|1|_ -> _|1|2 -> _|_|12  - _Allan Bickle_, Aug 07 2024

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, Addison-Wesley, 2004, p. 134.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 79.
Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg Schmidt-Bergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 20-21, Loesung, S. 36-37. See also the link below.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 60, 75-83.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", Penguin Books, 1987, pp. 112-113.

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..1000
Omran Ahmadi and Robert Granger, An efficient deterministic test for Kloosterman sum zeros, Math. Comp. 83 (2014), 347-363, arXiv:1104.3882 [math.NT], 2011-2012. See 1st and 2nd column of Table 1 p. 9.
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Anonymous, The Tower of Hanoi
M. Baake, F. Gahler and U. Grimm, Examples of substitution systems and their factors, arXiv:1211.5466 [math.DS], 2012-2013.
Michael Baake, Franz Gähler, and Uwe Grimm, Examples of Substitution Systems and Their Factors, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.
J. Bernheiden, Mersennesche Zahlen, (Text in German) [Wayback Machine cached version].
Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100, CWI Report 9212, 1992 [Wayback Machine cached version].
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 [BROKEN LINK]
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] [Subscription required].
Jill Britton, The Tower of Hanoi [Video file, Wayback Machine cached version].
Jill Britton, The Frog Puzzle [Wayback Machine cached version].
C. K. Caldwell, The Prime Glossary, Mersenne number
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.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Catarino, H. Campos, and P. Vasco, On the Mersenne sequence, Annales Mathematicae et Informaticae, 46 (2016) pp. 37-53.
Robert George Cowell, A unifying framework for the modelling and analysis of STR DNA samples arising in forensic casework, arXiv:1802.09863 [stat.AP], 2018.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
W. Edgington, Mersenne Page [BROKEN LINK]
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
T. Eveilleau, Animated solution to the Tower of Hanoi problem
G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.
G. Everest, S. Stevens, D. Tamsett and T. Ward, Primitive divisors of quadratic polynomial sequences, arXiv:math/0412079 [math.NT], 2004-2006.
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.
Bakir Farhi, Summation of Certain Infinite Lucas-Related Series, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Carrie E. Finch-Smith and R. Scottfield Groth, Arbitrarily Long Sequences of Sierpiński Numbers that are the Sum of a Sierpiński Number and a Mersenne Number, Journal of Integer Sequences, Vol. 28 (2025), Article 25.2.4. See p. 22.
Robert Frontczak and Taras Goy, Mersenne-Horadam identities using generating functions, Carpathian Mathematical Publications, Vol. 12, no. 1, (2020), 34-45.
Robert Granger, On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients, arXiv:1610.06878 [math.AG], 2016. See 1st and 2nd column of Table 1 p. 13.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Taras Goy, On new identities for Mersenne numbers, Applied Mathematics E-Notes, 18 (2018), 100-105.
R. K. Guy, Letter to N. J. A. Sloane
A. Hardt and J. M. Troyka, Restricted symmetric signed permutations, Pure Mathematics and Applications, Vol. 23 (No. 3, 2012), pp. 179--217.
A. Hardt and J. M. Troyka, Slides (associated with the Hardt and Troyka reference above).
Johann Peter Hebel, Erstes Rechnungsexempel, 1803; Solution: Auflösung des ersten Rechnungsexempels und ein zweites, 1804.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 11. Book's website
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 138, 345, 371, and 880
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
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.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
J. Loy, The Tower of Hanoi
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
Mathforum, Tower of Hanoi
Mathforum, Problem of the Week, The Tower of Hanoi Puzzle
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012
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. Neumarker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, JIS 12 (2009) 09.4.5, Example 11.
NRICH 1246, Frogs
Ahmet Öteleş, Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See pp. 1, 4.
Bernard Schott, Les nombres brésiliens, Reprinted from Quadrature, no. 76, avril-juin 2010, pages 30-38, included here with permission from the editors of Quadrature.
R. R. Snapp, The Tower of Hanoi.
Amelia Carolina Sparavigna, On the generalized sums of Mersenne, Fermat, Cullen and Woodall Numbers, Politecnico di Torino (Italy, 2019).
Amelia Carolina Sparavigna, Composition Operations of Generalized Entropies Applied to the Study of Numbers, International Journal of Sciences (2019) Vol. 8, No. 4, 87-92.
Amelia Carolina Sparavigna, The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences, Politecnico di Torino, Italy (2019), [math.NT].
Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
Thesaurus.maths.org, Mersenne Number
Thinks.com, Tower of Hanoi, A classic puzzle game
A. Umar, Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations, Journal of Integer Sequences, 14 (2011), #11.7.5.
Eric Weisstein's World of Mathematics, Coin Tossing, Digit, Repunit, Rule 222, Run, and Tower of Hanoi
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Mersenne Number
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, H tree, Lucas sequence, and Tower of Hanoi
K. K. Wong, Tower Of Hanoi:Online Game
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., 3 (1892), 265-284.
Index entries for "core" sequences
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000043 (Mersenne exponents).
Cf. A000668 (Mersenne primes).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A000079, A001045, A009545, A016189, A052955, A083329, A085104, A144081.
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.
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).
Cf. A000203, A239473, A279396.
Cf. A008277, A048993 (columns k=2), A000918, A130330.
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012

A000225 := n->2^n-1; [ seq(2^n-1,n=0..50) ];
A000225:=1/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, sequence starting at a(1)

a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* Stefan Steinerberger, Mar 30 2006 *)
Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NestList[2 # + 1 &, 0, 32] (* Robert G. Wilson v, Feb 28 2011 *)
2^Range[0, 20] - 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {1, 3}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)

A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009

concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015

def A000225(n): return (1<Chai Wah Wu, Jul 06 2022

def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

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, May 26 2003
a(n) = a(n-1) + 2*a(n-2) + 2, a(0)=0, a(1)=1. - Paul Barry, Jun 06 2003
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
a(n+1) = 2*a(n) + 1, a(0) = 0.
a(n) = Sum_{k=1..n} binomial(n, k).
a(n) = n + Sum_{i=0..n-1} a(i); a(0) = 0. - Rick L. Shepherd, Aug 04 2004
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) = A099393(n-1) - A020522(n-1) for n > 0. - Reinhard Zumkeller, Feb 07 2006
a(n) = A119258(n,n-1) for n > 0. - Reinhard Zumkeller, May 11 2006
a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0, a(1)=1. - Lekraj Beedassy, Jun 07 2006
Sum_{n>0} 1/a(n) = 1.606695152... = A065442, see A038631. - Philippe Deléham, Jun 27 2006
Stirling_2(n-k,2) starting from n=k+1. - Artur Jasinski, Nov 18 2006
a(n) = A125118(n,1) for n > 0. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1,2). - Ross La Haye, Jan 10 2008
a(n) = A024036(n)/A000051(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A024088(n)/A001576(n). -Reinhard Zumkeller, Feb 15 2009
a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). - Reinhard Zumkeller, Feb 28 2010
For n > 0: A179857(a(n)) = A024036(n) and A179857(m) < A024036(n) for m < a(n). - Reinhard Zumkeller, Jul 31 2010
From Enrique Pérez Herrero, Aug 21 2010: (Start)
a(n) = J_n(2), where J_n is the n-th Jordan Totient function: (A007434, is J_2).
a(n) = Sum_{d|2} d^n*mu(2/d). (End)
A036987(a(n)) = 1. - Reinhard Zumkeller, Mar 06 2012
a(n+1) = A044432(n) + A182028(n). - Reinhard Zumkeller, Apr 07 2012
a(n) = A007283(n)/3 - 1. - Martin Ettl, Nov 11 2012
a(n+1) = A001317(n) + A219843(n); A219843(a(n)) = 0. - Reinhard Zumkeller, Nov 30 2012
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
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) = A000203(2^(n-1)), n >= 1. - Ivan N. Ianakiev, Aug 17 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
a(0) = 0; a(n) = a(n-1) + 2^(n-1) for n >= 1. - Fred Daniel Kline, Feb 09 2014
a(n) = A125128(n) - A000325(n) + 1. - Miquel Cerda, Aug 07 2016
From Ilya Gutkovskiy, Aug 07 2016: (Start)
Binomial transform of A057427.
Sum_{n>=0} a(n)/n! = A090142. (End)
a(n) = A000918(n) + 1. - Miquel Cerda, Aug 09 2016
a(n+1) = (A095151(n+1) - A125128(n))/2. - Miquel Cerda, Aug 12 2016
a(n) = (A079583(n) - A000325(n+1))/2. - Miquel Cerda, Aug 15 2016
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) = (A083706(n-1) + A000325(n))/2. - Miquel Cerda, Sep 30 2016
a(n) = A005803(n) + A005408(n-1). - Miquel Cerda, Nov 25 2016
a(n) = A279396(n+2,2). - Wolfdieter Lang, Jan 10 2017
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
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k,i). - Wesley Ivan Hurt, Sep 21 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(m-1). - 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+j-1, i) (empirical observation). - Tony Foster III, May 11 2019
From Peter Bala, Jun 27 2025: (Start)
For n >= 1, a(3*n)/a(n) = A001576(n), a(4*n)/a(n) = A034496(n), a(5*n)/a(n) = A020514(n) a(6*n)/a(n) = A034665(n), a(7*n)/a(n) = A020516(n) and a(8*n)/a(n) = A034674(n).
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
Modulo differences in offsets, exp( Sum_{n >= 1} a(k*n)/a(n)*x^n/n ) is the o.g.f. of A006095 (k = 3), A006096 (k = 4), A006097 (k = 5), A006110 (k = 6), A022189 (k = 7), A022190 (k = 8), A022191 (k = 9) and A022192 (k = 10).
The following are all examples of telescoping series:
Sum_{n >= 1} 2^n/(a(n)*a(n+1)) = 1; Sum_{n >= 1} 2^n/(a(n)*a(n+1)*a(n+2)) = 1/9.
In general, for k >= 1, Sum_{n >= 1} 2^n/(a(n)*a(n+1)*...*a(n+k)) = 1/(a(1)*a(2)*...*a(k)*a(k)).
Sum_{n >= 1} 2^n/(a(n)*a(n+2)) = 4/9, since 2^n/(a(n)*a(n+2)) = b(n) - b(n+1), where b(n) = (2/3)*(3*2^(n-1) - 1)/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+2)) = -2/9, since (-2)^n/(a(n)*a(n+2)) = c(n) - c(n+1), where c(n) = (1/3)*(-2)^n/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} 2^n/(a(n)*a(n+4)) = 18/175, since 2^n/(a(n)*a(n+4)) = d(n) - d(n+1), where d(n) = (120*8^n - 140*4^n + 45*2^n - 4)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+4)) = -26/525, since (-2)^n/(a(n)*a(n+4)) = e(n) - e(n+1), where e(n) = (-1)^n*(40*8^n - 24*4^n + 5*2^n)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)). (End)

Name partially edited by Eric W. Weisstein, Sep 04 2021

A000051 a(n) = 2^n + 1.

Original entry on oeis.org

2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825, 2147483649, 4294967297, 8589934593

Offset: 0

N. J. A. Sloane

Same as Pisot sequence L(2,3).
Length of the continued fraction for Sum_{k=0..n} 1/3^(2^k). - Benoit Cloitre, Nov 12 2003
See also A004119 for a(n) = 2a(n-1)-1 with first term = 1. - Philippe Deléham, Feb 20 2004
From the second term on (n>=1), in base 2, these numbers present the pattern 1000...0001 (with n-1 zeros), which is the "opposite" of the binary 2^n-2: (0)111...1110 (cf. A000918). - Alexandre Wajnberg, May 31 2005
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)* charpoly(A,3). - Milan Janjic, Jan 27 2010
First differences of A006127. - Reinhard Zumkeller, Apr 14 2011
The odd prime numbers in this sequence form A019434, the Fermat primes. - David W. Wilson, Nov 16 2011
Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... . - R. J. Mathar, Aug 10 2012
Is the mentioned Pisano period lengths (see above) the same as A007733? - Omar E. Pol, Aug 10 2012
Only positive integers that are not 1 mod (2k+1) for any k>1. - Jon Perry, Oct 16 2012
For n >= 1, a(n) is the total length of the segments of the Hilbert curve after n iterations. - Kival Ngaokrajang, Mar 30 2014
Frénicle de Bessy (1657) proved that a(3) = 9 is the only square in this sequence. - Charles R Greathouse IV, May 13 2014
a(n) is the number of distinct possible sums made with at most two elements in {1,...,a(n-1)} for n > 0. - Derek Orr, Dec 13 2014
For n > 0, given any set of a(n) lattice points in R^n, there exist 2 distinct members in this set whose midpoint is also a lattice point. - Melvin Peralta, Jan 28 2017
Also the number of independent vertex sets, irredundant sets, and vertex covers in the (n+1)-star graph. - Eric W. Weisstein, Aug 04 and Sep 21 2017
Also the number of maximum matchings in the 2(n-1)-crossed prism graph. - Eric W. Weisstein, Dec 31 2017
Conjecture: For any integer n >= 0, a(n) is the permanent of the (n+1) X (n+1) matrix with M(j, k) = -floor((j - k - 1)/(n + 1)). This conjecture is inspired by the conjecture of Zhi-Wei Sun in A036968. - Peter Luschny, Sep 07 2021

Paul Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 60, 244.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.

Ivan Panchenko, Table of n, a(n) for n = 0..100
E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
Bakir Farhi, Summation of Certain Infinite Lucas-Related Series, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.
Massimiliano Fasi and Gian Maria Negri Porzio, Determinants of Normalized Bohemian Upper Hessemberg Matrices, University of Manchester (England, 2019).
Bartomeu Fiol, Jairo Martínez-Montoya, and Alan Rios Fukelman, The planar limit of N=2 superconformal field theories, arXiv:2003.02879 [hep-th], 2020.
Bernard Frénicle de Bessy, Solutio duorum problematum circa numeros cubos et quadratos, (1657). Bibliothèque Nationale de Paris.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 114
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 362
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
Kival Ngaokrajang, Illustration of Hilbert curve for n = 1..5
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 1.
Amelia Carolina Sparavigna, On the generalized sums of Mersenne, Fermat, Cullen and Woodall Numbers, Politecnico di Torino (Italy, 2019).
Amelia Carolina Sparavigna, Composition Operations of Generalized Entropies Applied to the Study of Numbers, International Journal of Sciences (2019) Vol. 8, No. 4, 87-92.
Amelia Carolina Sparavigna, The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences, Politecnico di Torino, Italy (2019), [math.NT].
Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
Eric Weisstein's World of Mathematics, Crossed Prism Graph.
Eric Weisstein's World of Mathematics, Cunningham Number.
Eric Weisstein's World of Mathematics, Fermat-Lucas Number.
Eric Weisstein's World of Mathematics, Hilbert curve.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Irredundant Set.
Eric Weisstein's World of Mathematics, Matching Number.
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set.
Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence.
Eric Weisstein's World of Mathematics, Star Graph.
Eric Weisstein's World of Mathematics, Vertex Cover.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Apart from the initial 1, identical to A094373.
See A008776 for definitions of Pisot sequences.
Column 2 of array A103438.
Cf. A007583 (a((n-1)/2)/3 for odd n).
Cf. A000079, A000225, A000918, A004119, A005126, A006217, A006521, A007583.
Cf. A007689, A007733, A019434, A024036, A027641, A027642, A034472, A034474.
Cf. A034491, A034524, A036968, A052539, A052944, A062394, A062395, A062396.
Cf. A062397, A063376, A063481, A074600 - A074624, A127904, A173786, A176691.
Cf. A178248, A194455, A228081, A323482.

a000051 = (+ 1) . a000079
a000051_list = iterate ((subtract 1) . (* 2)) 2
-- Reinhard Zumkeller, May 03 2012

[2^n+1: n in [0..40]]; // G. C. Greubel, Jan 18 2025

A000051:=-(-2+3*z)/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation
a := n -> add(binomial(n,k)*bernoulli(n-k,1)*2^(k+1)/(k+1),k=0..n); # Peter Luschny, Apr 20 2009

Table[2^n + 1, {n,0,40}]
2^Range[0,40] + 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {2, 3}, 40] (* Eric W. Weisstein, Sep 21 2017 *)

PARI
```
a(n)=2^n+1
```

first(n) = Vec((2 - 3*x)/((1 - x)*(1 - 2*x)) + O(x^n)) \\ Iain Fox, Dec 31 2017

def A000051(n): return (1<Chai Wah Wu, Dec 21 2022

a(n) = 2*a(n-1) - 1 = 3*a(n-1) - 2*a(n-2).
G.f.: (2-3*x)/((1-x)*(1-2*x)).
First differences of A052944. - Emeric Deutsch, Mar 04 2004
a(0) = 1, then a(n) = (Sum_{i=0..n-1} a(i)) - (n-2). - Gerald McGarvey, Jul 10 2004
Inverse binomial transform of A007689. Also, V sequence in Lucas sequence L(3, 2). - Ross La Haye, Feb 07 2005
a(n) = A127904(n+1) for n>0. - Reinhard Zumkeller, Feb 05 2007
Equals binomial transform of [2, 1, 1, 1, ...]. - Gary W. Adamson, Apr 23 2008
a(n) = A000079(n)+1. - Omar E. Pol, May 18 2008
E.g.f.: exp(x) + exp(2*x). - Mohammad K. Azarian, Jan 02 2009
a(n) = A024036(n)/A000225(n). - Reinhard Zumkeller, Feb 14 2009
From Peter Luschny, Apr 20 2009: (Start)
A weighted binomial sum of the Bernoulli numbers A027641/A027642 with A027641(1)=1 (which amounts to the definition B_{n} = B_{n}(1)).
a(n) = Sum_{k=0..n} C(n,k)*B_{n-k}*2^(k+1)/(k+1). (See also A052584.) (End)
a(n) is the a(n-1)-th odd number for n >= 1. - Jaroslav Krizek, Apr 25 2009
From Reinhard Zumkeller, Feb 28 2010: (Start)
a(n)*A000225(n) = A000225(2*n).
a(n) = A173786(n,0). (End)
If p[i]=Fibonacci(i-4) 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 08 2010
a(n+2) = a(n) + a(n+1) + A000225(n). - Ivan N. Ianakiev, Jun 24 2012
a(A006521(n)) mod A006521(n) = 0. - Reinhard Zumkeller, Jul 17 2014
a(n) = 3*A007583((n-1)/2) for n odd. - Eric W. Weisstein, Jul 17 2017
Sum_{n>=0} 1/a(n) = A323482. - Amiram Eldar, Nov 11 2020

A000302 Powers of 4: a(n) = 4^n.

Original entry on oeis.org

1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656

Offset: 0

N. J. A. Sloane

Same as Pisot sequences E(1, 4), L(1, 4), P(1, 4), T(1, 4). Essentially same as Pisot sequences E(4, 16), L(4, 16), P(4, 16), T(4, 16). See A008776 for definitions of Pisot sequences.
The convolution square root of this sequence is A000984, the central binomial coefficients: C(2n,n). - T. D. Noe, Jun 11 2002
With P(n) being the number of integer partitions of n, p(i) as the number of parts of the i-th partition of n, d(i) as the number of different parts of the i-th partition of n, m(i, j) 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)!) * 2^(n-1). - Thomas Wieder, May 18 2005
Sums of rows of the triangle in A122366. - Reinhard Zumkeller, Aug 30 2006
Hankel transform of A076035. - Philippe Deléham, Feb 28 2009
Equals the Catalan sequence: (1, 1, 2, 5, 14, ...), convolved with A032443: (1, 3, 11, 42, ...). - Gary W. Adamson, May 15 2009
Sum of coefficients of expansion of (1 + x + x^2 + x^3)^n.
a(n) is number of compositions of natural numbers into n parts less than 4. For example, a(2) = 16 since there are 16 compositions of natural numbers into 2 parts less than 4.
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 4-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Squares in A002984. - Reinhard Zumkeller, Dec 28 2011
Row sums of Pascal's triangle using the rule that going left increases the value by a factor of k = 3. For example, the first three rows are {1}, {3, 1}, and {9, 6, 1}. Using this rule gives row sums as (k+1)^n. - Jon Perry, Oct 11 2012
First differences of A002450. - Omar E. Pol, Feb 20 2013
Sum of all peak heights in Dyck paths of semilength n+1. - David Scambler, Apr 22 2013
Powers of 4 exceed powers of 2 by A020522 which is the m-th oblong number A002378(m), m being the n-th Mersenne number A000225(n); hence, we may write, a(n) = A000079(n) + A002378(A000225(n)). - Lekraj Beedassy, Jan 17 2014
a(n) is equal to 1 plus the sum for 0 < k < 2^n of the numerators and denominators of the reduced fractions k/2^n. - J. M. Bergot, Jul 13 2015
Binomial transform of A000244. - Tony Foster III, Oct 01 2016
From Ilya Gutkovskiy, Oct 01 2016: (Start)
Number of nodes at level n regular 4-ary tree.
Partial sums of A002001. (End)
Satisfies Benford's law [Berger-Hill, 2011]. - N. J. A. Sloane, Feb 08 2017
Also the number of connected dominating sets in the (n+1)-barbell graph. - Eric W. Weisstein, Jun 29 2017
Side length of the cells at level n in a pyramid scheme where a square grid is decomposed into overlapping 2 X 2 blocks (cf. Kropatsch, 1985). - Felix Fröhlich, Jul 04 2019
a(n-1) is the number of 3-compositions of n; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020

H. W. Gould, Combinatorial Identities, 1972, eq. (1.93), p. 12.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, eq. (5.39), p. 187.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
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).
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

T. D. Noe, Table of n, a(n) for n = 0..100
Arno Berger and Theodore P. Hill, Benford's law strikes back: no simple explanation in sight for mathematical gem, The Mathematical Intelligencer 33.1 (2011): 85-91.
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Combinatorial Identities Associated with a Multidimensional Polynomial Sequence, J. Int. Seq., Vol. 21 (2018), Article 18.7.4.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
G. Dresden and Y. Li, Periodic Weighted Sums of Binomial Coefficients, arXiv:2210.04322 [math.NT], 2022.
R. Duarte and A. G. de Oliveira, Short note on the convolution of binomial coefficients, arXiv preprint arXiv:1302.2100 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.7.6.
Roudy El Haddad, Recurrent Sums and Partition Identities, arXiv:2101.09089 [math.NT], 2021.
Roudy El Haddad, A generalization of multiple zeta value. Part 1: Recurrent sums. Notes on Number Theory and Discrete Mathematics, 28(2), 2022, 167-199, DOI: 10.7546/nntdm.2022.28.2.167-199.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 5.
R. K. Guy, Letter to N. J. A. Sloane
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 8
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 269
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
Tanya Khovanova, Recursive Sequences
Craig Knecht, Number of tilings for a 6 sphinx tile repetitive unit.
Walter G. Kropatsch, A pyramid that grows by powers of 2, Pattern Recognition Letters, Vol. 3, No. 5 (1985), 315-322 [Subscription required].
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Robert Price, Comments on A000302 concerning Elementary Cellular Automata, Feb 26 2016.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Robert Schneider, Partition zeta functions, Research in Number Theory, 2(1):9., 2016.
Paul K. Stockmeyer, The Pascal Rhombus and the Stealth Configuration, arXiv preprint arXiv:1504.04404 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Barbell Graph
Eric Weisstein's World of Mathematics, Cantor Dust
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for "core" sequences
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (4).
Index entries for sequences related to Benford's law

Cf. A024036, A052539, A032443, A000351 (Binomial transform).
Cf. A249307.
Cf. A083420.

a000302 = (4 ^)
a000302_list = iterate (* 4) 1  -- Reinhard Zumkeller, Apr 04 2012

A000302 := n->4^n;
for n from 0 to 10 do sum(2^(n-j)*binomial(n+j,j),j=0..n); od; # Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007
A000302:=-1/(-1+4*z); # Simon Plouffe in his 1992 dissertation.

Table[4^n, {n, 0, 30}] (* Stefan Steinerberger, Apr 01 2006 *)
CoefficientList[Series[1/(1 - 4 x), {x, 0, 50}], x]  (* Vincenzo Librandi, May 29 2014 *)
NestList[4 # &, 1, 30] (* Harvey P. Dale, Mar 26 2015 *)
4^Range[0, 30] (* Eric W. Weisstein, Jun 29 2017 *)
LinearRecurrence[{4}, {1}, 31] (* Robert A. Russell, Nov 08 2018 *)

A000302(n):=4^n$ makelist(A000302(n),n,0,30); /* Martin Ettl, Oct 24 2012 */

A000302(n)=4^n \\ Michael B. Porter, Nov 06 2009

print([4**n for n in range(25)]) # Michael S. Branicky, Jan 04 2021

is_A000302 = lambda n: n.bit_count()==1 and n.bit_length()&1 # M. F. Hasler, Nov 25 2024

[4**n for n in range(0,25)] # Stefano Spezia, Jul 23 2025

(List.fill(20)(4: BigInt)).scanLeft(1: BigInt)( * ) // Alonso del Arte, Jun 22 2019

a(n) = 4^n.
a(0) = 1; a(n) = 4*a(n-1).
G.f.: 1/(1-4*x).
E.g.f.: exp(4*x).
a(n) = Sum_{k = 0..n} binomial(2k, k) * binomial(2(n - k), n - k). - Benoit Cloitre, Jan 26 2003 [See Graham et al., eq. (5.39), p. 187. - Wolfdieter Lang, Aug 16 2019]
1 = Sum_{n >= 1} 3/a(n) = 3/4 + 3/16 + 3/64 + 3/256 + 3/1024, ...; with partial sums: 3/4, 15/16, 63/64, 255/256, 1023/1024, ... - Gary W. Adamson, Jun 16 2003
a(n) = A001045(2*n) + A001045(2*n+1). - Paul Barry, Apr 27 2004
A000005(a(n)) = A005408(n+1). - Reinhard Zumkeller, Mar 04 2007
a(n) = Sum_{j = 0..n} 2^(n - j)*binomial(n + j, j). - Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007
Hankel transform of A115967. - Philippe Deléham, Jun 22 2007
a(n) = 6*Stirling2(n+1, 4) + 6*Stirling2(n+1, 3) + 3*Stirling2(n+1, 2) + 1 = 2*Stirling2(2^n, 2^n - 1) + Stirling2(n+1, 2) + 1. - Ross La Haye, Jun 26 2008
a(n) = A159991(n)/A001024(n) = A047653(n) + A181765(n). A160700(a(n)) = A010685(n). - Reinhard Zumkeller, May 02 2009
a(n) = A188915(A006127(n)). - Reinhard Zumkeller, Apr 14 2011
a(n) = Sum_{k = 0..n} binomial(2*n+1, k). - Mircea Merca, Jun 25 2011
Sum_{n >= 1} Mobius(n)/a(n) = 0.1710822479183... - R. J. Mathar, Aug 12 2012
a(n) = Sum_{k = 0..n} binomial(2*k + x, k)*binomial(2*(n - k) - x, n - k) for every real number x. - Rui Duarte and António Guedes de Oliveira, Feb 16 2013
a(n) = 5*a(n - 1) - 4*a(n - 2). - Jean-Bernard François, Sep 12 2013
a(n) = (2*n+1) * binomial(2*n,n) * Sum_{j=0..n} (-1)^j/(2*j+1)*binomial(n,j). - Vaclav Kotesovec, Sep 15 2013
a(n) = A000217(2^n - 1) + A000217(2^n). - J. M. Bergot, Dec 28 2014
a(n) = (2^n)^2 = A000079(n)^2. - Doug Bell, Jun 23 2015
a(n) = A002063(n)/3 - A004171(n). - Zhandos Mambetaliyev, Nov 19 2016
a(n) = (1/2) * Product_{k = 0..n} (1 + (2*n + 1)/(2*k + 1)). - Peter Bala, Mar 06 2018
a(n) = A001045(n+1)*A001045(n+2) + A001045(n)^2. - Ezhilarasu Velayutham, Aug 30 2019
a(n) = denominator(zeta_star({2}(n + 1))/zeta(2*n + 2)) where zeta_star is the multiple zeta star values and ({2}_n) represents (2, ..., 2) where the multiplicity of 2 is n. - _Roudy El Haddad, Feb 22 2022
a(n) = 1 + 3*Sum_{k=0..n} binomial(2*n, n+k)*(k|9), where (k|9) is the Jacobi symbol. - Greg Dresden, Oct 11 2022
a(n) = Sum_{k = 0..n} binomial(2*n+1, 2*k) = Sum_{k = 0..n} binomial(2*n+1, 2*k+1). - Sela Fried, Mar 23 2023

Partially edited by Joerg Arndt, Mar 11 2010

A002450 a(n) = (4^n - 1)/3.

Original entry on oeis.org

0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 23456248059221, 93824992236885, 375299968947541

Offset: 0

N. J. A. Sloane

For n > 0, a(n) is the degree (n-1) "numbral" power of 5 (see A048888 for the definition of numbral arithmetic). Example: a(3) = 21, since the numbral square of 5 is 5(*)5 = 101(*)101(base 2) = 101 OR 10100 = 10101(base 2) = 21, where the OR is taken bitwise. - John W. Layman, Dec 18 2001
a(n) is composite for all n > 2 and has factors x, (3*x + 2*(-1)^n) where x belongs to A001045. In binary the terms greater than 0 are 1, 101, 10101, 1010101, etc. - John McNamara, Jan 16 2002
Number of n X 2 binary arrays with path of adjacent 1's from upper left corner to right column. - R. H. Hardin, Mar 16 2002
The Collatz-function iteration started at a(n), for n >= 1, will end at 1 after 2*n+1 steps. - Labos Elemer, Sep 30 2002 [corrected by Wolfdieter Lang, Aug 16 2021]
Second binomial transform of A001045. - Paul Barry, Mar 28 2003
All members of sequence are also generalized octagonal numbers (A001082). - Matthew Vandermast, Apr 10 2003
Also sum of squares of divisors of 2^(n-1): a(n) = A001157(A000079(n-1)), for n > 0. - Paul Barry, Apr 11 2003
Binomial transform of A000244 (with leading zero). - Paul Barry, Apr 11 2003
Number of walks of length 2n between two vertices at distance 2 in the cycle graph C_6. For n = 2 we have for example 5 walks of length 4 from vertex A to C: ABABC, ABCBC, ABCDC, AFABC and AFEDC. - Herbert Kociemba, May 31 2004
Also number of walks of length 2n + 1 between two vertices at distance 3 in the cycle graph C_12. - Herbert Kociemba, Jul 05 2004
a(n+1) is the number of steps that are made when generating all n-step random walks that begin in a given point P on a two-dimensional square lattice. To make one step means to mark one vertex on the lattice (compare A080674). - Pawel P. Mazur (Pawel.Mazur(AT)pwr.wroc.pl), Mar 13 2005
a(n+1) is the sum of square divisors of 4^n. - Paul Barry, Oct 13 2005
a(n+1) is the decimal number generated by the binary bits in the n-th generation of the Rule 250 elementary cellular automaton. - Eric W. Weisstein, Apr 08 2006
a(k) = [M^k]2,1, where M is the 3 X 3 matrix defined as follows: M = [1, 1, 1; 1, 3, 1; 1, 1, 1]. - _Simone Severini, Jun 11 2006
a(n-1) / a(n) = percentage of wasted storage if a single image is stored as a pyramid with a each subsequent higher resolution layer containing four times as many pixels as the previous layer. n is the number of layers. - Victor Brodsky (victorbrodsky(AT)gmail.com), Jun 15 2006
k is in the sequence if and only if C(4k + 1, k) (A052203) is odd. - Paul Barry, Mar 26 2007
This sequence also gives the number of distinct 3-colorings of the odd cycle C(2*n - 1). - Keith Briggs, Jun 19 2007
All numbers of the form m*4^m + (4^m-1)/3 have the property that they are sums of two squares and also their indices are the sum of two squares. This follows from the identity m*4^m + (4^m-1)/3 = 4(4(..4(4m + 1) + 1) + 1) + 1 ..) + 1. - Artur Jasinski, Nov 12 2007
For n > 0, terms are the numbers that, in base 4, are repunits: 1_4, 11_4, 111_4, 1111_4, etc. - Artur Jasinski, Sep 30 2008
Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 5, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = charpoly(A,1). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 3, 4; 2) = A(0, 1; 4, 0; 1) 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
6*a(n) + 1 is every second Mersenne number greater than or equal to M3, hence all Mersenne primes greater than M2 must be a 6*a(n) + 1 of this sequence. - Roderick MacPhee, Nov 01 2010
Smallest number having alternating bit sum n. Cf. A065359.
For n = 1, 2, ..., the last digit of a(n) is 1, 5, 1, 5, ... . - Washington Bomfim, Jan 21 2011
Rule 50 elementary cellular automaton generates this sequence. This sequence also appears in the second column of array in A173588. - Paul Muljadi, Jan 27 2011
Sequence found by reading the line from 0, in the direction 0, 5, ... and the line from 1, in the direction 1, 21, ..., in the square spiral whose edges are the Jacobsthal numbers A001045 and whose vertices are the numbers A000975. These parallel lines are two semi-diagonals in the spiral. - Omar E. Pol, Sep 10 2011
a(n), n >= 1, is also the inverse of 3, denoted by 3^(-1), Modd(2^(2*n - 1)). For Modd n see a comment on A203571. E.g., a(2) = 5, 3 * 5 = 15 == 1 (Modd 8), because floor(15/8) = 1 is odd and -15 == 1 (mod 8). For n = 1 note that 3 * 1 = 3 == 1 (Modd 2) because floor(3/2) = 1 and -3 == 1 (mod 2). The inverse of 3 taken Modd 2^(2*n) coincides with 3^(-1) (mod 2^(2*n)) given in A007583(n), n >= 1. - Wolfdieter Lang, Mar 12 2012
If an AVL tree has a leaf at depth n, then the tree can contain no more than a(n+1) nodes total. - Mike Rosulek, Nov 20 2012
Also, this is the Lucas sequence V(5, 4). - Bruno Berselli, Jan 10 2013
Also, for n > 0, a(n) is an odd number whose Collatz trajectory contains no odd number other than n and 1. - Jayanta Basu, Mar 24 2013
Sum_{n >= 1} 1/a(n) converges to (3*(log(4/3) - QPolyGamma[0, 1, 1/4]))/log(4) = 1.263293058100271... = A321873. - K. G. Stier, Jun 23 2014
Consider n spheres in R^n: the i-th one (i=1, ..., n) has radius r(i) = 2^(1-i) and the coordinates of its center are (0, 0, ..., 0, r(i), 0, ..., 0) where r(i) is in position i. The coordinates of the intersection point in the positive orthant of these spheres are (2/a(n), 4/a(n), 8/a(n), 16/a(n), ...). For example in R^2, circles centered at (1, 0) and (0, 1/2), and with radii 1 and 1/2, meet at (2/5, 4/5). - Jean M. Morales, May 19 2015
From Peter Bala, Oct 11 2015: (Start)
a(n) gives the values of m such that binomial(4*m + 1,m) is odd. Cf. A003714, A048716, A263132.
2*a(n) = A020988(n) gives the values of m such that binomial(4*m + 2, m) is odd.
4*a(n) = A080674(n) gives the values of m such that binomial(4*m + 4, m) is odd. (End)
Collatz Conjecture Corollary: Except for powers of 2, the Collatz iteration of any positive integer must eventually reach a(n) and hence terminate at 1. - Gregory L. Simay, May 09 2016
Number of active (ON, black) cells at stage 2^n - 1 of the two-dimensional cellular automaton defined by "Rule 598", based on the 5-celled von Neumann neighborhood. - Robert Price, May 16 2016
From Luca Mariot and Enrico Formenti, Sep 26 2016: (Start)
a(n) is also the number of coprime pairs of polynomials (f, g) over GF(2) where both f and g have degree n + 1 and nonzero constant term.
a(n) is also the number of pairs of one-dimensional binary cellular automata with linear and bipermutive local rule of neighborhood size n+1 giving rise to orthogonal Latin squares of order 2^m, where m is a multiple of n. (End)
Except for 0, 1 and 5, all terms are Brazilian repunits numbers in base 4, and so belong to A125134. For n >= 3, all these terms are composite because a(n) = {(2^n-1) * (2^n + 1)}/3 and either (2^n - 1) or (2^n + 1) is a multiple of 3. - Bernard Schott, Apr 29 2017
Given the 3 X 3 matrix A = [2, 1, 1; 1, 2, 1; 1, 1, 2] and the 3 X 3 unit matrix I_3, A^n = a(n)(A - I_3) + I_3. - Nicolas Patrois, Jul 05 2017
The binary expansion of a(n) (n >= 1) consists of n 1's alternating with n - 1 0's. Example: a(4) = 85 = 1010101_2. - Emeric Deutsch, Aug 30 2017
a(n) (n >= 1) is the viabin number of the integer partition [n, n - 1, n - 2, ..., 2, 1] (for the definition of viabin number see comment in A290253). Example: a(4) = 85 = 1010101_2; consequently, the southeast border of the Ferrers board of the corresponding integer partition is ENENENEN, where E = (1, 0), N = (0, 1); this leads to the integer partition [4, 3, 2, 1]. - Emeric Deutsch, Aug 30 2017
Numbers whose binary and Gray-code representations are both palindromes (i.e., intersection of A006995 and A281379). - Amiram Eldar, May 17 2021
Starting with n = 1 the sequence satisfies {a(n) mod 6} = repeat{1, 5, 3}. - Wolfdieter Lang, Jan 14 2022
Terms >= 5 are those q for which the multiplicative order of 2 mod q is floor(log_2(q)) + 2 (and which is 1 more than the smallest possible order for any q). - Tim Seuré, Mar 09 2024
The order of 2 modulo a(n) is 2*n for n >= 2. - Joerg Arndt, Mar 09 2024

			Apply Collatz iteration to 9: 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1.
Apply Collatz iteration to 27: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1. [Corrected by _Sean A. Irvine_ at the suggestion of Stephen Cornelius, Mar 04 2024]
a(5) = (4^5 - 1)/3 = 341 = 11111_4 = {(2^5 - 1) * (2^5 + 1)}/3 = 31 * 33/3 = 31 * 11. - _Bernard Schott_, Apr 29 2017

A. Fletcher, J. C. P. Miller, L. Rosenhead and L. J. Comrie, An Index of Mathematical Tables. Vols. 1 and 2, 2nd ed., Blackwell, Oxford and Addison-Wesley, Reading, MA, 1962, Vol. 1, p. 112.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 217.
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).

T. D. Noe, Table of n, a(n) for n = 0..200
Peter Bala, A characterization of A002450, A020988 and A080674.
Henry Bottomley, Illustration of initial terms
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 8.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J., 41 (1974), 305-318. (Annotated scanned copy)
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
C. Ernst and D. W. Sumners, The Growth of the Number of Prime Knots, Math. Proc. Cambridge Philos. Soc. 102, 303-315, 1987
Ernesto Estrada and José A. de la Peña, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, Alternating Sums in the Hosoya Polynomial Triangle, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).
Enrico Formenti and Luca Mariot, Exhaustive Generation of Linear Orthogonal CA, Automata 2023, Univ. Twente (Netherlands), see p. 22 of 38.
Mattia Fregola, Elementary Cellular Automata Rule 1 generating OEIS sequence A277799, A058896, A141725, A002450
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 373
Petro Kosobutskyy and Nataliia Nestor, On the mathematical model of the transformation of natural numbers by a function of a split type, Comp. Des. Sys. Theor. Practice (2024) Vol. 6, No. 2. See p. 7.
Petro Kosobutskyy, Anastasiia Yedyharova, and Taras Slobodzyan, From Newton's binomial and Pascal's triangle to Collatz's problem, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, 121-127.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
J. V. Leyendekkers and A.G. Shannon, Modular Rings and the Integer 3, Notes on Number Theory & Discrete Mathematics, 17 (2011), 47-51.
Luca Manzoni, Luca Mariot, and Giuliamaria Menara, Combinatorial Designs and Cellular Automata: A Survey, arXiv:2503.10320 [math.CO], 2025. See pp. 16, 27.
Luca Mariot, Cryptography by Cellular Automata, 2017.
Luca Mariot, Orthogonal labelings in de Bruijn graphs, IWOCA 2020 - Open Problems Session, Delft University of Technology (Netherlands).
Luca Mariot, Connections between Latin squares, Cellular Automata and Coprime Polynomials, Univ. Twente (Netherlands, 2023). See p. 16/37.
Luca Mariot and Enrico Formenti, The number of coprime/non-coprime pairs of polynomials over F_2 with degree n and nonzero constant term.
Luca Mariot, Enrico Formenti and Alberto Leporati, Constructing Orthogonal Latin Squares from Linear Cellular Automata. In: Exploratory papers of AUTOMATA 2016.
Luca Mariot, Maximilien Gadouleau, Enrico Formenti, and Alberto Leporati, Mutually Orthogonal Latin Squares based on Cellular Automata, arXiv:1906.08249 [cs.DM], 2019.
Luca Mariot, Counting Coprime Polynomials over Finite Fields with Formal Languages and Compositions of Natural Numbers, Univ. Twente (Netherlands 2023). See p. 11.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Mező István, Several Generating Functions for Second-Order Recurrence Sequences , JIS 12 (2009) 09.3.7.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Kalika Prasad, Munesh Kumari, Rabiranjan Mohanta, and Hrishikesh Mahato, The sequence of higher order Mersenne numbers and associated binomial transforms, arXiv:2307.08073 [math.NT], 2023.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 4.
A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913. - From _N. J. A. Sloane_, Jun 13 2012
T. N. Thiele, Interpolationsrechnung, Teubner, Leipzig, 1909, p. 35.
Eric Weisstein's World of Mathematics, Repunit, Rule 250, Prime Knot.
Wikipedia, Elementary cellular automaton
Wikipedia, Lucas sequence: Specific names.
Michael Williams, Collatz conjecture: an order isomorphic recursive machine, ResearchGate (2024). See pp. 8, 13.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Partial sums of powers of 4, A000302.
When converted to binary, this gives A094028.
Subsequence of A003714.
Primitive factors: A129735.
Cf. A000225, A002446, A006995, A007583, A018215, A020988, A024036, A047849, A048716, A080355, A080674, A112627, A113860, A139391, A155701, A156605, A160967, A163834, A163868, A178415, A263132, A281379, A347834.

List([0..25], n -> (4^n-1)/3); # Muniru A Asiru, Feb 18 2018

a002450 = (`div` 3) . a024036
a002450_list = iterate ((+ 1) . (* 4)) 0
-- Reinhard Zumkeller, Oct 03 2012

[ (4^n-1)/3: n in [0..25] ]; // Klaus Brockhaus, Oct 28 2008

[n le 2 select n-1 else 5*Self(n-1)-4*Self(n-2): n in [1..70]]; // Vincenzo Librandi, Jun 13 2015

[seq((4^n-1)/3,n=0..40)];
A002450:=1/(4*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, dropping the initial zero

Table[(4^n - 1)/3, {n, 0, 127}] (* Vladimir Joseph Stephan Orlovsky, Sep 29 2008 *)
LinearRecurrence[{5, -4}, {0, 1}, 30] (* Harvey P. Dale, Jun 23 2013 *)

makelist((4^n-1)/3, n, 0, 30); /* Martin Ettl, Nov 05 2012 */

PARI
```
a(n) = (4^n-1)/3;
```

my(z='z+O('z^40)); Vec(z/((1-z)*(1-4*z))) \\ Altug Alkan, Oct 11 2015

def A002450(n): return ((1<<(n<<1))-1)//3 # Chai Wah Wu, Jan 29 2023

((List.fill(20)(4: BigInt)).scanLeft(1: BigInt)( * )).scanLeft(0: BigInt)( + ) // Alonso del Arte, Sep 17 2019

From Wolfdieter Lang, Apr 24 2001: (Start)
a(n+1) = Sum_{m = 0..n} A060921(n, m).
G.f.: x/((1-x)*(1-4*x)). (End)
a(n) = Sum_{k = 0..n-1} 4^k; a(n) = A001045(2*n). - Paul Barry, Mar 17 2003
E.g.f.: (exp(4*x) - exp(x))/3. - Paul Barry, Mar 28 2003
a(n) = (A007583(n) - 1)/2. - N. J. A. Sloane, May 16 2003
a(n) = A000975(2*n)/2. - N. J. A. Sloane, Sep 13 2003
a(n) = A084160(n)/2. - N. J. A. Sloane, Sep 13 2003
a(n+1) = 4*a(n) + 1, with a(0) = 0. - Philippe Deléham, Feb 25 2004
a(n) = Sum_{i = 0..n-1} C(2*n - 1 - i, i)*2^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*3^k. - Paul Barry, Aug 20 2004
a(n) = center term in M^n * [1 0 0], where M is the 3 X 3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 0 0] = [A007583(n-1) a(n) A007583(n-1)]. E.g., a(4) = 85 since M^4 * [1 0 0] = [43 85 43] = [A007583(3) a(4) A007583(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = Sum_{k = 0..n, j = 0..n} C(n, j)*C(j, k)*A001045(j - k). - Paul Barry, Feb 15 2005
a(n) = Sum_{k = 0..n} C(n, k)*A001045(n-k)*2^k = Sum_{k = 0..n} C(n, k)*A001045(k)*2^(n-k). - Paul Barry, Apr 22 2005
a(n) = A125118(n, 3) for n > 2. - Reinhard Zumkeller, Nov 21 2006
a(n) = Sum_{k = 0..n} 2^(n - k)*A128908(n, k), n >= 1. - Philippe Deléham, Oct 19 2008
a(n) = Sum_{k = 0..n} A106566(n, k)*A100335(k). - Philippe Deléham, Oct 30 2008
If we define f(m, j, x) = Sum_{k = j..m} binomial(m, k)*stirling2(k, j)*x^(m - k) then a(n-1) = f(2*n, 4, -2), n >= 2. - Milan Janjic, Apr 26 2009
a(n) = A014551(n) * A001045(n). - R. J. Mathar, Jul 08 2009
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3) = 5*a(n-1) - 4*a(n-2), a(0) = 0, a(1) = 1, a(2) = 5. - Wolfdieter Lang, Oct 18 2010
a(0) = 0, a(n+1) = a(n) + 2^(2*n). - Washington Bomfim, Jan 21 2011
A036555(a(n)) = 2*n. - Reinhard Zumkeller, Jan 28 2011
a(n) = Sum_{k = 1..floor((n+2)/3)} C(2*n + 1, n + 2 - 3*k). - Mircea Merca, Jun 25 2011
a(n) = Sum_{i = 1..n} binomial(2*n + 1, 2*i)/3. - Wesley Ivan Hurt, Mar 14 2015
a(n+1) = 2^(2*n) + a(n), a(0) = 0. - Ben Paul Thurston, Dec 27 2015
a(k*n)/a(n) = 1 + 4^n + ... + 4^((k-1)*n). - Gregory L. Simay, Jun 09 2016
Dirichlet g.f.: (PolyLog(s, 4) - zeta(s))/3. - Ilya Gutkovskiy, Jun 26 2016
A000120(a(n)) = n. - André Dalwigk, Mar 26 2018
a(m) divides a(m*n), in particular: a(2*n) == 0 (mod 5), a(3*n) == 0 (mod 3*7), a(5*n) == 0 (mod 11*31), etc. - M. F. Hasler, Oct 19 2018
a(n) = 4^(n-1) + a(n-1). - Bob Selcoe, Jan 01 2020
a(n) = A178415(1, n) = A347834(1, n-1), arrays, for n >= 1.  - Wolfdieter Lang, Nov 29 2021
a(n) = A000225(2*n)/3. - John Keith, Jan 22 2022
a(n) = A080674(n) + 1 = A047849(n) - 1 = A163834(n) - 2 = A155701(n) - 3 = A163868(n) - 4 = A156605(n) - 7. - Ray Chandler, Jun 16 2023
From Peter Bala, Jul 23 2025: (Start)
The following are examples of telescoping products. Cf. A016153:
Product_{k = 1..2*n} 1 + 2^k/a(k+1) = a(n+1)/A007583(n) = (4^(n+1) - 1)/(2*4^n + 1).
Hence, Product_{k >= 1} 1 + 2^k/a(k+1) = 2.
Product_{k >= 1} 1 - 2^k/a(k+1) = 2/5, since 1 - 2^n/a(n+1) = b(n)/b(n-1), where b(n) = 2 - 3/(1 - 2^(n+1)).
Product_{k >= 1} 1 + (-2)^k/a(k+1) = 2/3, since 1 + (-2)^n/a(n+1) = c(n)/c(n-1), where c(n) = 2 - 1/(1 + (-2)^(n+1)).
Product_{k >= 1} 1 - (-2)^k/a(k+1) = 6/5, since 1 - (-2)^n/a(n+1) = d(n)/d(n-1), where d(n) = 2 - 1/(1 - (-2)^(n+1)). (End)

cp's OEIS Frontend

A064080 Zsigmondy numbers for a = 4, b = 1: Zs(n, 4, 1) is the greatest divisor of 4^n - 1^n (A024036) that is relatively prime to 4^m - 1^m for all positive integers m < n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A163912 Least common multiple of all cycle sizes in range [A000302(n-1)..A024036(n)] of permutation A163355/A163356.

Views

Author

Keywords

Crossrefs

A163910 Number of cycles in range [A000302(n-1)..A024036(n)] of permutation A163355/A163356.

Views

Author

Keywords

Crossrefs

A163911 Maximum cycle size in range [A000302(n-1)..A024036(n)] of permutation A163355/A163356.

Views

Author

Keywords

Crossrefs

A163914 Number of 3-cycles in range [A000302(n-1)..A024036(n)] of permutation A163355/A163356.

Views

Author

Keywords

Crossrefs

A163913 Number of integers i in range [A000302(n-1)..A024036(n)] of permutation A163355/A163356 with A163915(i)=i, but not A163355(i)=i.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

Extensions

A000051 a(n) = 2^n + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A000302 Powers of 4: a(n) = 4^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs