OFFSET
0,2
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).
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).
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)
EXAMPLE
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.)
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Sep 04 2020
STATUS
approved