A364995 - OEIS

%I #38 Jun 30 2024 03:14:34

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

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

%U 13,9,10,12,9,10,18,19,33,4,34,18,10,10,10,13,12,9

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

%C Also applies to the other versions of Rudin-Shapiro sequence (e.g., A020987).

%C 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

%H Bartosz Sobolewski, <a href="/A364995/b364995.txt">Table of n, a(n) for n = 1..10000</a>

%H Ibai Aedo, Uwe Grimm, Yasushi Nagai, and Petra Staynova, <a href="https://doi.org/10.1016/j.tcs.2022.08.013">Monochromatic arithmetic progressions in binary Thue-Morse-like words</a>, Theor. Comput. Sci., 934 (2022), 65-80; preprint: <a href="https://arxiv.org/abs/2101.02056">On long arithmetic progressions in binary Morse-like words</a>, arXiv:2101.02056 [math.CO], 2021.

%H Bartosz Sobolewski, <a href="https://arxiv.org/abs/2204.05287">On monochromatic arithmetic progressions in binary words associated with pattern sequences</a>, arXiv:2204.05287 [math.CO], 2023.

%e 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.

%t 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}]]];

%t Table[a[n], {n, 1, 72}] (* _Bartosz Sobolewski_, Jun 17 2024 *)

%Y Cf. A020985, A020987.

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

%K nonn

%O 1,1

%A _Gandhar Joshi_, Aug 15 2023

%E a(33)-a(34) from Sobolewski added by _Gandhar Joshi_, Apr 30 2024

%E Corrected and extended by _Bartosz Sobolewski_, Jun 17 2024