

A002450


a(n) = (4^n  1)/3.
(Formerly M3914 N1608)


292



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



OFFSET

0,3


COMMENTS

For n > 0, a(n) is the degree (n1) "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 Collatzfunction 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]
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 nstep random walks that begin in a given point P on a twodimensional 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 nth 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(n1) / 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 3colorings of the odd cycle C(2*n  1).  Keith Briggs, Jun 19 2007
All numbers of the form m*4^m + (4^m1)/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^m1)/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 semidiagonals 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 ith one (i=1, ..., n) has radius r(i) = 2^(1i) 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
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 twodimensional cellular automaton defined by "Rule 598", based on the 5celled von Neumann neighborhood.  Robert Price, May 16 2016
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 onedimensional 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^n1) * (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 Graycode 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


REFERENCES

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 AddisonWesley, 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).


LINKS



FORMULA

a(n+1) = Sum_{m = 0..n} A060921(n, m).
G.f.: x/((1x)*(14*x)). (End)
E.g.f.: (exp(4*x)  exp(x))/3.  Paul Barry, Mar 28 2003
a(n) = Sum_{i = 0..n1} 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(n1) a(n) A007583(n1)]. 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
If we define f(m, j, x) = Sum_{k = j..m} binomial(m, k)*stirling2(k, j)*x^(m  k) then a(n1) = f(2*n, 4, 2), n >= 2.  Milan Janjic, Apr 26 2009
a(n) = 4*a(n1) + a(n2)  4*a(n3) = 5*a(n1)  4*a(n2), a(0) = 0, a(1) = 1, a(2) = 5.  Wolfdieter Lang, Oct 18 2010
a(n) = Sum_{k = 1..floor((n+2)/3)} C(2*n + 1, n + 2  3*k).  Mircea Merca, Jun 25 2011
Dirichlet g.f.: (PolyLog(s, 4)  zeta(s))/3.  Ilya Gutkovskiy, Jun 26 2016
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^(n1) + a(n1).  Bob Selcoe, Jan 01 2020


EXAMPLE

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


MAPLE

[seq((4^n1)/3, n=0..40)];


MATHEMATICA

LinearRecurrence[{5, 4}, {0, 1}, 30] (* Harvey P. Dale, Jun 23 2013 *)


PROG

(Magma) [n le 2 select n1 else 5*Self(n1)4*Self(n2): n in [1..70]]; // Vincenzo Librandi, Jun 13 2015
(PARI) a(n) = (4^n1)/3;
(PARI) my(z='z+O('z^40)); Vec(z/((1z)*(14*z))) \\ Altug Alkan, Oct 11 2015
(Haskell)
a002450 = (`div` 3) . a024036
a002450_list = iterate ((+ 1) . (* 4)) 0
(Maxima) makelist((4^n1)/3, n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(Scala) ((List.fill(20)(4: BigInt)).scanLeft(1: BigInt)(_ * _)).scanLeft(0: BigInt)(_ + _) // Alonso del Arte, Sep 17 2019
(Python)


CROSSREFS

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


KEYWORD

nonn,easy,nice


AUTHOR



STATUS

approved



