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

Author

Simon Plouffe

Keywords

• nonn
• easy

Comments

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

References

• 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).

Links

• 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).

Crossrefs

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.

Programs

GAP

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

Haskell

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

Magma

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

Maple

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

Mathematica

(* 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 *)

PARI

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

PARI

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

PARI

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

PARI

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

Sage

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

Formula

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