A005943 Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.

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

Offset: 0

Author

N. J. A. Sloane, Jeffrey Shallit

Keywords

• nonn
• nice
• easy

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

Examples

			All 8 subwords of length three (000, 001, ..., 111) occur in A020987, so a(3) = 8.
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• David A. Corneth, Table of n, a(n) for n = 0..9999
• Jean-Paul Allouche, The Number of Factors in a Paperfolding Sequence, Bulletin of the Australian Mathematical Society, volume 46, number 1, August 1992, pages 23-32. Section 6 theorem 2, a(n) = P_{w_i}(n).
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A006697, A005942, A337120 (paperfolding).

Programs

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 *)

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

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

From Kevin Ryde, Aug 18 2020: (Start)

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)

Extensions

Minor edits by N. J. A. Sloane, Jun 06 2012

a(14)-a(32) added by Joerg Arndt, Jun 10 2012

a(33)-a(36) added by Joerg Arndt, Oct 28 2012