A005346 -id:A005346 - cp's OEIS frontend

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

Steve Butler, Jul 26 2006

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)

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

Cf. A005346, A121386.

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

A121386 Number of different two-colorings of {1,...,n} that minimize the number of monochromatic three-term arithmetic progressions that such a coloring can contain.

Original entry on oeis.org

2, 4, 6, 10, 14, 20, 16, 6, 36, 8, 44, 10, 8, 30, 16, 8, 12, 2, 12, 28, 64, 110, 96, 134, 56, 44, 16, 2, 16, 74, 116, 188, 200, 180

Offset: 1

Steve Butler, Jul 26 2006

nonn

The unique (up to switching colors) sequences for n=18 and n=28 are 001001111000011011 and 0001100011111100000011100111 respectively.

			a(3)=6 because all non-monochromatic colorings are such an example

Cf. A005346, A121385.

Definition corrected by Rob Pratt, Jun 11 2014

A157102 Tuple-chromatic Van der Waerden numbers.

Original entry on oeis.org

3, 7, 7, 21, 11, 43, 15, 25, 19, 111, 23, 157, 27, 43, 31, 273, 35, 343, 39, 61, 43, 507, 47, 121, 51, 79, 55, 813, 59, 931, 63, 97, 67, 171, 71, 1333, 75, 115, 79, 1641, 83, 1807, 87, 133, 91, 2163, 95, 337, 99, 151, 103, 2757, 107, 271, 111, 169, 115, 3423, 119, 3661

Offset: 2

Reed Kelly, Feb 22 2009, Feb 25 2009

nonn

See links for definition. Specifically, the terms of this sequence are the first several terms of tcW(r,r-1,r), where r=2,3,4,.... Informally, the function tcW is like the multi-color Van der Waerden function W, except that the second parameter determines the number of colors found in the target subsequence. If W(r,k) is the standard multi-color Van der Waerden function with r colors and a required monochrome arithmetic subsequence of length k, then tcW(r,1,k) = W(r,k). In tcW(r,1,k), the 1 would indicate a monochrome subsequence. For tcW(r,2,k) an arithmetic subsequence of length k in 1 OR 2 colors would match the criteria. For tcW(r,3,k) an arithmetic subsequence of length k in 1, 2, or 3 colors suffices.

a(r) = tcW(r,r-1,r).

			a(2) = tcW(2,1,2) = W(2,2) = 3. If {1,2,3} is colored in 2 colors, then a 2 term arithmetic subsequence exists in 1 color (monochrome).
a(3) = tcW(3,2,3) = 7. If {1,...,7} is colored in 3 colors, then a 3 term arithmetic subsequence exists that is colored in at most 2 colors.
a(2) = (2-1)(2) + 1 = 3 a(15) = (15-1)(3) + 1 = 43.

Reed Kelly, On a Generalization of Ramsey Theory, 2009.
Reed Kelly, Code for Computing Tuple-chromatic Ramsey Numbers and Tuple-chromatic Van der Waerden Numbers

The 2-color Van der Waerden numbers: A005346, W(2, k). Multi-color Van der Waerden numbers with 3 term monochrome arithmetic subsequences A135415, W(r, 3).

Table[(x - 1) * (FactorInteger[x])[[1]][[1]] + 1, {x, 2, 100}]

a(n) = (n-1)*(smallest prime factor of n) + 1.

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

Original entry on oeis.org

1, 3, 8, 12, 21, 29, 42, 59, 67, 80, 88, 144, 160, 173, 186, 199, 220, 254, 377, 394, 423, 444, 465, 491, 512, 533, 554, 588, 609, 987, 1024, 1058, 1092, 1126, 1160, 1194, 1228, 1262, 1296, 1330, 1364, 1406, 1440, 1474, 1508, 1563, 1652, 2588, 2643, 2698, 2753

Offset: 1

Gandhar Joshi, Feb 29 2024

nonn

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

			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:
  Fibonacci word: 0 1 0 0 1 0 1 0 ...
                        ^   ^   ^
The 3 terms have equal values and are at locations which are a constant step apart (2 in this case).

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

Kevin Ryde, Table of n, a(n) for n = 1..7500
Kevin Ryde, C Code

Cf. A003849, A005346, A339949 (longest progression lengths), A364648 (first positions of longest progressions of length A339949(n)).

C
```
/* See links. */
```

// 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 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]";
// This asserts that there is a progression of length 5 for difference d and first position i taken in pair.
def fibw5mapnew "?msd_fib $fibw5map(d,i) & d>0 & i+4*dA339949.
test fibw5mapnew 5;
// 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.
def fibw5mapfin "?msd_fib Ed,i ($fibw5map(d,i) & d>0 & i+4*d

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

Original entry on oeis.org

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

Gandhar Joshi, Feb 29 2024

nonn

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

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

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

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

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

C
```
/* See links. */
```

// 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*dA342818.
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

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

A157199 The terms of this sequence are the first several terms of tcW(r,r-1,r+1), where r=2,3,4,.... Informally, the function tcW is like the multi-color Van der Waerden function W, except that the second parameter determines the number of colors found in the target subsequence. See links for definition.

Original entry on oeis.org

9, 13, 22, 26, 44, 50, 25, 28

Offset: 2

Reed Kelly, Feb 25 2009

If W(r,k) is the standard multi-color Van der Waerden function with r colors and a required monochrome arithmetic subsequence of length k, then tcW(r,1,k) = W(r,k). In tcW(r,1,k), the 1 would indicate a monochrome subsequence. For tcW(r,2,k) an arithmetic subsequence of length k in 1 OR 2 colors would match the criteria. For tcW(r,3,k) an arithmetic subsequence of length k in 1, 2, or 3 colors suffices.

			a(2) = tcW(2,1,3) = W(2,3) = 9. If {1,...,9} is colored in 2 colors, then a 3-term arithmetic subsequence exists in 1 color (monochrome).
a(3) = tcW(3,2,4) = 13. If {1,...,13} is colored in 3 colors, then a 4-term arithmetic subsequence exists in at most 2 colors.

Reed Kelly, On a Generalization of Ramsey Theory, 2009.
Reed Kelly, Code for Computing Tuple-chromatic Ramsey Numbers and Tuple-chromatic Van der Waerden Numbers

Another part of the tcW function: A157102. The 2-color Van der Waerden numbers: A005346, W(2, k). Multi-color Van der Waerden numbers with 3-term monochrome arithmetic subsequences A135415, W(r, 3).

a(r) = tcW(r,r-1,r+1).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A121386 Number of different two-colorings of {1,...,n} that minimize the number of monochromatic three-term arithmetic progressions that such a coloring can contain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A157102 Tuple-chromatic Van der Waerden numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Walnut

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Walnut

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula