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

John M. Campbell, James Currie, and Narad Rampersad, Reduced complexities for sequences over finite alphabets, arXiv:2509.16034 [math.CO], 2025. See p. 9.

John M. Campbell and Narad Rampersad, Subword enumeration up to stack-sorting equivalence, arXiv:2604.25811 [math.CO], 2026. See p. 10.

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)

E.g.f.: (720 - 1440*x + 2880*exp(x)*x - 1440*x^2 - 480*x^3 - 120*x^4 - 12*x^5 - x^6)/720. - Stefano Spezia, Feb 23 2026

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 * A385653 A100057 A007590

Adjacent sequences: A337117 A337118 A337119 * A337121 A337122 A337123

Keyword

nonn,easy

Author

Kevin Ryde, Aug 17 2020

Status

approved