A095344 Length of n-th string generated by a Kolakoski(9,1) rule starting with a(1)=1.

1, 1, 9, 9, 49, 81, 281, 601, 1729, 4129, 11049, 27561, 71761, 182001, 469049, 1197049, 3073249, 7861441, 20154441, 51600201, 132217969, 338618769, 867490649, 2221965721, 5691928321, 14579791201, 37347504489, 95666669289, 245056687249, 627723364401

Offset: 1

Author

Benoit Cloitre, Jun 03 2004

Keywords

• nonn
• easy

Comments

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.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (0,5,4).

Crossrefs

Cf. A000002, A066983, A095342, A095343.

Cf. A123270, A090390.

Programs

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

Haskell

a095344 n = a095344_list !! (n-1)
a095344_list = tail xs where
   xs = 1 : 1 : 1 : zipWith (-) (map (* 5) $ zipWith (+) (tail xs) xs) xs
-- Reinhard Zumkeller, Aug 16 2013

Magma

R:=PowerSeriesRing(Integers(), 35); Coefficients(R!( x*(1+x+ 4*x^2)/((1+x)*(1-x-4*x^2)) )); // G. C. Greubel, Dec 26 2019

Maple

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

Mathematica

Table[2*(-1)^n - 2^n*(Fibonacci[n+1, 1/2] - 2*Fibonacci[n, 1/2]), {n,35}] (* G. C. Greubel, Dec 26 2019 *)
LinearRecurrence[{0,5,4},{1,1,9},40] (* Harvey P. Dale, Oct 12 2022 *)

PARI

Vec(x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) + O(x^50)) \\ Colin Barker, Apr 20 2016

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

Sage

def A095344_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) ).list()
a=A095344_list(35); a[1:] # G. C. Greubel, Dec 26 2019

Formula

a(1) = a(2) = 1; for n>1, a(n) = a(n-1) + 4*a(n-2) - 4*(-1)^n.

G.f.: x*(1 + x + 4*x^2)/((1 + x)*(1 - x - 4*x^2)). - Colin Barker, Mar 25 2012

a(n) = 5*a(n-2) + 4*a(n-3). - Colin Barker, Mar 25 2012

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

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