A141725 -id:A141725 - cp's OEIS frontend

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

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)

A001576 a(n) = 1^n + 2^n + 4^n.

Original entry on oeis.org

3, 7, 21, 73, 273, 1057, 4161, 16513, 65793, 262657, 1049601, 4196353, 16781313, 67117057, 268451841, 1073774593, 4295032833, 17180000257, 68719738881, 274878431233, 1099512676353, 4398048608257, 17592190238721, 70368752566273, 281474993487873, 1125899940397057

Offset: 0

N. J. A. Sloane

Equals A135576, except for the first term. - Omar E. Pol, Nov 18 2008
Conjecture: For n > 1, if a(n) = 1^n + 2^n + 4^n is a prime number then n is of the form 3^h. For example, for h=1, n=3, a(n) = 1^3 + 2^3 + 4^3 = 73 (prime); for h=2, n=9, a(n) = 1^9 + 2^9 + 4^9 = 262657 (prime); for h=3, n=27, a(n) is not prime. - Vincenzo Librandi, Aug 03 2010
The previous conjecture was proved by Golomb in 1978. See A051154. - T. D. Noe, Aug 15 2010
Another more elementary proof can be found in Liu link. - Bernard Schott, Mar 08 2019
Fills in one quarter section of the figurate form of the Sierpinski square curve. See illustration in links and A141725. - John Elias, Mar 29 2023

T. D. Noe, Table of n, a(n) for n = 0..200
John Elias, Illustration of Initial Terms: 1/4 Sierpinski Square Curve
Andy Liu, West German Mathematical Olympiad 1982 - Second round, Problem 4, Crux Mathematicorum, p. 105, Vol. 12, May. 86.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Subsequence of A002061.
Cf. A001550, A034513, A001579, A074501-A074580, A135576, A135577.
See also comments in A051154.
Cf. A006095, A022166.

Mathematica
```
Table[1^n + 2^n + 4^n, {n, 0, 24}]
```

a(n)=1+2^n+4^n \\ Charles R Greathouse IV, Jun 10 2011

[sigma(4,n)for n in range(0,23)] # Zerinvary Lajos, Jun 04 2009

a(n) = 6*a(n-1) - 8*a(n-2) + 3.
O.g.f.: -1/(-1+x) - 1/(-1+2*x) - 1/(-1+4*x) = ( -3+14*x-14*x^2 ) / ( (x-1)*(2*x-1)*(4*x-1) ). - R. J. Mathar, Feb 29 2008
E.g.f.: e^x + e^(2*x) + e^(4*x). - Mohammad K. Azarian, Dec 26 2008
a(n) = A024088(n)/A000225(n). - Reinhard Zumkeller, Feb 15 2009
Exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + 7*x + 35*x^2 + 155*x^3 + ... is the o.g.f. for the 2nd subdiagonal of triangle A022166, essentially A006095. - Peter Bala, Apr 07 2015

A188161 a(n) = 2*4^n + 3.

Original entry on oeis.org

5, 11, 35, 131, 515, 2051, 8195, 32771, 131075, 524291, 2097155, 8388611, 33554435, 134217731, 536870915, 2147483651, 8589934595, 34359738371, 137438953475, 549755813891, 2199023255555, 8796093022211, 35184372088835, 140737488355331, 562949953421315, 2251799813685251

Offset: 0

Brad Clardy, Mar 22 2011

For n > 0, binary representation of a(n) is 1X11 where X is 2*n-1 zeros.

Number of conjugacy classes in Suzuki group Sz(2*4^n). - Eric M. Schmidt, Apr 18 2013

			The first seven terms written in binary are 101, 1011, 100011, 10000011, 1000000011, 100000000011, and 10000000000011.

Bruno Berselli, Table of n, a(n) for n = 0..1000
Frank Luebeck, Numbers of Conjugacy Classes in Finite Groups of Lie Type.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A141725 (4^(n+1)-3), A224790.

[2*4^n+3: n in [1..100]]; // Vincenzo Librandi, Mar 29 2011
(Decimal BASIC)
FOR n=0 TO 1000
   PRINT n; 2*4^n+3
NEXT n
END ! /* Bruno Berselli, Apr 28 2011 */

2 4^Range[0,30]+3  (* Harvey P. Dale, Apr 02 2011 *)

a(n)=2*4^n+3 \\ Charles R Greathouse IV, Jul 02 2013

a(n) = A141725(n) - 2*A141725(n-1) for n > 0.
G.f.: (5-14*x)/((1-4*x)*(1-x)). - R. J. Mathar, Apr 09 2011
a(n) = 5*a(n-1) - 4*a(n-2). - Joerg Arndt, Apr 09 2011
From Felix P. Muga II, Mar 19 2014: (Start)
a(n) = a(n-1) + 6*4^(n-1) for n > 0, a(0)=5.
a(n) = a(n-1) + 12*a(n-2) - 36 for n > 1, a(0)=5, a(1)=11. (End)
E.g.f.: exp(x)*(2*exp(3*x) + 3). - Elmo R. Oliveira, Mar 08 2025

A100402 Digital root of 4^n.

Original entry on oeis.org

1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7

Offset: 0

Cino Hilliard, Dec 31 2004

Equals A141725 mod 9. - Paul Curtz, Sep 15 2008
Sequence is the digital root of A016777. - Odimar Fabeny, Sep 13 2010
Digital root of the powers of any number congruent to 4 mod 9. - Alonso del Arte, Jan 26 2014
Period 3: repeat [1, 4, 7]. - Wesley Ivan Hurt, Aug 26 2014
From Timothy L. Tiffin, Dec 02 2023: (Start)
The period 3 digits of this sequence are the same as those of A070403 (digital root of 7^n) but the order is different: [1, 4, 7] vs. [1, 7, 4].
The digits in this sequence appear in the decimal expansions of the following rational numbers: 49/333, 490/333, 4900/333, .... (End)

			4^2 = 16, digitalroot(16) = 7, the third entry.

Cecil Balmond, Number 9: The Search for the Sigma Code. Munich, New York: Prestel (1998): 203.

Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. Digital roots of powers of c mod 9: c = 2, A153130; c = 5, A070366; c = 7, A070403; c = 8, A010689.

Cf. A000302, A001022, A009966, A009975, A009984, A010872, A010888, A070403, A087752, A121013, A141725, A016777.

Table[PowerMod[4, n, 9], {n, 0, 100}] (* Timothy L. Tiffin, Dec 03 2023 *)
StringRepeat["1, 4, 7, ", 100] (* Timothy L. Tiffin, Dec 03 2023 *)

a(n)=[1,4,7][1+n%3]; \\ Joerg Arndt, Aug 26 2014

[power_mod(4, n, 9) for n in range(0, 105)] # Zerinvary Lajos, Nov 25 2009

a(n) = 4^n mod 9. - Zerinvary Lajos, Nov 25 2009
From R. J. Mathar, Apr 13 2010: (Start)
a(n) = a(n-3) for n>2.
G.f.: (1+4*x+7*x^2)/ ((1-x)*(1+x+x^2)). (End)
a(n) = A010888(A000302(n)). - Michel Marcus, Aug 25 2014
a(n) = 3*A010872(n) + 1. - Robert Israel, Aug 25 2014
a(n) = 4 - 3*cos(2*n*Pi/3) - sqrt(3)*sin(2*n*Pi/3). - Wesley Ivan Hurt, Jun 30 2016
a(n) = A153130(2n). - Timothy L. Tiffin, Dec 01 2023
a(n) = A010888(A001022(n)) = A010888(A009966(n)) = A010888(A009975(n)) = A010888(A009984(n)) = A010888(A087752(n)) = A010888(A121013(n)). - Timothy L. Tiffin, Dec 02 2023
a(n) = A010888(4*a(n-1)). - Stefano Spezia, Mar 20 2025

A101622 A Horadam-Jacobsthal sequence.

Original entry on oeis.org

