A342818 -id:A342818 - cp's OEIS frontend

A350600 Color of the first occurrence of a monochromatic arithmetic progression of difference n and length b(n) in the Thue-Morse sequence (A010060), where b(n) = A342818(n).

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1

Offset: 1

Ibai Aedo, Jan 08 2022

nonn

Ibai Aedo, Table of n, a(n) for n = 1..2048
Ibai Aedo, Uwe Grimm, Yasushi Nagai, and Petra Staynova, On long arithmetic progressions in binary Morse-like words, arXiv:2101.02056 [math.CO], 2021.
Olga Parshina, On arithmetic index in the generalized Thue-Morse word, arXiv:1811.03884 [math.CO], 2018.

Cf. A010060. A342818, A342827.

a(n) = A010060(A342827(n)).

A342827 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference d in the Thue-Morse sequence (A010060).

Original entry on oeis.org

1, 2, 45, 4, 43, 90, 7, 8, 183, 86, 12, 180, 27, 14, 753, 16, 751, 366, 20, 172, 370, 24, 166, 360, 37, 54, 48, 28, 35, 1506, 31, 32, 3039, 1502, 36, 732, 94, 40, 205, 344, 56, 740, 725, 48, 663, 332, 326, 720, 321, 74, 137, 108, 60, 96, 617, 56, 378, 70, 101

Offset: 1

Jeffrey Shallit, Mar 23 2021

nonn

The length of this longest progression is A342818(n).

			For example, the smallest i with t(i)=t(i+3)=t(i+6)=t(i+9)=t(i+12)=t(i+15)=t(i+18)=t(i+21) is i=45 and so, a(3)=45.

Ibai Aedo, Table of n, a(n) for n = 1..2048
Ibai Aedo, Uwe Grimm, Yasushi Nagai, and Petra Staynova, On long arithmetic progressions in binary Morse-like words, arXiv:2101.02056 [math.CO], 2021.
Gandhar Joshi and Dan Rust, Monochromatic arithmetic progressions in the Fibonacci word, arXiv:2501.05830 [math.DS], 2025. See p. 7.
Olga Parshina, On arithmetic index in the generalized Thue-Morse word, arXiv:1811.03884 [math.CO], 2018.

Cf. A010060, A342818.

A350226 a(n) is the length of the longest sequence of distinct numbers in arithmetic progression in the interval 0..n, ending with n and where the Thue-Morse sequence (A010060) is constant.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 3, 3, 2, 4, 3, 2, 5, 3, 3, 6, 2, 3, 7, 4, 5, 3, 4, 3, 5, 5, 4, 4, 6, 3, 6, 7, 2, 4, 3, 5, 7, 7, 4, 6, 5, 5, 6, 3, 5, 6, 3, 6, 5, 7, 7, 5, 5, 4, 7, 4, 8, 6, 4, 4, 6, 6, 7, 8, 2, 3, 8, 5, 6, 3, 5, 5, 9, 7, 7, 7, 6, 4, 6, 7, 5, 5, 8, 5, 6, 6, 4

Offset: 0

Rémy Sigrist, Dec 20 2021

nonn

In other words, a(n) is the greatest k > 0 such that A010060(n) = A010060(n - i*d) for i = 0..k-1 and some d > 0 (see A350285 for the least such d).

This sequence is unbounded (this is a consequence of Van der Waerden's theorem).

			For n = 12:
- the first 13 terms of A010060 are:
         0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0
         ^        ^        ^        ^        ^
- A010060(0) = A010060(3) = A010060(6) = A010060(9) = A010060(12),
- and there is no longer sequence of distinct numbers <= 12 in arithmetic progression ending in 12 with this property,
- so a(12) = 5.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, C program for A350226

Cf. A005346, A010060, A342818, A342827, A350235 (records), A350285 (least first differences).

C
```
See Links section.
```

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

Original entry on oeis.org

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

Gandhar Joshi, Aug 15 2023

nonn

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

			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.

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.

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

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

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

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

Corrected and extended by Bartosz Sobolewski, Jun 17 2024

A370756 a(n) is the van der Waerden number W_t(2,n) of the Thue-Morse word (A010060).

Original entry on oeis.org

1, 3, 7, 10, 13, 16, 19, 57, 73, 136, 151, 166, 181, 196, 211, 226, 241, 256, 271, 621, 652, 683, 714, 745, 776, 807, 838, 869, 900, 931, 962, 993, 1057, 2080, 2143, 2206, 2269, 2332, 2395, 2458, 2521, 2584, 2647, 2710, 2773, 2836, 2899, 2962, 3025, 3088, 3151

Offset: 1

Gandhar Joshi, Feb 29 2024

nonn

a(n) is an extremely naive lower bound of the Waerden numbers A005346(n).

			For n=3, at least a(3)=7 terms of the prefix of the Thue-Morse word are required to find a monochromatic arithmetic progression of length 3:
  Thue-Morse word: 0 1 1 0 1 0 0 ...
                   ^     ^     ^
The 3 terms have equal values and are at locations which are a constant step apart (3 in this case).

B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. (in German), 15 (1927), 212-216.

Kevin Ryde, Table of n, a(n) for n = 1..8194
Kevin Ryde, C Code

Cf. A010060, A005346, A342818 (longest progression lengths), A342827 (first positions of longest progressions of length A342818(n)).

C
```
/* See links. */
```

// The program is written for a fixed value of progression length, so it is run to find each a(n) separately. Following is an example to find a(5).
def tmw5map "T[i]=T[i+d] & T[i]=T[i+2*d] & T[i]=T[i+3*d] & T[i]=T[i+4*d]";
// This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
def tmw5mapnew "$tmw5map(d,i) & d>0 & i+4*dA342818.
test tmw5mapnew 5;
// This enumerates the first 5 accepted pairs (d,i) in binary listed in lexicographic order. The first or second in the list is our improved bound to be replaced for N in line number 2.
def tmw5mapfin "Ed,i ($tmw5map(d,i) & d>0 & i+4*d

a(13) onward from Kevin Ryde, Mar 31 2024

cp's OEIS Frontend

A350600 Color of the first occurrence of a monochromatic arithmetic progression of difference n and length b(n) in the Thue-Morse sequence (A010060), where b(n) = A342818(n).

Views

Author

Keywords

Links

Crossrefs

Formula

A342827 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference d in the Thue-Morse sequence (A010060).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A350226 a(n) is the length of the longest sequence of distinct numbers in arithmetic progression in the interval 0..n, ending with n and where the Thue-Morse sequence (A010060) is constant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A370756 a(n) is the van der Waerden number W_t(2,n) of the Thue-Morse word (A010060).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Walnut

Extensions