login
Arithmetical complexity of the regular paperfolding sequence (A014577).
2

%I #28 Feb 29 2024 11:31:11

%S 1,2,4,8,16,24,32,44,52,64,76,86,96,106,116,124,132,140,148,156,164,

%T 172,180,188,196,204,212,220,228,236,244,252,260,268,276,284,292,300,

%U 308,316,324,332,340,348,356,364,372,380,388,396,404,412,420,428,436

%N Arithmetical complexity of the regular paperfolding sequence (A014577).

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

%H Kevin Ryde, <a href="/A333994/b333994.txt">Table of n, a(n) for n = 0..8192</a>

%H S. V. Avgustinovich, D. G. Fon-Der-Flaas, and A. E. Frid, <a href="https://doi.org/10.1142/9789812704979_0004">Arithmetical Complexity of Infinite Words</a>, in Proceedings of the International Colloquium on Words, Languages & Combinatorics III (ICWLC), Kyoto, March 2000, World Scientific Publishing, 2003, pages 51-62. Also <a href="http://www.math.nsc.ru/~frid/Frid_arithm.ps">third author's copy</a>. See section 4 final example 2, a(n) = f^A(n).

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

%F 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]

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

%F 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.

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

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

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

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

%K nonn,easy

%O 0,2

%A _Kevin Ryde_, Sep 04 2020