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
Examples
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.)
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).
Crossrefs
Programs
-
Mathematica
LinearRecurrence[{2, -1}, {1, 2, 4, 8, 12, 18, 23, 28, 32}, 100] (* Paolo Xausa, Feb 29 2024 *) -
PARI
Vec((1 + x^2)*(1 + 2*x^3 - x^6) / (1 - x)^2 + O(x^50)) \\ Colin Barker, Sep 08 2020
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)