login
Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.
(Formerly M1116)
5

%I M1116 #71 Aug 27 2023 19:46:33

%S 1,2,4,8,16,24,36,46,56,64,72,80,88,96,104,112,120,128,136,144,152,

%T 160,168,176,184,192,200,208,216,224,232,240,248,256,264,272,280,288,

%U 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

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

%C 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

%C 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

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

%H David A. Corneth, <a href="/A005943/b005943.txt">Table of n, a(n) for n = 0..9999</a>

%H Jean-Paul Allouche, <a href="https://doi.org/10.1017/S0004972700011655">The Number of Factors in a Paperfolding Sequence</a>, 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).

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).

%F 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

%F From _Kevin Ryde_, Aug 18 2020: (Start)

%F a(1..7) = 2,4,8,16,24,36,46, then a(n) = 8*n - 8 for n>=8. [Allouche]

%F a(n) = 2*A337120(n-1) for n>=1. [Allouche, end of proof of theorem 2]

%F (End)

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

%p # Naive Maple program, useful for getting initial terms of factor complexity FC of a sequence b1[]. _N. J. A. Sloane_, Jun 04 2019

%p FC:=[0]; # a(0)=0 from the empty subword

%p for L from 1 to 12 do

%p lis := {};

%p for n from 1 to nops(b1)-L do

%p s:=[seq(b1[i],i=n..n+L-1)];

%p lis:={op(lis),s}; od:

%p FC:=[op(FC),nops(lis)];

%p od:

%p FC;

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

%o (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

%Y Cf. A006697, A005942, A337120 (paperfolding).

%K nonn,nice,easy

%O 0,2

%A _N. J. A. Sloane_, _Jeffrey Shallit_

%E Minor edits by _N. J. A. Sloane_, Jun 06 2012

%E a(14)-a(32) added by _Joerg Arndt_, Jun 10 2012

%E a(33)-a(36) added by _Joerg Arndt_, Oct 28 2012