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

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

Comments

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

References

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

Links

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

Kevin Ryde, C Code

Example

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

Prog

(Walnut)
// 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*d<N";
// This accepts 2-tuple (d, i) such that the last progression appears before N. In the code, N must be replaced with an integer value. We take a calculated guess of what N=i+(n-1)*d is from the list of longest progression lengths A342818.
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<N')";
// This checks if there is any pair (d, i) such that progression length 5 appears before N' which is our improved bound. If Walnut outputs FALSE, then a(n)=N'+1.
(C) /* See links. */

Crossrefs

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

Sequence in context: A310183 A145004 A310184 * A226723 A029918 A081842

Adjacent sequences: A370752 A370754 A370755 * A370757 A370758 A370759

Keyword

nonn,more

Author

Gandhar Joshi, Feb 29 2024

Extensions

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

Status

approved