|
|
A005943
|
|
Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.
(Formerly M1116)
|
|
5
|
|
|
1, 2, 4, 8, 16, 24, 36, 46, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408, 416, 424, 432, 440, 448, 456, 464, 472, 480, 488, 496, 504
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Terms a(0)..a(13) were verified and terms a(14)..a(32) were computed using the first 2^32 terms of the GRS sequence. - Joerg Arndt, Jun 10 2012
Terms a(0)..a(63) were computed using the first 2^36 terms of the GRS sequence, and are consistent with Arndt's conjectured g.f. - Sean A. Irvine, Oct 12 2016
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1+x^2+2*x^3+4*x^4+4*x^6-2*x^7-2*x^9)/(1-x)^2. - Joerg Arndt, Jun 10 2012
a(1..7) = 2,4,8,16,24,36,46, then a(n) = 8*n - 8 for n>=8. [Allouche]
a(n) = 2*A337120(n-1) for n>=1. [Allouche, end of proof of theorem 2]
(End)
|
|
EXAMPLE
|
All 8 subwords of length three (000, 001, ..., 111) occur in A020987, so a(3) = 8.
|
|
MAPLE
|
# Naive Maple program, useful for getting initial terms of factor complexity FC of a sequence b1[]. N. J. A. Sloane, Jun 04 2019
FC:=[0]; # a(0)=0 from the empty subword
for L from 1 to 12 do
lis := {};
for n from 1 to nops(b1)-L do
s:=[seq(b1[i], i=n..n+L-1)];
lis:={op(lis), s}; od:
FC:=[op(FC), nops(lis)];
od:
FC;
|
|
MATHEMATICA
|
CoefficientList[Series[(1 + x^2 + 2 x^3 + 4 x^4 + 4 x^6 - 2 x^7 - 2 x^9)/(1 - x)^2, {x, 0, 64}], x] (* Michael De Vlieger, Oct 14 2021 *)
|
|
PROG
|
(PARI) first(n) = n = max(n, 10); concat([1, 2, 4, 8, 16, 24, 36, 46], vector(n-8, i, 8*i+48)) \\ David A. Corneth, Apr 28 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|