cp's OEIS Frontend

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

%I A370756 #38 Jul 21 2025 12:28:53
%S A370756 1,3,7,10,13,16,19,57,73,136,151,166,181,196,211,226,241,256,271,621,
%T A370756 652,683,714,745,776,807,838,869,900,931,962,993,1057,2080,2143,2206,
%U A370756 2269,2332,2395,2458,2521,2584,2647,2710,2773,2836,2899,2962,3025,3088,3151
%N A370756 a(n) is the van der Waerden number W_t(2,n) of the Thue-Morse word (A010060).
%C A370756 a(n) is an extremely naive lower bound of the Waerden numbers A005346(n).
%D A370756 B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. (in German), 15 (1927), 212-216.
%H A370756 Kevin Ryde, <a href="/A370756/b370756.txt">Table of n, a(n) for n = 1..8194</a>
%H A370756 Kevin Ryde, <a href="/A370756/a370756.c.txt">C Code</a>
%e A370756 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:
%e A370756   Thue-Morse word: 0 1 1 0 1 0 0 ...
%e A370756                    ^     ^     ^
%e A370756 The 3 terms have equal values and are at locations which are a constant step apart (3 in this case).
%o A370756 (Walnut)
%o A370756 // 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).
%o A370756 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]";
%o A370756 // This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
%o A370756 def tmw5mapnew "$tmw5map(d,i) & d>0 & i+4*d<N";
%o A370756 // 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.
%o A370756 test tmw5mapnew 5;
%o A370756 // 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.
%o A370756 def tmw5mapfin "Ed,i ($tmw5map(d,i) & d>0 & i+4*d<N')";
%o A370756 // 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.
%o A370756 (C) /* See links. */
%Y A370756 Cf. A010060, A005346, A342818 (longest progression lengths), A342827 (first positions of longest progressions of length A342818(n)).
%K A370756 nonn
%O A370756 1,2
%A A370756 _Gandhar Joshi_, Feb 29 2024
%E A370756 a(13) onward from _Kevin Ryde_, Mar 31 2024