|
%I M2895 #216 Aug 02 2023 14:36:30
%S 1,3,11,43,171,683,2731,10923,43691,174763,699051,2796203,11184811,
%T 44739243,178956971,715827883,2863311531,11453246123,45812984491,
%U 183251937963,733007751851,2932031007403,11728124029611,46912496118443,187649984473771,750599937895083
%N a(n) = (2^(2*n + 1) + 1)/3.
%C 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
%C 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
%C Binomial transform of A025192. - _Paul Barry_, Apr 11 2003
%C 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
%C Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - _Artur Jasinski_, Feb 09 2007
%C 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
%C Related to A024493(6n+1), A131708(6n+3), A024495(6n+5). - _Paul Curtz_, Mar 27 2008
%C 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
%C Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - _Omar E. Pol_, Feb 28 2011
%C 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
%C a(n) is the smallest number for which A072219(a(n)) = 2*n+1. - _Ramasamy Chandramouli_, Dec 22 2012
%C 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
%C 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
%C 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
%D H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A007583/b007583.txt">Table of n, a(n) for n = 0..170</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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.]
%H C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, <a href="https://arxiv.org/abs/math/0506334">On the X-rays of permutations</a>, arXiv:math/0506334 [math.CO], 2005.
%H Greg Bell, A. Lawson, N. Pritchard, and D. Yasaki, <a href="https://arxiv.org/abs/1711.00809">On locally infinite Cayley graphs of the integers</a>, arXiv preprint arXiv:1711.00809 [math.GT], 2017. See lambda_2.
%H Phillip G. Bradford, <a href="https://arxiv.org/abs/1802.05239">Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability</a>, arXiv:1802.05239 [cs.DS], 2018.
%H J. R. Britnell and M. Wildon, <a href="https://arxiv.org/abs/1507.04803">Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D</a>, arXiv:1507.04803 [math.CO], 2015.
%H E. Estrada and J. A. de la Pena, <a href="http://arxiv.org/abs/1302.1176">From Integer Sequences to Block Designs via Counting Walks in Graphs</a>, arXiv preprint arXiv:1302.1176 [math.CO], 2013.
%H E. Estrada and J. A. de la Pena, <a href="http://www.nntdm.net/papers/nntdm-19/NNTDM-19-3-78-84.pdf">Integer sequences from walks in graphs</a>, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84
%H S. Hong and J. H. Kwak, <a href="http://dx.doi.org/10.1002/jgt.3190170509">Regular fourfold coverings with respect to the identity automorphism</a>, J. Graph Theory, 17 (1993), 621-627.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=893">Encyclopedia of Combinatorial Structures 893</a>
%H Dmitry Kamenetsky, <a href="https://puzzling.stackexchange.com/questions/121545/a-magic-grasshopper/">A magic grasshopper</a>, Puzzling StackExchange, 2023.
%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1404.2710">On Collatz' Words, Sequences and Trees</a>, arXiv preprint arXiv:1404.2710 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Lang/lang6.html">J. Int. Seq. 17 (2014) # 14.11.7</a>.
%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a> J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
%H Quynh Nguyen, Jean Pedersen, and Hien T. Vu, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Pedersen/pedersen2.html">New Integer Sequences Arising From 3-Period Folding Numbers</a>, Vol. 19 (2016), Article 16.3.1.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Repunit.html">Repunit</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-4).
%F a(n) = 2*A002450(n) + 1.
%F From _Wolfdieter Lang_, Apr 24 2001: (Start)
%F a(n) = Sum_{m = 0..n} A060920(n, m) = A002450(n+1) - 2*A002450(n).
%F G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
%F a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
%F a(n) = 4*a(n-1) - 1, n > 0.
%F From _Paul Barry_, Mar 17 2003: (Start)
%F a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
%F a(n) = A001045(2n+1). (End)
%F a(n) = A020988(n-1) + 1 = A039301(n+1) - 1 = A083584(n-1) + 2. - _Ralf Stephan_, Jun 14 2003
%F 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)
%F a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - _Benoit Cloitre_, Mar 25 2004
%F a(n) = 5*a(n-1) - 4*a(n-2). - _Emeric Deutsch_, Apr 01 2004
%F a(n) = 4^n - A001045(2*n). - _Paul Barry_, Apr 17 2004
%F a(n) = 2*(A001045(n))^2 + (A001045(n+1))^2. - _Paul Barry_, Jul 15 2004
%F 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
%F a(n) = A072197(n) - A020988(n). - _Creighton Dement_, Dec 31 2004
%F a(n) = A139250(2^n). - _Omar E. Pol_, Feb 28 2011
%F a(n) = A193652(2*n+1). - _Reinhard Zumkeller_, Aug 08 2011
%F a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - _Mircea Merca_, Jan 28 2012
%F a(n) = 2^(2*(n+1)) - A072197(n). - _Vladimir Pletser_, Apr 12 2014
%F 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 13, 20 2015
%F 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
%F a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - _Bob Selcoe_, Aug 21 2016
%F E.g.f.: (1 + 2*exp(3*x))*exp(x)/3. - _Ilya Gutkovskiy_, Aug 21 2016
%p 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
%p A007583 := proc(n)
%p (2^(2*n+1)+1)/3 ;
%p end proc: # _R. J. Mathar_, Feb 19 2015
%t (* From _Michael De Vlieger_, Aug 22 2016 *)
%t Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
%t Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
%t NestList[4# -1 &, 1, 23]
%t Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
%t CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)
%o (PARI) a(n)=sum(k=-n\3,n\3,binomial(2*n+1,n+1+3*k))
%o (PARI) a=1; for(n=1,23, print1(a,", "); a=bitor(a,3*a)) \\ _K. Spage_, Aug 20 2014
%o (PARI) Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ _Altug Alkan_, Dec 08 2015
%o (PARI) apply( {A007583(n)=2<<(2*n)\/3}, [0..25]) \\ _M. F. Hasler_, Nov 30 2021
%o (Magma) [(2^(2*n+1) + 1)/3: n in [0..30] ]; // _Vincenzo Librandi_, Apr 28 2011
%o (Haskell)
%o a007583 = (`div` 3) . (+ 1) . a004171
%o -- _Reinhard Zumkeller_, Jan 09 2013
%o (Sage) [(2^(2*n+1) + 1)/3 for n in (0..25)] # _G. C. Greubel_, Dec 25 2019
%o (GAP) List([0..25], n-> (2^(2*n+1) + 1)/3); # _G. C. Greubel_, Dec 25 2019
%Y Cf. also A006054, A006356, A005578.
%Y Partial sums of A081294.
%Y Cf. A002450, A004171, A007051, A083065, A083066, A083884.
%Y Cf. A000978, A000979, A124400, A124401, A127936, A127955, A127956, A127957, A127958.
%Y Cf. location of records in A007302.
%K nonn,easy
%O 0,2
%A _Simon Plouffe_
| 