A020988 -id:A020988 - cp's OEIS frontend

A007583 a(n) = (2^(2*n + 1) + 1)/3.

1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763, 699051, 2796203, 11184811, 44739243, 178956971, 715827883, 2863311531, 11453246123, 45812984491, 183251937963, 733007751851, 2932031007403, 11728124029611, 46912496118443, 187649984473771, 750599937895083

Offset: 0

Simon Plouffe

Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)-w(k), v(k+1)=u(k)-v(k)+w(k), w(k+1)=-u(k)+v(k)+w(k); let M(k)=Max(u(k),v(k),w(k)); then a(n)=M(2n)=M(2n-1). - Benoit Cloitre, Mar 25 2002
Also the number of words of length 2n generated by the two letters s and t that reduce to the identity 1 by using the relations ssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the dihedral group D6=C2xD3. - Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002
Binomial transform of A025192. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_6. Example: a(1)=3 because in the cycle ABCDEF we have three walks of length 3 between A and B: ABAB, ABCB and AFAB. - Emeric Deutsch, Apr 01 2004
Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - Artur Jasinski, Feb 09 2007
Prime numbers of the form 1+Sum[2^(2n-1)] are in A000979. Numbers x such that 1+Sum[2^(2n-1)] is prime for n=1,2,...,x is A127936. - Artur Jasinski, Feb 09 2007
Related to A024493(6n+1), A131708(6n+3), A024495(6n+5). - Paul Curtz, Mar 27 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-6, (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,2). - Milan Janjic, Feb 21 2010
Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Feb 28 2011
Numbers whose binary representation is "10" repeated (n-1) times with "11" appended on the end, n >= 1. For example 171 = 10101011 (2). - Omar E. Pol, Nov 22 2012
a(n) is the smallest number for which A072219(a(n)) = 2*n+1. - Ramasamy Chandramouli, Dec 22 2012
An Engel expansion of 2 to the base b := 4/3 as defined in A181565, with the associated series expansion 2 = b + b^2/3 + b^3/(3*11) + b^4/(3*11*43) + .... Cf. A007051. - Peter Bala, Oct 29 2013
The positive integer solution (x,y) of 3*x - 2^n*y = 1, n>=0, with smallest x is (a(n/2), 2) if n is even and (a((n-1)/2), 1) if n is odd. - Wolfdieter Lang, Feb 15 2014
The smallest positive number that requires at least n additions and subtractions of powers of 2 to be formed. See Puzzling StackExchange link. - Alexander Cooke Jul 16 2023

H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..170
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Cecilia Bebeacua, Toufik Mansour, Alexander Postnikov, and Simone Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Greg Bell, Austin Lawson, Neil Pritchard, and Dan Yasaki, On locally infinite Cayley graphs of the integers, arXiv preprint arXiv:1711.00809 [math.GT], 2017. See lambda_2.
Phillip G. Bradford, Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability, arXiv:1802.05239 [cs.DS], 2018.
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D, arXiv:1507.04803 [math.CO], 2015.
Ernesto Estrada and José A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013.
Ernesto Estrada and José A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 35.
Sungpyo Hong and Jin Ho Kwak, Regular fourfold coverings with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 893
Dmitry Kamenetsky, A magic grasshopper, Puzzling StackExchange, 2023.
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv preprint arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
Quynh Nguyen, Jean Pedersen, and Hien T. Vu, New Integer Sequences Arising From 3-Period Folding Numbers, Vol. 19 (2016), Article 16.3.1.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. also A006054, A006356, A005578, A075680.
Partial sums of A081294.
Cf. A002450, A004171, A007051, A083065, A083066, A083884.
Cf. A000978, A000979, A124400, A124401, A127936, A127955, A127956, A127957, A127958.
Cf. location of records in A007302.

List([0..25], n-> (2^(2*n+1) + 1)/3); # G. C. Greubel, Dec 25 2019

a007583 = (`div` 3) . (+ 1) . a004171
-- Reinhard Zumkeller, Jan 09 2013

[(2^(2*n+1) + 1)/3: n in [0..30] ]; // Vincenzo Librandi, Apr 28 2011

a[0]:=1:for n from 1 to 50 do a[n]:=4*a[n-1]-1 od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 22 2008, with correction by K. Spage, Aug 20 2014
A007583 := proc(n)
    (2^(2*n+1)+1)/3 ;
end proc: # R. J. Mathar, Feb 19 2015

(* From Michael De Vlieger, Aug 22 2016 *)
Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
NestList[4# -1 &, 1, 23]
Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)

a(n)=sum(k=-n\3,n\3,binomial(2*n+1,n+1+3*k))

a=1; for(n=1,23, print1(a,", "); a=bitor(a,3*a)) \\ K. Spage, Aug 20 2014

Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ Altug Alkan, Dec 08 2015

apply( {A007583(n)=2<<(2*n)\/3}, [0..25]) \\ M. F. Hasler, Nov 30 2021

[(2^(2*n+1) + 1)/3 for n in (0..25)] # G. C. Greubel, Dec 25 2019

