A337120 Factor complexity (number of subwords of length n) of the regular paperfolding sequence (A014577), and all generalized paperfolding sequences.

1, 2, 4, 8, 12, 18, 23, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 172, 176, 180, 184, 188, 192, 196, 200, 204, 208, 212, 216, 220, 224, 228

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

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 5 theorem, a(n) = P_{u_i}(n).

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

a(1..6) = 2,4,8,12,18,23, then a(n) = 4*n for n>=7. [Allouche]

From Colin Barker, Sep 05 2020: (Start)

G.f.: (1 + x^2)*(1 + 2*x^3 - x^6) / (1 - x)^2.

a(n) = 2*a(n-1) - a(n-2) for n>8.

(End)

Example

For n=4, all length 4 subwords except 0000, 0101, 1010, 1111 occur, so a(4) = 16-4 = 12.  (These words do not occur because odd terms in a paperfolding sequence alternate, so a subword wxyz must have w!=y or x!=z.)

Mathematica

LinearRecurrence[{2, -1}, {1, 2, 4, 8, 12, 18, 23, 28, 32}, 100] (* Paolo Xausa, Feb 29 2024 *)

Prog

(PARI) Vec((1 + x^2)*(1 + 2*x^3 - x^6) / (1 - x)^2 + O(x^50)) \\ Colin Barker, Sep 08 2020

Crossrefs

Cf. A014577, A214613 (Abelian complexity), A333994 (arithmetical complexity).

Cf. A005943 (GRS).

Sequence in context: A338097 A305694 A176562 * A100057 A007590 A080476

Adjacent sequences: A337117 A337118 A337119 * A337121 A337122 A337123

Keyword

nonn,easy

Author

Kevin Ryde, Aug 17 2020

Status

approved