login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005943 Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.
(Formerly M1116)
4
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

Needs a b-file. - N. J. A. Sloane, Jun 04 2019

REFERENCES

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

LINKS

Table of n, a(n) for n=0..64.

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

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)

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;

CROSSREFS

Cf. A006697, A005942, A337120 (paperfolding).

Sequence in context: A318654 A333994 A305656 * A330131 A008233 A224815

Adjacent sequences:  A005940 A005941 A005942 * A005944 A005945 A005946

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Jeffrey Shallit.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 30 15:48 EDT 2020. Contains 338080 sequences. (Running on oeis4.)