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,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

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.

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. A020985, A020987.

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

Sequence in context: A158935 A226446 A158086 * A195783 A376178 A360997

Adjacent sequences: A364992 A364993 A364994 * A364996 A364997 A364998

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