cp's OEIS Frontend

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

%I A026644 #124 Apr 17 2025 16:56:21
%S A026644 1,2,4,10,20,42,84,170,340,682,1364,2730,5460,10922,21844,43690,87380,
%T A026644 174762,349524,699050,1398100,2796202,5592404,11184810,22369620,
%U A026644 44739242,89478484,178956970,357913940,715827882,1431655764,2863311530,5726623060
%N A026644 a(n) = a(n-1) + 2*a(n-2) + 2, for n>=3, where a(0)= 1, a(1)= 2, a(2)= 4.
%C A026644 Number of moves to solve Chinese rings puzzle.
%C A026644 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.
%C A026644 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
%C A026644 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
%D A026644 Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
%D A026644 Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.
%H A026644 Vincenzo Librandi, <a href="/A026644/b026644.txt">Table of n, a(n) for n = 0..1000</a>
%H A026644 Thomas Baruchel, <a href="https://arxiv.org/abs/1908.02250">Properties of the cumulated deficient binary digit sum</a>, arXiv:1908.02250 [math.NT], 2019.
%H A026644 Sela Fried, <a href="/A026644/a026644_1.pdf">Economically solving the Tower of Hanoi puzzle</a>.
%H A026644 Nicolas Gastineau and O. Togni, <a href="https://arxiv.org/abs/1711.10906">On S-packing edge-colorings of cubic graphs</a>, arXiv preprint arXiv:1711.10906 [cs.DM], 2017.
%H A026644 Lee Hae-hwang, <a href="/A026644/a026644.html">Illustration of initial terms in terms of rosemary plants</a>
%H A026644 Krzysztof A. Meissner, <a href="https://arxiv.org/abs/gr-qc/0407052">Black hole entropy in Loop Quantum Gravity</a>, arXiv:gr-qc/0407052, 2004.
%H A026644 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).
%F A026644 a(2*k) = 2*a(2*k-1), a(2*k+1) = 2*a(2*k) + 2. - _Peter Shor_, Apr 11 2002
%F A026644 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
%F A026644 For n>0: if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3. - Richard Hess
%F A026644 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
%F A026644 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
%F A026644 From _Paul Barry_, Oct 24 2007: (Start)
%F A026644 G.f.: (1 - x^2 + 2*x^3)/((1 - x)*(1 - x - 2*x^2)).
%F A026644 a(n) = J(n+2) - 1 + 0^n, where J(n) = A001045(n) (Jacobsthal numbers).
%F A026644 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
%F A026644 a(n) = 0^n + Sum_{k=0..n} (2 - 2*0^(n-k))*J(k+1). (End)
%F A026644 a(n) = A052953(n+1) - 2, n>0. [Moved from A020988, _R. J. Mathar_, Oct 21 2008]
%F A026644 a(n) = floor(A097074(n+1)/2), n>0. - _Gary Detlefs_, Dec 19 2010
%F A026644 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
%F A026644 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
%F A026644 a(n) + A084170(n) = 3*2^n - 2, n>=1. - _Yosu Yurramendi_, Jul 05 2016
%F A026644 E.g.f: (3 - 4*cosh(x) + 4*cosh(2*x) - 2*sinh(x) + 4*sinh(2*x))/3. - _Ilya Gutkovskiy_, Jul 05 2016
%F A026644 a(n+3) = 9*2^n + A084170(n), n>=0. - _Yosu Yurramendi_, Jul 07 2016
%F A026644 a(n) = A000975(n+1) - A000035(n+1), n>0, a(0)=1. - _Yuchun Ji_, Aug 05 2020
%p A026644 f:=n-> if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3; fi;
%t A026644 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 *)
%t A026644 CoefficientList[Series[(1-x^2+2x^3)/((1-x)(1-x-2x^2)),{x,0,1001}],x] (* _Vincenzo Librandi_, Apr 04 2012 *)
%o A026644 (PARI) Vec((1-x^2+2*x^3)/(1-x)/(1-x-2*x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Apr 04 2012
%o A026644 (Magma) [n eq 0 select 1 else (2^(n+2) -3-(-1)^n)/3 : n in [0..40]]; // _G. C. Greubel_, Jun 28 2024
%o A026644 (SageMath) [(2^(n+2)-3-(-1)^n)/3 + int(n==0) for n in range(41)] # _G. C. Greubel_, Jun 28 2024
%o A026644 (Python)
%o A026644 def A026644(n): return ((4<<n)|1)//3-1 if n else 1 # _Chai Wah Wu_, Apr 17 2025
%Y A026644 Row sums of A026637.
%Y A026644 For n >= 1, equals twice A000975, also A001045 - 1.
%Y A026644 A167030 is an essentially identical sequence.
%K A026644 nonn,easy
%O A026644 0,2
%A A026644 _Clark Kimberling_
%E A026644 Recurrence in definition line found by _Lee Hae-hwang_, Apr 03 2002