login
The OEIS is supported by the many generous donors to the OEIS 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)
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

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

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;

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

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,easy

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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 6 09:29 EDT 2022. Contains 357263 sequences. (Running on oeis4.)