%I #36 Oct 12 2022 16:20:51
%S 1,1,9,9,49,81,281,601,1729,4129,11049,27561,71761,182001,469049,
%T 1197049,3073249,7861441,20154441,51600201,132217969,338618769,
%U 867490649,2221965721,5691928321,14579791201,37347504489,95666669289,245056687249,627723364401
%N Length of n-th string generated by a Kolakoski(9,1) rule starting with a(1)=1.
%C Each string is derived from the previous string using the Kolakoski(9,1) rule and the additional condition: "string begins with 1 if previous string ends with 9 and vice versa". The strings are 1 -> 9 -> 111111111 -> 919191919 -> 11111111191111111119... -> ... and each one contains 1,1,9,9,31,... elements.
%H Reinhard Zumkeller, <a href="/A095344/b095344.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,4).
%F a(1) = a(2) = 1; for n>1, a(n) = a(n-1) + 4*a(n-2) - 4*(-1)^n.
%F G.f.: x*(1 + x + 4*x^2)/((1 + x)*(1 - x - 4*x^2)). - _Colin Barker_, Mar 25 2012
%F a(n) = 5*a(n-2) + 4*a(n-3). - _Colin Barker_, Mar 25 2012
%F a(n) = 2*(-1)^n + (2^(-1-n)*(-(-7+sqrt(17))*(1+sqrt(17))^n - (1-sqrt(17))^n*(7+sqrt(17))))/sqrt(17). - _Colin Barker_, Apr 20 2016
%F a(n) = 2*(-1)^n - 2^n*(Fibonacci(n+1, 1/2) - 2*Fibonacci(n, 1/2)) = 2*(-1)^n - (2/I)^n*(ChebyshevU(n, I/4) - 2*I*ChebyshevU(n-1, I/4)). - _G. C. Greubel_, Dec 26 2019
%p seq(simplify(2*(-1)^n -(2/I)^n*(ChebyshevU(n, I/4) -2*I*ChebyshevU(n-1, I/4)) ), n = 1..35); # _G. C. Greubel_, Dec 26 2019
%t Table[2*(-1)^n - 2^n*(Fibonacci[n+1, 1/2] - 2*Fibonacci[n, 1/2]), {n,35}] (* _G. C. Greubel_, Dec 26 2019 *)
%t LinearRecurrence[{0,5,4},{1,1,9},40] (* _Harvey P. Dale_, Oct 12 2022 *)
%o (Haskell)
%o a095344 n = a095344_list !! (n-1)
%o a095344_list = tail xs where
%o xs = 1 : 1 : 1 : zipWith (-) (map (* 5) $ zipWith (+) (tail xs) xs) xs
%o -- _Reinhard Zumkeller_, Aug 16 2013
%o (PARI) Vec(x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) + O(x^50)) \\ _Colin Barker_, Apr 20 2016
%o (PARI) vector(35, n, round( 2*(-1)^n - (2/I)^n*(polchebyshev(n, 2, I/4) -2*I*polchebyshev(n-1, 2, I/4)) )) \\ _G. C. Greubel_, Dec 26 2019
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 35); Coefficients(R!( x*(1+x+ 4*x^2)/((1+x)*(1-x-4*x^2)) )); // _G. C. Greubel_, Dec 26 2019
%o (Sage)
%o def A095344_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) ).list()
%o a=A095344_list(35); a[1:] # _G. C. Greubel_, Dec 26 2019
%o (GAP) a:=[1,1,9];; for n in [4..35] do a[n]:=5*a[n-2]+4*a[n-3]; od; a; # _G. C. Greubel_, Dec 26 2019
%Y Cf. A000002, A066983, A095342, A095343.
%Y Cf. A123270, A090390.
%K nonn,easy
%O 1,3
%A _Benoit Cloitre_, Jun 03 2004
|