a(n) = 2*A002450(n) + 1.
From Wolfdieter Lang, Apr 24 2001: (Start)
a(n) = Sum_{m = 0..n} A060920(n, m) = A002450(n+1) - 2*A002450(n).
G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
a(n) = 4*a(n-1) - 1, n > 0.
From Paul Barry, Mar 17 2003: (Start)
a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
a(n) = A001045(2n+1). (End)
a(n) = A020988(n-1) + 1 = A039301(n+1) - 1 = A083584(n-1) + 2. - Ralf Stephan, Jun 14 2003
a(0) = 1; a(n+1) = a(n) * 4 - 1. - Regis Decamps (decamps(AT)users.sf.net), Feb 04 2004 (correction to lead index by K. Spage, Aug 20 2014)
a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - Benoit Cloitre, Mar 25 2004
a(n) = 5*a(n-1) - 4*a(n-2). - Emeric Deutsch, Apr 01 2004
a(n) = 4^n - A001045(2*n). - Paul Barry, Apr 17 2004
a(n) = 2*(A001045(n))^2 + (A001045(n+1))^2. - Paul Barry, Jul 15 2004
a(n) = left and right terms in M^n * [1 1 1] where M = the 3X3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 1 1] = [a(n) A002450(n+1) a(n)] E.g. a(3) = 43 since M^n * [1 1 1] = [43 85 43] = [a(3) A002450(4) a(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = A072197(n) - A020988(n). - Creighton Dement, Dec 31 2004
a(n) = A139250(2^n). - Omar E. Pol, Feb 28 2011
a(n) = A193652(2*n+1). - Reinhard Zumkeller, Aug 08 2011
a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - Mircea Merca, Jan 28 2012
a(n) = 2^(2*(n+1)) - A072197(n). - Vladimir Pletser, Apr 12 2014
a(n) == 2*n + 1 (mod 3). Indeed, from Regis Decamps' formula (Feb 04 2004) we have a(i+1) - a(i) == -1 (mod 3), i= 0, 1, ..., n - 1. Summing, we have a(n) - 1 == -n (mod 3), and the formula follows. - Vladimir Shevelev, May 20 2015
For n > 0 a(n) = A133494(0) + 2 * (A133494(n) + Sum_{x = 1..n - 1}Sum_{k = 0..x - 1}(binomial(x - 1, k)*(A133494(k+1) + A133494(n-x+k)))). - J. Conrad, Dec 06 2015
a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - Bob Selcoe, Aug 21 2016
E.g.f.: (1 + 2*exp(3*x))*exp(x)/3. - Ilya Gutkovskiy, Aug 21 2016
A075680(a(n)) = 1, for n > 0. - Ralf Stephan, Jun 17 2025

A024036 a(n) = 4^n - 1.

Original entry on oeis.org

0, 3, 15, 63, 255, 1023, 4095, 16383, 65535, 262143, 1048575, 4194303, 16777215, 67108863, 268435455, 1073741823, 4294967295, 17179869183, 68719476735, 274877906943, 1099511627775, 4398046511103, 17592186044415, 70368744177663, 281474976710655

Offset: 0

N. J. A. Sloane

This sequence is the normalized length per iteration of the space-filling Peano-Hilbert curve. The curve remains in a square, but its length increases without bound. The length of the curve, after n iterations in a unit square, is a(n)*2^(-n) where a(n) = 4*a(n-1)+3. This is the sequence of a(n) values. a(n)*(2^(-n)*2^(-n)) tends to 1, the area of the square where the curve is generated, as n increases. The ratio between the number of segments of the curve at the n-th iteration (A015521) and a(n) tends to 4/5 as n increases. - Giorgio Balzarotti, Mar 16 2006
Numbers whose base-4 representation is 333....3. - Zerinvary Lajos, Feb 03 2007
From Eric Desbiaux, Jun 28 2009: (Start)
It appears that for a given area, a square n^2 can be divided into n^2+1 other squares.
It's a rotation and zoom out of a Cartesian plan, which creates squares with side
= sqrt( (n^2) / (n^2+1) ) --> A010503|A010532|A010541... --> limit 1,
and diagonal sqrt(2*sqrt((n^2)/(n^2+1))) --> A010767|... --> limit A002193.
(End)
Also the total number of line segments after the n-th stage in the H tree, if 4^(n-1) H's are added at the n-th stage to the structure in which every "H" is formed by 3 line segments. A164346 (the first differences of this sequence) gives the number of line segments added at the n-th stage. - Omar E. Pol, Feb 16 2013
a(n) is the cumulative number of segment deletions in a Koch snowflake after (n+1) iterations. - Ivan N. Ianakiev, Nov 22 2013
Inverse binomial transform of A005057. - Wesley Ivan Hurt, Apr 04 2014
For n > 0, a(n) is one-third the partial sums of A002063(n-1). - J. M. Bergot, May 23 2014
Also the cyclomatic number of the n-Sierpinski tetrahedron graph. - Eric W. Weisstein, Sep 18 2017

			G.f. = 3*x + 15*x^2 + 63*x^3 + 255*x^4 + 1023*x^5 + 4095*x^6 + ...

Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

Felix Fröhlich, Table of n, a(n) for n = 0..99
Alexander V. Kitaev, Meromorphic Solution of the Degenerate Third Painlevé Equation Vanishing at the Origin, Symmetry, Integrability and Geometry: Methods and Applications, Vol. 15 (2019), 046, 53 pages; arXiv preprint, arXiv:1809.00122 [math.CA], 2018-2019.
Eric Weisstein's World of Mathematics, Cyclomatic Number.
Eric Weisstein's World of Mathematics, Sierpinski Tetrahedron Graph.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000051, A000120, A000225, A000302, A002001, A002063, A002193, A002450, A005057, A010503, A010532, A010541, A010767, A015521, A020988, A027637 (partial products), A078904 (partial sums), A079978, A080674, A164346 (first differences), A178789, A179857, A248721.

a024036 = (subtract 1) . a000302
a024036_list = iterate ((+ 3) . (* 4)) 0
-- Reinhard Zumkeller, Oct 03 2012

A024036:=n->4^n-1; seq(A024036(n), n=0..30); # Wesley Ivan Hurt, Apr 04 2014

Array[4^# - 1 &, 50, 0] (* Vladimir Joseph Stephan Orlovsky, Nov 03 2009 *)
(* Start from Eric W. Weisstein, Sep 19 2017 *)
Table[4^n - 1, {n, 0, 20}]
4^Range[0, 20] - 1
LinearRecurrence[{5, -4}, {0, 3}, 20]
CoefficientList[Series[3 x/(1 - 5 x + 4 x^2), {x, 0, 20}], x]
(* End *)

for(n=0, 100, print1(4^n-1, ", ")) \\ Felix Fröhlich, Jul 04 2014

[gaussian_binomial(2*n,1, 2) for n in range(21)] # Zerinvary Lajos, May 28 2009

[stirling_number2(2*n+1, 2) for n in range(21)] # Zerinvary Lajos, Nov 26 2009

a(n) = 3*A002450(n). - N. J. A. Sloane, Feb 19 2004
G.f.: 3*x/((-1+x)*(-1+4*x)) = 1/(-1+x) - 1/(-1+4*x). - R. J. Mathar, Nov 23 2007
E.g.f.: exp(4*x) - exp(x). - Mohammad K. Azarian, Jan 14 2009
a(n) = A000051(n)*A000225(n). - Reinhard Zumkeller, Feb 14 2009
A079978(a(n)) = 1. - Reinhard Zumkeller, Nov 22 2009
a(n) = A179857(A000225(n)), for n > 0; a(n) > A179857(m), for m < A000225(n). - Reinhard Zumkeller, Jul 31 2010
a(n) = 4*a(n-1) + 3, with a(0) = 0. - Vincenzo Librandi, Aug 01 2010
A000120(a(n)) = 2*n. - Reinhard Zumkeller, Feb 07 2011
a(n) = (3/2)*A020988(n). - Omar E. Pol, Mar 15 2012
a(n) = (Sum_{i=0..n} A002001(i)) - 1 = A178789(n+1) - 3. - Ivan N. Ianakiev, Nov 22 2013
a(n) = n*E(2*n-1,1)/B(2*n,1), for n > 0, where E(n,x) denotes the Euler polynomials and B(n,x) the Bernoulli polynomials. - Peter Luschny, Apr 04 2014
a(n) = A000302(n) - 1. - Sean A. Irvine, Jun 18 2019
Sum_{n>=1} 1/a(n) = A248721. - Amiram Eldar, Nov 13 2020
a(n) = A080674(n) - A002450(n). - Elmo R. Oliveira, Dec 02 2023

More terms Wesley Ivan Hurt, Apr 04 2014

A020522 a(n) = 4^n - 2^n.

Original entry on oeis.org

0, 2, 12, 56, 240, 992, 4032, 16256, 65280, 261632, 1047552, 4192256, 16773120, 67100672, 268419072, 1073709056, 4294901760, 17179738112, 68719214592, 274877382656, 1099510579200, 4398044413952, 17592181850112, 70368735789056, 281474959933440

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of walks of length 2*n+2 between any two diametrically opposite vertices of the cycle graph C_8. - Herbert Kociemba, Jul 02 2004
If we consider a(4*k+2), then 2^4 == 3^4 == 3 (mod 13); 2^(4*k+2) + 3^(4*k+2) == 3^k*(4+9) == 3*0 == 0 (mod 13). So a(4*k+2) can never be prime. - Jose Brox, Dec 27 2005
If k is odd, then a(n*k) is divisible by a(n), since: a(n*k) = (2^n)^k + (3^n)^k = (2^n + 3^n)*((2^n)^(k-1) - (2^n)^(k-2) (3^n) + - ... + (3^n)^(k-1)). So the only possible primes in the sequence are a(0) and a(2^n) for n>=1. I've checked that a(2^n) is composite for 3 <= n <= 15. As with Fermat primes, a probabilistic argument suggests that there are only finitely many primes in the sequence. - Dean Hickerson, Dec 27 2005
Let x,y,z be elements from some power set P(n), i.e., the power set of a set of n elements. Define a function f(x,y,z) in the following manner: f(x,y,z) = 1 if x is a subset of y and y is a subset of z and x does not equal z; f(x,y,z) = 0 if x is not a subset of y or y is not a subset of z or x equals z. Now sum f(x,y,z) for all x,y,z of P(n). This gives a(n). - Ross La Haye, Dec 26 2005
Number of monic (irreducible) polynomials of degree 1 over GF(2^n). - Max Alekseyev, Jan 13 2006
Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then a(n) = the number of (x,y) of B for which x does not equal y. - Ross La Haye, Jan 02 2008
For n>1: central terms of the triangle in A173787. - Reinhard Zumkeller, Feb 28 2010
Pronic numbers of the form: (2^n - 1)*2^n, which is the n-th Mersenne number times 2^n, see A000225 and A002378. - Fred Daniel Kline, Nov 30 2013
Indices where records of A037870 occur. - Philippe Beaudoin, Sep 03 2014
Half the total edge length for a minimum linear arrangement of a hypercube of dimension n. (See Harper's paper below for proof). - Eitan Frachtenberg, Apr 07 2017
Number of pairs in GF(2)^{n+1} whose dot product is 1. - Christopher Purcell, Dec 11 2021

			n=5: a(5) = 4^5 - 2^5 = 1024 - 32 = 992 -> '1111100000'.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Tom Copeland, The Kervaire-Milnor formula
John Elias, Illustration of initial terms: Twin 2^n hexagonal numbers
L. H. Harper, Optimal Assignment of Numbers to Vertices, J. SIAM 12(1), p. 131--135, March 1964; alternative link.
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.
The Sixtieth William Lowell Putnam Mathematical Competition, Question A6, Amer. Math. Monthly 107 (Oct 2000), 721-732; see p. 725.
Index entries for linear recurrences with constant coefficients, signature (6,-8).

Ratio of successive terms of A028365.
Cf. A000225, A060867, A161168, A006516, A059153, A065442.
Cf. A000079, A265736, A020988, A047849.
Cf. A000079, A000302.

a020522 = (* 2) . a006516  -- Reinhard Zumkeller, Dec 15 2015

[4^n - 2^n: n in [0..60]]; // Vincenzo Librandi, Apr 26 2011

A020522:=n->4^n-2^n; seq(A020522(n), n=0..50); # Wesley Ivan Hurt, Nov 29 2013

Table[4^n - 2^n, {n, 40}] (* or *) LinearRecurrence[{6, -8}, {0, 2}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2012 *)

a(n)=4^n-2^n \\ Charles R Greathouse IV, Jan 30 2012

def A020522(n): return (1<Chai Wah Wu, Mar 10 2025

[4^n - 2^n for n in range(0,23)] # Zerinvary Lajos, Jun 05 2009

From Herbert Kociemba, Jul 02 2004: (Start)
G.f.: 2*x/((-1 + 2*x)*(-1 + 4*x)).
a(n) = 6*a(n-1) - 8*a(n-2). (End)
E.g.f.: exp(4*x) - exp(2*x). - Mohammad K. Azarian, Jan 14 2009
From Reinhard Zumkeller, Feb 07 2006, Jaroslav Krizek, Aug 02 2009: (Start)
a(n) = A099393(n)-A000225(n+1) = A083420(n)-A099393(n).
In binary representation, n>0: n 1's followed by n 0's (A138147(n)).
A000120(a(n)) = n.
A023416(a(n)) = n.
A070939(a(n)) = 2*n.
2*a(n)+1 = A030101(A099393(n)). (End)
a(n) = A085812(n) - A001700(n). - John Molokach, Sep 28 2013
a(n) = 2*A006516(n) = A000079(n)*A000225(n) = A265736(A000225(n)). - Reinhard Zumkeller, Dec 15 2015
a(n) = (4^(n/2) - 4^(n/4))*(4^(n/2) + 4^(n/4)). - Bruno Berselli, Apr 09 2018
Sum_{n>0} 1/a(n) = E - 1, where E is the Erdős-Borwein constant (A065442). - Peter McNair, Dec 19 2022
a(n) = A000302(n) - A000079(n). - John Reimer Morales, Aug 04 2025

A047849 a(n) = (4^n + 2)/3.

Original entry on oeis.org

1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542

Offset: 0

Clark Kimberling

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143). - Vincent Vatter, Aug 17 2009; minor correction by Henning Ulfarsson, May 14 2017
This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - Bruno Berselli, Jul 27 2010, Mar 02 2012
For n >= 2, a(n) equals 2^n times the permanent of the (2n-2) X (2n-2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
For n > 0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex. - David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is an odd integer <= 2^n, there exists a unique integer in the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
   a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - Paul M. Bradley, Jun 04 2023
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561. - _Wolfdieter Lang_, Nov 08 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000
Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.
Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171-183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *)

PARI
```
a(n)=(4^n+2)/3;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
From Henry Bottomley, Aug 29 2000: (Start)
a(n) = (4^n + 2)/3.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, ... (3^n/3 + 2*0^n/3). a(n) = A078008(2n). - Paul Barry, Mar 14 2004
G.f.: (1-3*x)/((1-x)*(1-4*x)). - Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006
a(n) = (A001045(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
Sum_{i=0..n} a(i) = A073724(n). (End)
For n >= 3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n - 2)*{1, 1, 2}*{1, 1, 2}. - John M. Campbell, Jul 09 2011
a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 2, 6, 10, 26, 42, 106, 170, 426, 682, 1706, 2730, 6826, 10922, 27306, 43690, 109226, 174762, 436906, 699050, 1747626, 2796202, 6990506, 11184810, 27962026, 44739242, 111848106, 178956970, 447392426, 715827882, 1789569706, 2863311530, 7158278826

Offset: 0

Emeric Deutsch, May 16 2001

Or, number of permutations with no fixed points avoiding 213 and 132.
Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - Emeric Deutsch, Dec 08 2004
Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - Creighton Dement, May 09 2005
Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008
Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010
a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - Abdullahi Umar, Dec 28 2010
a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011
For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - K D Pegrume, Jan 26 2022
Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - Ed Pegg Jr, Dec 27 2022

			a(4)=6 because the only 132 and 213-avoiding permutations of {1,2,3,4} without fixed points are: 2341, 3412, 3421, 4123, 4312 and 4321.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. Al-Kharousi, R. Kehinde and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
J. Brillhart and P. Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
Emeric Deutsch, Derangements That Don't Rise Too Fast: 10902, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
K. Dilcher and K. B. Stolarsky, Stern polynomials and double-limit continued fractions, Acta Arithmetica 140 (2009), 119-134
R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Cf. A000166, A020988, A020989, A068018.
Cf. A177993. - Gary W. Adamson, May 16 2010
Cf. A183158, A183159. - Abdullahi Umar, Dec 28 2010
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), this sequence (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 31 2011

[(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // Vincenzo Librandi, Aug 13 2011

A061547:=n->ceil(abs((3/8)*2^n +(1/24)*(-2)^n - 2/3)); seq(A061547(n), n=1..30); # Wesley Ivan Hurt, Apr 03 2014

f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* Robert G. Wilson v, Aug 13 2011 *)

a(n)=(3/8)*2^n+(1/24)*(-2)^n-2/3 \\ Charles R Greathouse IV, Sep 24 2015

a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.
a(n) = 4*a(n-2) + 2, a(0)=1, a(1)=0, a(2)=1.
G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).
a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .
a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - Paul Curtz, Jun 15 2008
a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.
a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.
a(n+2) = Sum_{k=0..n} A144464(n,k)^2 = Sum_{k=0..n} A152716(n,k). - Philippe Deléham and Michel Marcus, Feb 26 2014
a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - Yosu Yurramendi, Dec 23 2016
a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - Yosu Yurramendi, Jan 03 2017
a(n+2) = 2*A086893(n), n > 0. - Yosu Yurramendi, Mar 07 2017
E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - Stefano Spezia, Apr 07 2022

a(0)=1 prepended by Alois P. Heinz, Jan 27 2022

A072197 a(n) = 4*a(n-1) + 1 with a(0) = 3.

Original entry on oeis.org

3, 13, 53, 213, 853, 3413, 13653, 54613, 218453, 873813, 3495253, 13981013, 55924053, 223696213, 894784853, 3579139413, 14316557653, 57266230613, 229064922453, 916259689813, 3665038759253, 14660155037013, 58640620148053, 234562480592213, 938249922368853, 3752999689475413

Offset: 0

N. Rathankar (rathankar(AT)yahoo.com), Jul 03 2002

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 - 1) = (-1)^n*charpoly(A, -2). - Milan Janjic, Jan 26 2010
Numbers whose binary representation is 11 together with n times 01. For example, 213 = 11010101 (2). - Omar E. Pol, Nov 22 2012
The Collatz-function starting with a(n) will terminate at 1 after 2*n + 7 steps. This is because 3*a(n) + 1 = 5*2^(2n + 1), and the Collatz-function starting with 5 terminates at 1 after 5 additional steps.  So for example, a(2) = 53; Collatz sequence starting with 53 follows: 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (11 steps). - Bob Selcoe, Apr 03 2015
a(n) is also the sum of the numerator and denominator of the binary fractions 0.1, 0.101, 0.10101, 0.1010101... Thus 0.1 = 1/2 with 1 + 2 = 3, 0.101 = 1/2 + 1/8 = 5/8 with 5 + 8 = 13; 0.10101 = 1/2 + 1/8 + 1/32 = 21/32 with 21 + 32 = 53. - J. M. Bergot, Sep 28 2016
a(n), for n >= 2, is also the smallest odd number congruent to 5 modulo 8 for which the modified reduced Collatz map given in A324036 has n consecutive extra steps compared to the reduced Collatz map given in A075677. - Nicolas Vaillant, Philippe Delarue, Wolfdieter Lang, May 09 2019

			a(1) = 13 because a(0) = 3 and 4 * 3 + 1 = 13.
a(2) = 53 because a(1) = 13 and 4 * 13 + 1 = 53.
a(3) = 213 because a(2) = 53 and 4 * 53 + 1 = 213.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Petro Kosobutskyy and Volodymyr Karkulovskyy, Recurrence and structuring of sequences of transformations 3n+ 1 as arguments for confirmation of the Collatz hypothesis, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, pp. 28-33. See p. 29.
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, pp. 121-127.
Index entries for linear recurrences with constant coefficients, signature (5,-4).
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000302, A002066 (first differences), A002450, A007583, A020988, A075677, A178415, A324036, A347834.

[(10*4^n-1)/3: n in [0..30]]; // Vincenzo Librandi, Oct 31 2011

A072197:=n->(10*4^n - 1)/3: seq(A072197(n), n=0..30); # Wesley Ivan Hurt, Sep 29 2016

Table[(10(4^n) - 1)/3, {n, 0, 19}] (* Alonso del Arte, Nov 22 2012 *)
NestList[4#+1&,3,30] (* Harvey P. Dale, Mar 09 2019 *)

a(n)=10*4^n\3 \\ Charles R Greathouse IV, Apr 06 2016

Vec((3-2*x)/((1-x)*(1-4*x)) + O(x^30)) \\ Colin Barker, Sep 28 2016

a(n) = (10*4^n - 1)/3 = 10*A002450(n) + 3. - Henry Bottomley, Dec 02 2002
a(n) = 5*a(n-1) - 4*a(n-2), n > 1. - Vincenzo Librandi, Oct 31 2011
a(n) = 2^(2*(n + 1)) - (2^(2*n + 1) + 1)/3 = A000302(n + 1) - A007583(n). - Vladimir Pletser, Apr 12 2014
a(n) = (5*2^(2*n + 1) - 1)/3. - Bob Selcoe, Apr 03 2015
G.f.: (3-2*x)/((1-x)*(1-4*x)). - Colin Barker, Sep 28 2016
a(n) = A020988(n) + A020988(n+1) + 1 = 2*(A002450(n) + A002450(n+1)) + 1. - Yosu Yurramendi, Jan 24 2017
a(n) = A002450(n+1) + 2^(2*n+1). - Adam Michael Bere, May 13 2021
a(n) = a(n-1) + 5*2^(2*n-1), for n >= 1, with a(0) = 3. - Wolfdieter Lang, Aug 16 2021
a(n) = A178415(2,n+1) = A347834(2,n), arrays, for n >= 0. - Wolfdieter Lang, Nov 29 2021
E.g.f.: exp(x)*(10*exp(3*x) - 1)/3. - Elmo R. Oliveira, Apr 02 2025

More terms from Henry Bottomley, Dec 02 2002

A020989 a(n) = (5*4^n - 2)/3.

Original entry on oeis.org

1, 6, 26, 106, 426, 1706, 6826, 27306, 109226, 436906, 1747626, 6990506, 27962026, 111848106, 447392426, 1789569706, 7158278826, 28633115306, 114532461226, 458129844906, 1832519379626, 7330077518506, 29320310074026, 117281240296106, 469124961184426

Offset: 0

N. J. A. Sloane

Let Zb[n](x) = polynomial in x whose coefficients are the corresponding digits of index n in base b. Then Z2[(5*4^k-2)/3](1/tau) = 1. - Marc LeBrun, Mar 01 2001
a(n)=number of derangements of [2n+2] with runs consisting of consecutive integers. E.g., a(1)=6 because the derangements of {1,2,3,4} with runs consisting of consecutive integers are 4|123, 34|12, 4|3|12, 4|3|2|1, 234|1 and 34|2|1 (the bars delimit the runs). - Emeric Deutsch, May 26 2003
Sum of n-th row of triangle of powers of 4: 1; 1 4 1; 1 4 16 4 1; 1 4 16 64 16 4 1; ... - Philippe Deléham, Feb 22 2014

			a(0) = 1;
a(1) = 1 + 4 + 1 = 6;
a(2) = 1 + 4 + 16 + 4 + 1 = 26;
a(3) = 1 + 4 + 16 + 64 + 16 + 4 + 1 = 106; etc. - _Philippe Deléham_, Feb 22 2014

Clifford A. Pickover, A Passion for Mathematics, John Wiley & Sons, Inc., 2005, at pp. 104 and 311 (for "Mr. Zanti's ants").

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John Brillhart and Patrick Morton, Über Summen von Rudin-Shapiroschen Koeffizienten, Illinois Journal of Mathematics, volume 22, issue 1, 1978, pages 126-148. See Satz 9(a) page 132 and Satz 21 page 144 m_k = a(k).
John Brillhart and Patrick Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869, see page 858 m_k = a(k).
Kevin Ryde, Iterations of the Alternate Paperfolding Curve, see index "m_k".
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A002450, A020988, A112468.

A column of A119726.

[(5*4^n-2)/3: n in [0..25]]; // Vincenzo Librandi, Jul 24 2011

NestList[4#+2&,1,25] (* Harvey P. Dale, Jul 23 2011 *)

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

a(0) = 1, a(n) = 4*a(n-1) + 2; a(n) = a(n-1)+ 5*{4^(n-1)}; - Amarnath Murthy, May 27 2001
G.f.: (1+x)/((1-4*x)*(1-x)). - Zerinvary Lajos, Jan 11 2009; adapted to offset by Philippe Deléham, Feb 22 2014
a(n) = 5*a(n-1) - 4*a(n-2), a(0) = 1, a(1) = 6. - Philippe Deléham, Feb 22 2014
a(n) = Sum_{k=0..n} A112468(n,k)*5^k. - Philippe Deléham, Feb 22 2014
a(n) = (A020988(n) + A020988(n+1))/2. - Yosu Yurramendi, Jan 23 2017
a(n) = A002450(n) + A002450(n+1). - Yosu Yurramendi, Jan 24 2017
a(n) = 10*A020988(n-1) + 6. - Yosu Yurramendi, Feb 19 2017
E.g.f.: exp(x)*(5*exp(3*x) - 2)/3. - Stefano Spezia, Apr 10 2022

A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result.

Original entry on oeis.org

3, 12, 7, 24, 51, 28, 15, 48, 99, 204, 103, 56, 115, 60, 31, 96, 195, 396, 199, 408, 819, 412, 207, 112, 227, 460, 231, 120, 243, 124, 63, 192, 387, 780, 391, 792, 1587, 796, 399, 816, 1635, 3276, 1639, 824, 1651, 828, 415, 224, 451, 908, 455, 920, 1843, 924

Offset: 1

Leroy Quet, Dec 02 2009

A318921 expands the runs in a similar way, and A318921(a(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018
From Chai Wah Wu, Nov 18 2018: (Start)
Let f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e., the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 3 and f(1) = a(2) + a(3) = 19.
Then f(k) = 20*6^(k-1) - 2^(k-1) for k > 0.
Proof: by summing over the recurrence relations for a(n) (see formula section), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (6*a(2i) + 6*a(2i+1) + 4) = 6*f(k+1) + 2^(k+2). Solving this first-order recurrence relation with the initial condition f(1) = 19 shows that f(k) = 20*6^(k-1)-2^(k-1) for k > 0.
(End)

			6 in binary is 110. Increase each run by one digit to get 11100, which is 28 in decimal. So a(6) = 28.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.

Cf. A175047, A175048, A324127 (partial sums).
Cf. also A030308, A007088, A182512, A318921.
For records see A319422, A319423, A319424.

import Data.List (group)
a175046 = foldr (\b v -> 2 * v + b) 0 .
          concatMap (\bs@(b:_) -> b : bs) . group . a030308_row
-- Reinhard Zumkeller, Jul 05 2013

a[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;
Array[a, 60] (* Jean-François Alcover, Nov 12 2018 *)

A175046(n)={for(i=2,#n=binary (n*2+bittest (n,0)),n[i]!=n[i-1]&&n[i-1]*=[1,1]);fromdigits(concat(n),2)} \\ M. F. Hasler, Sep 08 2018

from re import split
def A175046(n):
    return int(''.join(d+'1' if '1' in d else d+'0' for d in split('(0+)|(1+)',bin(n)[2:]) if d != '' and d != None),2) # Chai Wah Wu, Sep 24 2018

def a(n):
    b = bin(n)[2:]
    return int(b.replace("01", "001").replace("10", "110") + b[-1], 2)
print([a(n) for n in range(1, 55)]) # Michael S. Branicky, Dec 07 2021

2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2). - M. F. Hasler, Sep 08 2018
a(n) <= (9*n^2 + 12*n)/5, with equality iff n = (2/3)*(4^k-1) = A182512(k) for some k, i.e., n = 10101...10 in binary. - Conjectured by N. J. A. Sloane, Sep 09 2018, proved by M. F. Hasler, Sep 12 2018
From M. F. Hasler, Sep 12 2018: (Start)
Proof of N. J. A. Sloane's formula: For given (binary) length L(n) = floor(log_2(n)+1), the length of a(n) is maximal, L(a(n)) = 2*L(n), if and only if n's bits are alternating, i.e., n in A020988 (if even) or in A002450 (if odd).
For n = A020988(k) (= k times '10' in base 2) = (4^k - 1)*2/3, one has a(n) = A108020(k) (= k times '1100' in base 2) = (16^k - 1)*4/5. This yields a(n)/n = (4^k + 1)*6/5 = (n*9 + 12)/5, i.e., the given upper bound.
For n = A002450(k) = (4^k - 1)/3, one gets a(n) = A182512(k) = (16^k - 1)/5, whence a(n)/n = (4^k + 1)*3/5 = (n*9 + 6)/5, smaller than the bound.
If L(a(n)) < 2 L(n) - 1, then log_2(a(n)) < floor(log_2(a(n))+1) = L(a(n)) <= 2*L(n) - 2 = 2*floor(log_2(n)+1)-2 = 2*floor(log_2(n)) <= 2*log_2(n), whence a(n) < n^2.
It remains to consider the case L(a(n)) = 2 L(n) - 1. There are two possibilities:
If n = 10..._2, then n >= 2^(L(n)-1) and a(n) = 1100..._2 < 1101_2 * 2^(L(a(n))-4) = 13*2^(2*L(n)-5), so a(n)/n^2 < 13*2^(-5+2) = 13/8 = 1.625 < 9/5 = 1.8.
If n = 11..._2, then n >= 3*2^(L(n)-2) and a(n) = 111..._2 < 2^L(a(n)) = 2^(2*L(n)-1), so a(n)/n^2 < 2^(-1+4)/9 = 8/9 < 1 < 9/5.
This shows that a(n)/n^2 <= 9/5 + 12/(5*n) always holds, with equality iff n is in A020988; and a(n)/n^2 < 13/8 if n is not in A020988 or A002450. (End)
From M. F. Hasler, Sep 10 2018: (Start)
Right inverse of A318921: A318921 o A175046 = id (= A001477).
a(A020988(k)) = A108020(k); a(A002450(k)) = A182512(k); a(A000225(k)) = A000225(k+1) (achieves the lower bound a(n) >= 2n + 1) for all k >= 0. (End)
From David A. Corneth, Sep 20 2018: (Start)
a(4*k)   = 2*a(2*k).
a(4*k+1) = 4*a(2*k) + 3.
a(4*k+2) = 4*a(2*k+1).
a(4*k+3) = 2*a(2*k+1) + 1. (End)

Extended by Ray Chandler, Dec 18 2009

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

Original entry on oeis.org

1, 2, 4, 10, 20, 42, 84, 170, 340, 682, 1364, 2730, 5460, 10922, 21844, 43690, 87380, 174762, 349524, 699050, 1398100, 2796202, 5592404, 11184810, 22369620, 44739242, 89478484, 178956970, 357913940, 715827882, 1431655764, 2863311530, 5726623060

Offset: 0

Clark Kimberling

Number of moves to solve Chinese rings puzzle.
a(n-1) (with a(0):=0) enumerates all sequences of length m=1,2,...,floor(n/2) with nonzero integer entries n_i satisfying sum |n_i| <= n-m. Rephrasing K. A. Meissner's example p. 6. Example n=4: from length m=1: [1], [2], [3], each in 2 signed versions; from m=2: [1,1] in 2^2 = 4 signed versions. Hence a(3) = a(4-1) = 3*2 + 1*4 = 10.
Also the number of different 3-colorings (out of 4 colors) for the vertices of all triangulated planar polygons on a base with n+1 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Mar 23 2010
For n > 0, also the total distance that the disks travel from the leftmost peg to the rightmost peg in the Tower of Hanoi puzzle, in the unique solution with 2^n-1 moves (see links). - Sela Fried, Dec 17 2023

Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019.
Sela Fried, Economically solving the Tower of Hanoi puzzle.
Nicolas Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, arXiv preprint arXiv:1711.10906 [cs.DM], 2017.
Lee Hae-hwang, Illustration of initial terms in terms of rosemary plants
Krzysztof A. Meissner, Black hole entropy in Loop Quantum Gravity, arXiv:gr-qc/0407052, 2004.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Row sums of A026637.
For n >= 1, equals twice A000975, also A001045 - 1.
A167030 is an essentially identical sequence.

[n eq 0 select 1 else (2^(n+2) -3-(-1)^n)/3 : n in [0..40]]; // G. C. Greubel, Jun 28 2024

f:=n-> if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3; fi;

Join[{1}, Floor[(2^Range[3, 40] - 2)/3]] (* or *) LinearRecurrence[{2,1,-2},{1,2,4,10},40] (* Vladimir Joseph Stephan Orlovsky, Jan 29 2012 *)
CoefficientList[Series[(1-x^2+2x^3)/((1-x)(1-x-2x^2)),{x,0,1001}],x] (* Vincenzo Librandi, Apr 04 2012 *)

Vec((1-x^2+2*x^3)/(1-x)/(1-x-2*x^2)+O(x^99)) \\ Charles R Greathouse IV, Apr 04 2012

def A026644(n): return ((4<Chai Wah Wu, Apr 17 2025

[(2^(n+2)-3-(-1)^n)/3 + int(n==0) for n in range(41)] # G. C. Greubel, Jun 28 2024

a(2*k) = 2*a(2*k-1), a(2*k+1) = 2*a(2*k) + 2. - Peter Shor, Apr 11 2002
For n>0: a(n+1) = a(n) + 2*b(n+1) + 4*b(n), where b(k) = A001045(k). - N. J. A. Sloane, May 16 2003
For n>0: if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3. - Richard Hess
a(2*n) = 2*n-1 + Sum_{k=0..2*n-1} a(k), n>0; a(2*n+1) = 2*n+1 + Sum_{k=0..n} a(k). - Lee Hae-hwang, Sep 17 2002; corrected by R. J. Mathar, Oct 21 2008
a(n) = 2*n + 2*Sum_{k=1..n-2} a(k), n>0. - Lee Hae-hwang, Sep 19 2002; corrected by R. J. Mathar, Oct 21 2008
From Paul Barry, Oct 24 2007: (Start)
G.f.: (1 - x^2 + 2*x^3)/((1 - x)*(1 - x - 2*x^2)).
a(n) = J(n+2) - 1 + 0^n, where J(n) = A001045(n) (Jacobsthal numbers).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
a(n) = 0^n + Sum_{k=0..n} (2 - 2*0^(n-k))*J(k+1). (End)
a(n) = A052953(n+1) - 2, n>0. [Moved from A020988, R. J. Mathar, Oct 21 2008]
a(n) = floor(A097074(n+1)/2), n>0. - Gary Detlefs, Dec 19 2010
a(n) = A169969(2*n-1) - 1, n>=2; a(n) = 3*2^(n-1) - 1 - A169969(2*n-7), n>=5 . - Yosu Yurramendi, Jul 05 2016
a(n+3) = 3*2^(n+2) - 2 - a(n), n>=1, a(1)=2, a(2)=4, a(3)=10 . - Yosu Yurramendi, Jul 05 2016
a(n) + A084170(n) = 3*2^n - 2, n>=1. - Yosu Yurramendi, Jul 05 2016
E.g.f: (3 - 4*cosh(x) + 4*cosh(2*x) - 2*sinh(x) + 4*sinh(2*x))/3. - Ilya Gutkovskiy, Jul 05 2016
a(n+3) = 9*2^n + A084170(n), n>=0. - Yosu Yurramendi, Jul 07 2016
a(n) = A000975(n+1) - A000035(n+1), n>0, a(0)=1. - Yuchun Ji, Aug 05 2020

Recurrence in definition line found by Lee Hae-hwang, Apr 03 2002

A053985 Replace 2^k with (-2)^k in binary expansion of n.

Original entry on oeis.org

0, 1, -2, -1, 4, 5, 2, 3, -8, -7, -10, -9, -4, -3, -6, -5, 16, 17, 14, 15, 20, 21, 18, 19, 8, 9, 6, 7, 12, 13, 10, 11, -32, -31, -34, -33, -28, -27, -30, -29, -40, -39, -42, -41, -36, -35, -38, -37, -16, -15, -18, -17, -12, -11, -14, -13, -24, -23, -26, -25, -20, -19

Offset: 0

Henry Bottomley, Apr 03 2000

Base 2 representation for n (in lexicographic order) converted from base -2 to base 10.
Maps natural numbers uniquely onto integers; within each group of positive values, maximum is in A002450; a(n)=n iff n can be written only with 1's and 0's in base 4 (A000695).
a(n) = A004514(n) - n. - Reinhard Zumkeller, Dec 27 2003
Schroeppel gives formula n = (a(n) + b) XOR b where b = binary ...101010, and notes this formula is reversible.  The reverse a(n) = (n XOR b) - b is a bit twiddle to transform 1 bits to -1.  Odd position 0 or 1 in n is flipped by "XOR b" to 1 or 0, then "- b" gives 0 or -1.  Only odd position 1's are changed, so b can be any length sure to cover those. - Kevin Ryde, Jun 26 2020

			a(9)=-7 because 9 is written 1001 base 2 and (-2)^3 + (-2)^0 = -8 + 1 = -7.
Or by Schroeppel's formula, b = binary 1010 then a(9) = (1001 XOR 1010) - 1010 = decimal -7. - _Kevin Ryde_, Jun 26 2020

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972, item 128 by Schroeppel, page 62. Also HTML transcription. Figure 7 path drawn 0, 1, -2, -1, 4, ... is the present sequence.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 45, 49.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Inverse of A005351. Cf. A039724, A007088, A065369, A073791, A073792, A073793, A073794, A073795, A073796 and A073835.

f[n_Integer, b_Integer] := Block[{l = IntegerDigits[n]}, Sum[l[[ -i]]*(-b)^(i - 1), {i, 1, Length[l]}]]; a = Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 80}]; b = {}; Do[b = Append[b, f[a[[n]], 2]], {n, 1, 80}]; b
(* Second program: *)
Array[FromDigits[IntegerDigits[#, 2], -2] &, 62, 0] (* Michael De Vlieger, Jun 27 2020 *)

a(n) = fromdigits(binary(n), -2) \\ Rémy Sigrist, Sep 01 2018

def A053985(n): return  -(b:=int('10'*(n.bit_length()+1>>1),2)) + (n^b) if n else 0 # Chai Wah Wu, Nov 18 2022

From Ralf Stephan, Jun 13 2003: (Start)
G.f.: (1/(1-x)) * Sum_{k>=0} (-2)^k*x^2^k/(1+x^2^k).
a(0) = 0, a(2*n) = -2*a(n), a(2*n+1) = -2*a(n)+1. (End)
a(n) = Sum_{k>=0} A030308(n,k)*A122803(k). - Philippe Deléham, Oct 15 2011
a(n) = (n XOR b) - b where b = binary ..101010 [Schroeppel].  Any b of this form (A020988) with bitlength(b) >= bitlength(n) suits. - Kevin Ryde, Jun 26 2020

cp's OEIS Frontend

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

A024036 a(n) = 4^n - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Sage

Formula

Extensions

A020522 a(n) = 4^n - 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A047849 a(n) = (4^n + 2)/3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs