A337120 -id:A337120 - cp's OEIS frontend

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

N. J. A. Sloane, Jeffrey Shallit

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

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

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

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

Cf. A006697, A005942, A337120 (paperfolding).

# 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;

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

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

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)

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

A214613 Abelian complexity function of ordinary paperfolding word (A014707).

Original entry on oeis.org

2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 6, 5, 6, 5, 6, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 6, 7, 8, 7, 6, 7, 6, 5, 6, 7, 6, 5, 6, 7, 6, 5, 6, 7, 6, 5, 6, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 6, 7, 8, 7, 6, 7, 6, 5, 6, 7

Offset: 1

N. J. A. Sloane, Mar 08 2013

nonn

k first appears at position A005578(k-1). - Charlie Neder, Mar 03 2019

Charlie Neder, Table of n, a(n) for n = 1..1024
Blake Madill, Narad Rampersad, The abelian complexity of the paperfolding word, Discrete Math. 313 (2013), no. 7, 831--838. MR3017968.

Cf. A014707, A014577, A005578, A337120.

From Charlie Neder, Mar 03 2019 [Corrected by Kevin Ryde, Sep 05 2020]: (Start)
Madill and Rampersad provide the following recurrence:
a(1) = 2,
a(4n) = a(2n),
a(4n+2) = a(2n+1) + 1,
a(16n+1) = a(8n+1),
a(16n+{3,7,9,13}) = a(2n+1) + 2,
a(16n+5) = a(4n+1) + 2,
a(16n+11) = a(4n+3) + 2,
a(16n+15) = a(2n+2) + 1. (End)

a(21)-a(82) from Charlie Neder, Mar 03 2019

A333994 Arithmetical complexity of the regular paperfolding sequence (A014577).

Original entry on oeis.org

1, 2, 4, 8, 16, 24, 32, 44, 52, 64, 76, 86, 96, 106, 116, 124, 132, 140, 148, 156, 164, 172, 180, 188, 196, 204, 212, 220, 228, 236, 244, 252, 260, 268, 276, 284, 292, 300, 308, 316, 324, 332, 340, 348, 356, 364, 372, 380, 388, 396, 404, 412, 420, 428, 436

Offset: 0

Kevin Ryde, Sep 04 2020

Avgustinovich, Fon-Der-Flaas, and Frid define arithmetical complexity of a sequence t as the number of distinct subwords of length n formed by taking terms in arithmetic progression, so t(s), t(s+d), t(s+2*d), ..., t(s+(n-1)*d), each term a step d>=1 apart. For d=1, these are the ordinary subwords (factors) so that arithmetical complexity >= factor complexity, which here is a(n) >= A337120(n).

			For n=4, all subwords of length 4 occur in arithmetic progressions so a(4)=16.  These are the 12 ordinary subwords of the paperfolding sequence (A337120(4) = 12) and the 4 further 0000, 0101, 1010, 1111 which are arithmetic progressions in the odd terms.  (Odd terms alternate 0,1.)

Kevin Ryde, Table of n, a(n) for n = 0..8192
S. V. Avgustinovich, D. G. Fon-Der-Flaas, and A. E. Frid, Arithmetical Complexity of Infinite Words, in Proceedings of the International Colloquium on Words, Languages & Combinatorics III (ICWLC), Kyoto, March 2000, World Scientific Publishing, 2003, pages 51-62. Also third author's copy. See section 4 final example 2, a(n) = f^A(n).
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A014577, A337120 (factor complexity), A214613 (Abelian complexity).

LinearRecurrence[{2, -1}, {1, 2, 4, 8, 16, 24, 32, 44, 52, 64, 76, 86, 96, 106, 116, 124}, 100] (* Paolo Xausa, Feb 29 2024 *)

a(1..13) = 2,4,8,16,24, 32,44,52,64,76, 86,96,106, and a(n) = 8*n + 4 for n >= 14. [Avgustinovich, Fon-Der-Flaas, and Frid]
From Colin Barker, Sep 05 2020: (Start)
G.f.: (1 + x^2 + 2*x^3 + 4*x^4 + 4*x^7 - 4*x^8 + 4*x^9 - 2*x^11 - 2*x^15) / (1 - x)^2.
a(n) = 2*a(n-1) - a(n-2) for n >= 16. (End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A214613 Abelian complexity function of ordinary paperfolding word (A014707).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A333994 Arithmetical complexity of the regular paperfolding sequence (A014577).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula