Van der Waerden's theorem states that for any positive integers "r" and "k" there exists a positive integer "N" such that if the integers {1, 2, ..., "N"} are colored, each with one of "r" different colors, then there are at least "k" integers in arithmetic progression all of the same color. The smallest such "N" is the van der Waerden number "W"("r", "k").
Tables of Van der Waerden numbers.
There are two cases in which the van der Waerden number "W"("r", "k") is easy to compute: first, when the number of colors "r" is equal to 1, one has "W"(1, "k") = "k" for any integer "k", since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, when the length "k" of the forced arithmetic progression is 2, one has "W"("r", 2) = "r" + 1, since one may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but using any color twice creates a length-2 arithmetic progression. (For example, for "r" = 3, the longest coloring that avoids an arithmetic progression of length 2 is RGB.) There are only seven other van der Waerden numbers that are known exactly. The table below gives exact values and bounds for values of "W"("r", "k"); values are taken from Rabung and Lotts except where otherwise noted.
Some lower bound colorings computed using SAT approach by Marijn J.H. Heule can be found on github project page. 
Van der Waerden numbers with "r" ≥ 2 are bounded above by
formula_1
as proved by Gowers.
For a prime number "p", the 2-color van der Waerden number is bounded below by
formula_2
as proved by Berlekamp.
One sometimes also writes "w"(r; "k"1, "k"2, ..., "k""r") to mean the smallest number "w" such that any coloring of the integers {1, 2, ..., "w"} with "r" colors contains a progression of length "k""i" of color "i", for some "i". Such numbers are called "off-diagonal van der Waerden numbers". Thus "W"("r", "k") = "w"(r; "k", "k", ..., "k").
Following is a list of some known van der Waerden numbers:
Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are (at most) on the fifth level formula_3 of the Grzegorczyk hierarchy.
References.
 ;templatestyles src="Reflist/styles.css" / ;