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

%I #32 Feb 29 2024 14:32:13

%S 1,2,4,8,12,18,23,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,

%T 96,100,104,108,112,116,120,124,128,132,136,140,144,148,152,156,160,

%U 164,168,172,176,180,184,188,192,196,200,204,208,212,216,220,224,228

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

%H Colin Barker, <a href="/A337120/b337120.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Paul Allouche, <a href="https://doi.org/10.1017/S0004972700011655">The Number of Factors in a Paperfolding Sequence</a>, Bulletin of the Australian Mathematical Society, volume 46, number 1, August 1992, pages 23-32. Section 5 theorem, a(n) = P_{u_i}(n).

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).

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

%F From _Colin Barker_, Sep 05 2020: (Start)

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

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

%F (End)

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

%t LinearRecurrence[{2, -1}, {1, 2, 4, 8, 12, 18, 23, 28, 32}, 100] (* _Paolo Xausa_, Feb 29 2024 *)

%o (PARI) Vec((1 + x^2)*(1 + 2*x^3 - x^6) / (1 - x)^2 + O(x^50)) \\ _Colin Barker_, Sep 08 2020

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

%Y Cf. A005943 (GRS).

%K nonn,easy

%O 0,2

%A _Kevin Ryde_, Aug 17 2020