A333994 Arithmetical complexity of the regular paperfolding sequence (A014577).

1, 2, 4, 8, 16, 24, 32, 44, 52, 64, 76, 86, 96, 106, 116, 124, 132, 140, 148, 156, 164, 172, 180, 188, 196, 204, 212, 220, 228, 236, 244, 252, 260, 268, 276, 284, 292, 300, 308, 316, 324, 332, 340, 348, 356, 364, 372, 380, 388, 396, 404, 412, 420, 428, 436

Offset: 0

Author

Kevin Ryde, Sep 04 2020

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

• Kevin Ryde, Table of n, a(n) for n = 0..8192
• S. V. Avgustinovich, D. G. Fon-Der-Flaas, and A. E. Frid, Arithmetical Complexity of Infinite Words, in Proceedings of the International Colloquium on Words, Languages & Combinatorics III (ICWLC), Kyoto, March 2000, World Scientific Publishing, 2003, pages 51-62. Also third author's copy. See section 4 final example 2, a(n) = f^A(n).
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

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

Programs

Mathematica

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

Formula

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]

From Colin Barker, Sep 05 2020: (Start)

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.

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