0, 1, 6, 13, 30, 61, 126, 253, 510, 1021, 2046, 4093, 8190, 16381, 32766, 65533, 131070, 262141, 524286, 1048573, 2097150, 4194301, 8388606, 16777213, 33554430, 67108861, 134217726, 268435453, 536870910, 1073741821, 2147483646, 4294967293, 8589934590

Offset: 0

Paul Barry, Dec 10 2004

Companion sequence to A084639.
This is the sequence A(0,1;1,2;5) 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
Except for the initial three terms, the decimal representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Mar 27 2017
Named after the Australian mathematician Alwyn Francis Horadam (1923-2016) and the German mathematician Ernst Jacobsthal (1882-1965). - Amiram Eldar, Jun 10 2021

Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. F. Horadam, Jacobsthal Representation Numbers, Fib Quart., Vol. 34, No. 1 (1996), pp. 40-54.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences. [_Wolfdieter Lang_, Oct 18 2010]
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
Stephen Wolfram, A New Kind of Science.
Wolfram Research, Wolfram Atlas of Simple Programs.
Index entries for sequences related to cellular automata.
Index to 2D 5-Neighbor Cellular Automata.
Index to Elementary Cellular Automata.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A131953.

[(2^(n+2)+(-1)^n-5)/2: n in [0..35]]; // Vincenzo Librandi, Aug 12 2011

LinearRecurrence[{2,1,-2},{0,1,6},40] (* Harvey P. Dale, Jul 08 2014 *)

concat(0, Vec(x*(1+4*x)/((1-x)*(1+x)*(1-2*x)) + O(x^30))) \\ Colin Barker, Mar 28 2017

a(n) = (2^(n+2) + (-1)^n - 5)/2.
G.f.: x*(1+4*x)/((1-x)*(1+x)*(1-2*x)).
a(n) = (A014551(n+2)-5)/2.
(1, 6, 13, 30, 61, ...) are the row sums of A131953. - Gary W. Adamson, Jul 31 2007
From Paul Curtz, Jan 01 2009: (Start)
a(n) = a(n-1) + 2*a(n-2) + 5.
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
a(n) = A000079(n+1) - A010693(n).
a(n+1) = A141722(n) + 5 = A141722(n) + A010716(n).
a(2n+1) - a(2n) = 1, 7, 31, ... = A083420.
a(2n+1) - 2*a(2n) = 1.
a(2n) = A002446 = 6*A002450, a(2n+1) = A141725. (End)
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) for n>2. - Colin Barker, Mar 28 2017
a(n) = (1/2) * Sum_{k=1..n} binomial(n+1,k) * (2+(-1)^k). - Wesley Ivan Hurt, Sep 23 2017

A253208 a(n) = 4^n + 3.

Original entry on oeis.org

4, 7, 19, 67, 259, 1027, 4099, 16387, 65539, 262147, 1048579, 4194307, 16777219, 67108867, 268435459, 1073741827, 4294967299, 17179869187, 68719476739, 274877906947, 1099511627779, 4398046511107, 17592186044419, 70368744177667, 281474976710659

Offset: 0

Vincenzo Librandi, Dec 29 2014

Subsequence of A226807.

Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A141725, A226807.

Cf. Numbers of the form k^n+k-1: A000057 (k=2), A168607 (k=3), this sequence (k=4), A242329 (k=5), A253209 (k=6), A253210 (k=7), A253211 (k=8), A253212 (k=9), A253213 (k=10).

Magma
```
[4^n+3: n in [0..30]];
```

Table[4^n + 3, {n, 0, 30}] (* or *) CoefficientList[Series[(4 - 13 x) / ((1 - x) (1 - 4 x)), {x, 0, 40}], x]

a(n)=4^n+3 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (4 - 13*x)/((1 - x)*(1 - 4*x)).
a(n) = 5*a(n-1) - 4*a(n-2) for n > 1.
From Elmo R. Oliveira, Nov 14 2023: (Start)
a(n) = 4*a(n-1) - 9 with a(0) = 4.
E.g.f.: exp(4*x) + 3*exp(x). (End)

