A364995 Length of the longest monochromatic arithmetic progressions of difference n in the Rudin-Shapiro sequence (A020985).

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

Author

Gandhar Joshi, Aug 15 2023

Keywords

• nonn

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

Examples

			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.
		

Links

• Bartosz Sobolewski, Table of n, a(n) for n = 1..10000
• 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.
• Bartosz Sobolewski, On monochromatic arithmetic progressions in binary words associated with pattern sequences, arXiv:2204.05287 [math.CO], 2023.

Crossrefs

Cf. A020985, A020987, A380593 (first starting index).

Cf. A342818 (analog for the Thue-Morse sequence).

Programs

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

Extensions

a(33)-a(34) from Sobolewski added by Gandhar Joshi, Apr 30 2024

Corrected and extended by Bartosz Sobolewski, Jun 17 2024