cp's OEIS Frontend

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

%I A005943 M1116 #71 Aug 27 2023 19:46:33
%S A005943 1,2,4,8,16,24,36,46,56,64,72,80,88,96,104,112,120,128,136,144,152,
%T A005943 160,168,176,184,192,200,208,216,224,232,240,248,256,264,272,280,288,
%U A005943 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 A005943 Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.
%C A005943 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 A005943 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 A005943 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005943 David A. Corneth, <a href="/A005943/b005943.txt">Table of n, a(n) for n = 0..9999</a>
%H A005943 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 A005943 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 A005943 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A005943 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 A005943 From _Kevin Ryde_, Aug 18 2020: (Start)
%F A005943 a(1..7) = 2,4,8,16,24,36,46, then a(n) = 8*n - 8 for n>=8. [Allouche]
%F A005943 a(n) = 2*A337120(n-1) for n>=1. [Allouche, end of proof of theorem 2]
%F A005943 (End)
%e A005943 All 8 subwords of length three (000, 001, ..., 111) occur in A020987, so a(3) = 8.
%p A005943 # Naive Maple program, useful for getting initial terms of factor complexity FC of a sequence b1[]. _N. J. A. Sloane_, Jun 04 2019
%p A005943 FC:=[0]; # a(0)=0 from the empty subword
%p A005943 for L from 1 to 12 do
%p A005943   lis := {};
%p A005943   for n from 1 to nops(b1)-L do
%p A005943     s:=[seq(b1[i],i=n..n+L-1)];
%p A005943     lis:={op(lis),s}; od:
%p A005943 FC:=[op(FC),nops(lis)];
%p A005943 od:
%p A005943 FC;
%t A005943 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 A005943 (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 A005943 Cf. A006697, A005942, A337120 (paperfolding).
%K A005943 nonn,nice,easy
%O A005943 0,2
%A A005943 _N. J. A. Sloane_, _Jeffrey Shallit_
%E A005943 Minor edits by _N. J. A. Sloane_, Jun 06 2012
%E A005943 a(14)-a(32) added by _Joerg Arndt_, Jun 10 2012
%E A005943 a(33)-a(36) added by _Joerg Arndt_, Oct 28 2012