A277799 Decimal representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 1", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 0, 1, 12, 1, 60, 1, 252, 1, 1020, 1, 4092, 1, 16380, 1, 65532, 1, 262140, 1, 1048572, 1, 4194300, 1, 16777212, 1, 67108860, 1, 268435452, 1, 1073741820, 1, 4294967292, 1, 17179869180, 1, 68719476732, 1, 274877906940, 1, 1099511627772, 1, 4398046511100, 1

Offset: 0

Robert Price, Oct 31 2016

Initialized with a single black (ON) cell at stage zero.

Rule numbers 1, 9, 17, 25, 257, 265, 273 and 281 all generate this sequence.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..126
Mattia Fregola, Elementary Cellular Automata Rule 1 generating OEIS sequence A277799, A058896, A141725, A002450
Robert Price, Diagrams of first 20 stages
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A277797, A277798, A277800.

CAStep[rule_,a_]:=Map[rule[[10-#]]&,ListConvolve[{{0,2,0},{2,1,2},{0,2,0}},a,2],{2}];
code=1; stages=128;
rule=IntegerDigits[code,2,10];
g=2*stages+1; (* Maximum size of grid *)
a=PadLeft[{{1}},{g,g},0,Floor[{g,g}/2]]; (* Initial ON cell on grid *)
ca=a;
ca=Table[ca=CAStep[rule,ca],{n,1,stages+1}];
PrependTo[ca,a];
(* Trim full grid to reflect growth by one cell at each stage *)
k=(Length[ca[[1]]]+1)/2;
ca=Table[Table[Part[ca[[n]][[j]],Range[k+1-n,k-1+n]],{j,k+1-n,k-1+n}],{n,1,k}];
Table[FromDigits[Part[ca[[i]][[i]],Range[1,i]],2], {i,1,stages-1}]

Conjectures from Colin Barker, Nov 01 2016: (Start)
G.f.: (1 - 4*x^2 + 12*x^3) / ((1 - x)*(1 + x)*(1 - 2*x)*(1 + 2*x)).
a(n) = 5*a(n-2) - 4*a(n-4) for n>3.
a(n) = (-3/2-(-2)^n+(5*(-1)^n)/2+2^n). (End)

A058896 a(n) = 4^n - 4.

Original entry on oeis.org

-3, 0, 12, 60, 252, 1020, 4092, 16380, 65532, 262140, 1048572, 4194300, 16777212, 67108860, 268435452, 1073741820, 4294967292, 17179869180, 68719476732, 274877906940, 1099511627772, 4398046511100, 17592186044412, 70368744177660, 281474976710652, 1125899906842620

Offset: 0

Henry Bottomley, Jan 08 2001

Harry J. Smith, Table of n, a(n) for n = 0..500
Mattia Fregola, Elementary Cellular Automata Rule 1 generating OEIS sequence A277799, A058896, A141725, A002450
Index entries for linear recurrences with constant coefficients, signature (5, -4).

Cf. A000302, A000918, A002450, A024036, A052548, A058809, A141725, A277799.

List([0..25],n->4^n-4); # Muniru A Asiru, Mar 09 2018

seq(4^n-4,n=0..25); # Muniru A Asiru, Mar 09 2018

Array[4^# - 4 &, 26, 0]  (* Michael De Vlieger, Feb 18 2018 *)

a(n) = { 4^n - 4 } \\ Harry J. Smith, Jun 23 2009

a(n) = A000302(n) - 4 = 4*a(n-1) + 12 = 4*A024036(n-1) = 12*A002450(n-1).
G.f.: 3*(5*x - 1)/(1 - x)/(1 - 4*x).
a(n) = A000918(n)*A052548(n). - Reinhard Zumkeller, Feb 14 2009
From Elmo R. Oliveira, Nov 16 2023 (Start)
a(n) = 5*a(n-1) - 4*a(n-2) for n > 1.
E.g.f.: exp(4*x) - 4*exp(x). (End)

A193871 Square array T(n,k) = k^n - k + 1 read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 25, 13, 1, 1, 31, 79, 61, 21, 1, 1, 63, 241, 253, 121, 31, 1, 1, 127, 727, 1021, 621, 211, 43, 1, 1, 255, 2185, 4093, 3121, 1291, 337, 57, 1, 1, 511, 6559, 16381, 15621, 7771, 2395, 505, 73, 1, 1, 1023, 19681, 65533, 78121, 46651, 16801, 4089, 721, 91, 1

Offset: 1

Omar E. Pol, Aug 21 2011

The columns give 1^n-0, 2^n-1, 3^n-2, 4^n-3, 5^n-4, etc.

The main diagonal gives A006091, which is a sequence related to the famous "coconuts" problem.

			Array begins:
  1,   1,    1,     1,     1,    1,    1,   1,   1,   1
  1,   3,    7,    13,    21,   31,   43,  57,  73
  1,   7,   25,    61,   121,  211,  337, 505
  1,  15,   79,   253,   621, 1291, 2395
  1,  31,  241,  1021,  3121, 7771
  1,  63,  727,  4093, 15621
  1, 127, 2185, 16381
  1, 255, 6559
  1, 511
  1

M. B. Richardson, A Needlessly Complicated and Unhelpful Solution to Ben Ames Williams' Coconuts Problem, The Winnower, 3 (2016), e147175.52128. doi: 10.15200/winn.147175.52128

Row 1: A000012. Rows 2,3: A002061, A061600 but both without repetitions.
Columns 1..10: A000012, positives A000225, A058481, A141725, A164785, A164784, A164783, A164786, A177095, A170955.
Cf. A276135.

Table[k^# - k + 1 &[n - k + 1], {n, 11}, {k, n}] // Flatten (* Michael De Vlieger, Nov 16 2016 *)

A254076 a(n) = 2a(n-1) + a(n-2) - 2a(n-3) for n>2, a(0)=-1, a(1)=-2, a(2)=-4.

Original entry on oeis.org

-1, -2, -4, 1, 2, 13, 26, 61, 122, 253, 506, 1021, 2042, 4093, 8186, 16381, 32762, 65533, 131066, 262141, 524282, 1048573, 2097146, 4194301, 8388602, 16777213, 33554426, 67108861, 134217722, 268435453, 536870906, 1073741821, 2147483642, 4294967293

Offset: 0

Paul Curtz, Jan 29 2015

The main diagonal of the difference table is -A000079(n) = -2^n.
a(n) mod 9 is of period 6: repeat 8, 7, 5, 1, 2, 4.
a(n) + a(n+1) = -3, -6, -3, 3, 15, ...; all are multiples of 3.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A000079, A010704, A141725, A153130, A156067, A157823.

a[0] = -1; a[n_] := 2^(n-1) + 3*Mod[n, 2] - 6; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Feb 04 2015 *)

Vec((9*x^3+x^2-1)/((x-1)*(x+1)*(2*x-1)) + O(x^100)) \\ Colin Barker, Jan 30 2015

a(2n+1) = A141725(n-1), a(2n+2) = 2*a(2n+1).
a(n+1) = 2*a(n) + (period 2: repeat 0, 9), n>0.
a(n) = -A157823(n) - (period 2: repeat 6, 3).
a(n+1) = a(n) - A156067(n).
a(n+2) = a(n) +  3*2^(n-1), n>0.
a(n+4) = a(n) + 15*2^(n-1), n>0.
a(n+6) = a(n) + 63*2^(n-1), n>0.
a(n) = (2^n - 3*(-1)^n - 9)/2 for n>0. - Colin Barker, Jan 30 2015
G.f.: (9*x^3+x^2-1) / ((x-1)*(x+1)*(2*x-1)). - Colin Barker, Jan 30 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Scala

Formula

A001576 a(n) = 1^n + 2^n + 4^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A188161 a(n) = 2*4^n + 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A100402 Digital root of 4^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A101622 A Horadam-Jacobsthal sequence.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A253208 a(n) = 4^n + 3.

Views

Author

Keywords

Comments

A254076 a(n) = 2a(n-1) + a(n-2) - 2a(n-3) for n>2, a(0)=-1, a(1)=-2, a(2)=-4.