A121385 Minimal number of monochromatic three-term arithmetic progressions that a two-coloring of {1,...,n} can contain.

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 62, 66, 70, 74, 78, 82, 86

Offset

1,11

Comments

a(9) = 1 is the well-known fact that the van der Waerden number for two colors and three-term arithmetic progressions is 9.

From Rob Pratt, May 27 2014: (Start)

By ignoring the last element, we see that a(n) >= a(n-1).

The general problem for k terms and r colors can be solved by using integer programming, with binary decision variables x[i,c] = 1 if element i receives color c and 0 otherwise, y[i,d] = 1 if arithmetic progression (i,i+d,...,i+(k-1)d) is monochromatic and 0 otherwise. The constraints are sum {c in 1..r} x[i,c] = 1 for all i in 1, …, n and sum {j=0 to k-1} x[i+j*d,c] - k + 1 <= y[i,d] for all i, d, c. The objective is to minimize sum {i, d} y[i,d].

Upper bounds are a(46) <= 90, a(47) <= 95, a(48) <= 100, a(49) <= 104, a(50) <= 110.

(End)

Links

Table of n, a(n) for n=1..45.

Example

a(8) = 0 because we can two color {1,...,8} by 11001100 so that there are no monochromatic three-term arithmetic progressions.

Crossrefs

Cf. A005346, A121386.

Sequence in context: A017874 A029016 A290807 * A029015 A000008 A001312

Adjacent sequences: A121382 A121383 A121384 * A121386 A121387 A121388

Keyword

nonn,more

Author

Steve Butler, Jul 26 2006

Extensions

a(35)-a(45) from Rob Pratt, May 27 2014

Status

approved