|
| |
|
|
A333994
|
|
Arithmetical complexity of the regular paperfolding sequence (A014577).
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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).
|
|
|
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]
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
