cp's OEIS Frontend

A370755 a(n) is the van der Waerden number W_f(2,n) of the Fibonacci word (A003849).

%I A370755 #51 Apr 21 2024 10:01:20
%S A370755 1,3,8,12,21,29,42,59,67,80,88,144,160,173,186,199,220,254,377,394,
%T A370755 423,444,465,491,512,533,554,588,609,987,1024,1058,1092,1126,1160,
%U A370755 1194,1228,1262,1296,1330,1364,1406,1440,1474,1508,1563,1652,2588,2643,2698,2753
%N A370755 a(n) is the van der Waerden number W_f(2,n) of the Fibonacci word (A003849).
%C A370755 a(n) is an extremely naive lower bound of the Waerden numbers A005346(n).
%D A370755 B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. (in German), 15 (1927), 212-216.
%H A370755 Kevin Ryde, <a href="/A370755/b370755.txt">Table of n, a(n) for n = 1..7500</a>
%H A370755 Kevin Ryde, <a href="/A370755/a370755.c.txt">C Code</a>
%e A370755 For n=3, at least a(3)=8 terms of the prefix of the Fibonacci word are required to find a monochromatic arithmetic progression of length 3:
%e A370755   Fibonacci word: 0 1 0 0 1 0 1 0 ...
%e A370755                         ^   ^   ^
%e A370755 The 3 terms have equal values and are at locations which are a constant step apart (2 in this case).
%o A370755 (Walnut)
%o A370755 // 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 A370755 def fibw5map "?msd_fib F[i]=F[i+d] & F[i]=F[i+2*d] & F[i]=F[i+3*d] & F[i]=F[i+4*d]";
%o A370755 // This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
%o A370755 def fibw5mapnew "?msd_fib $fibw5map(d,i) & d>0 & i+4*d<N";
%o A370755 // 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 A339949.
%o A370755 test fibw5mapnew 5;
%o A370755 // This enumerates the first 5 accepted pairs (d,i) in Zeckendorf representation 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 A370755 def fibw5mapfin "?msd_fib Ed,i ($fibw5map(d,i) & d>0 & i+4*d<N')";
%o A370755 // 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 A370755 (C) /* See links. */
%Y A370755 Cf. A003849, A005346, A339949 (longest progression lengths), A364648 (first positions of longest progressions of length A339949(n)).
%K A370755 nonn
%O A370755 1,2
%A A370755 _Gandhar Joshi_, Feb 29 2024