login
A364995
Length of the longest monochromatic arithmetic progressions of difference n in the Rudin-Shapiro sequence (A020985).
1
4, 4, 5, 4, 6, 5, 9, 4, 9, 6, 15, 5, 6, 9, 10, 4, 10, 9, 12, 6, 10, 15, 13, 5, 12, 6, 12, 9, 12, 10, 19, 4, 18, 10, 13, 9, 15, 12, 22, 6, 12, 10, 15, 15, 12, 13, 9, 5, 12, 12, 15, 6, 13, 12, 13, 9, 10, 12, 9, 10, 18, 19, 33, 4, 34, 18, 10, 10, 10, 13, 12, 9
OFFSET
1,1
COMMENTS
Also applies to the other versions of Rudin-Shapiro sequence (e.g., A020987).
For n < 2^k the inequality a(n) <= 2^(k+1) holds, and a monochromatic arithmetic progression of length a(n) and difference n appears within 10*4^k initial terms of the Rudin-Shapiro sequence (A020985). More generally, if a(n) <= 2^m, then such a progression appears within 5*2^(k+m) initial terms. Conversely, if the maximal length of a progression within 5*2^(k+m) initial terms is <= 2^m, then also a(n) <= 2^m. These properties follow from the referenced paper by Sobolewski. - Bartosz Sobolewski, Jun 17 2024
LINKS
Ibai Aedo, Uwe Grimm, Yasushi Nagai, and Petra Staynova, Monochromatic arithmetic progressions in binary Thue-Morse-like words, Theor. Comput. Sci., 934 (2022), 65-80; preprint: On long arithmetic progressions in binary Morse-like words, arXiv:2101.02056 [math.CO], 2021.
EXAMPLE
For n = 3, let r(i) be the i-th term of the Rudin-Shapiro sequence (A020985). We have r(28) = r(31) = r(34) = r(37) = r(40), and no k and m > 5 exist such that r(k) = r(k+3) = r(k+2*3) = ... = r(k+(m-1)*3). So a(3)=5.
MATHEMATICA
a[n_] := a[n] = If[EvenQ[n], a[n/2], Max[Map[Length, Split /@ Table[RudinShapiro[m n + j], {j, 1, n}, {m, 0, 10*4^(Floor[Log2[n]] + 1)/n}], {2}]]];
Table[a[n], {n, 1, 72}] (* Bartosz Sobolewski, Jun 17 2024 *)
CROSSREFS
Cf. A342818 (analog for the Thue-Morse sequence).
Sequence in context: A158935 A226446 A158086 * A195783 A376178 A360997
KEYWORD
nonn
AUTHOR
Gandhar Joshi, Aug 15 2023
EXTENSIONS
a(33)-a(34) from Sobolewski added by Gandhar Joshi, Apr 30 2024
Corrected and extended by Bartosz Sobolewski, Jun 17 2024
STATUS
approved