A005346 -id:A005346 - cp's OEIS frontend

A121894 Van der Waerden numbers: A005346(n) - 1.

0, 2, 8, 34, 177, 1131

Offset: 1

James Dow Allen, Sep 01 2006

The maximum length of a string of 0's and 1's with no n-length "decimated substring" being all 0's or all 1's. A decimated substring is defined to be any subset {x_a, x_(a+p), x_(a+2p), x_(a+3p), ...} for any appropriate a, p.

Some authors prefer this version to A005346.

			a(3) = 8 because 00110011 is the maximal string for n=3: appending 1 gives ......111 and appending 0 gives 0...0...0. No other starting string improves on this.

Cf. A005346.

Term a(6) (using A005346) from Joerg Arndt, Jun 06 2016

A171081 Van der Waerden numbers w(3, n).

Original entry on oeis.org

9, 18, 22, 32, 46, 58, 77, 97, 114, 135, 160, 186, 218, 238, 279, 312, 349

Offset: 3

N. J. A. Sloane, based on an email from Tanbir Ahmed, Sep 07 2010

The two-color van der Waerden number w(3,n) is also denoted as w(2;3,n).
Ahmed et al. give lower bounds for a(20)-a(30) which may in fact be the true values. - N. J. A. Sloane, May 13 2018
B. Green shows that w(3,n) is bounded below by n^b(n), where b(n) = c*(log(n)/ log(log(n)))^(1/3). T. Schoen proves that for large n one has w(3,n) < exp(n^(1 - c)) for some constant c > 0. - Peter Luschny, Feb 03 2021

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, page 5.

Tanbir Ahmed, Oliver Kullmann, and Hunter Snevily, On the van der Waerden numbers w(2;3,t), arXiv:1102.5433 [math.CO], 2011-2014; Discrete Applied Math., 174 (2014), 27-51.
Ben Green, New lower bounds for van der Waerden numbers, arXiv:2102.01543 [math.CO], Feb. 2021.
Tomasz Schoen, A subexponential bound for van der Waerden numbers, arXiv:2006.02877 [math.CO], June 2020.

Cf. A005346 (w(2, n)), A171082, A217235.

a(19) from Ahmed et al. - Jonathan Vos Post, Mar 01 2011

A100042 a(n) = prime(n)*2^prime(n).

Original entry on oeis.org

8, 24, 160, 896, 22528, 106496, 2228224, 9961472, 192937984, 15569256448, 66571993088, 5085241278464, 90159953477632, 378231999954944, 6614661952700416, 477381560501272576, 34011184385901985792

Offset: 1

Jorge Coveiro, Dec 26 2004

nonn

A lower bound for the 2-color van der Waerden number A005346(prime(n)); see Berlekamp reference. - Charles R Greathouse IV, Jul 13 2008

E. R. Berlekamp, A construction for partitions which avoid long arithmetic progressions, Canadian Mathematical Bulletin, Vol. 11, No. 3 (1968), pp. 409-414.

Cf. A005346, A034785, A157413.

Maple
```
seq(ithprime(n)*2^ithprime(n),n=1..20);
```

#*2^#&/@Prime[Range[20]] (* Harvey P. Dale, Sep 18 2020 *)

a(n) = prime(n)*2^prime(n); \\ Michel Marcus, May 14 2017

Sum_{n>=1} 1/a(n) = A157413. - Amiram Eldar, Nov 17 2020

A135415 Van der Waerden numbers for 3-arithmetic progressions with n colors.

Original entry on oeis.org

3, 9, 27, 76

Offset: 1

Hunter Monroe (hmonroe(AT)huntermonroe.com), Feb 17 2008

It is known that a(5) > 170.

Eric Weisstein's World of Mathematics, Van der Waerden numbers
Wikipedia, Van der Waerden number

Cf. A005346.

a(1) prepended by Jinyuan Wang, Mar 13 2020

A171082 Van der Waerden numbers w(2;4,n).

Original entry on oeis.org

35, 55, 73, 109, 146, 309

Offset: 4

N. J. A. Sloane, based on an email from Tanbir Ahmed, Sep 07 2010 and Feb 22 2012

Tanbir Ahmed, Van der Waerden numbers
Tanbir Ahmed, On computation of exact van der Waerden numbers, Integers: Electronic Journal of Combinatorial Number Theory, 11 (2011), A71.

Cf. A005346, A171081, A217235.

A350226 a(n) is the length of the longest sequence of distinct numbers in arithmetic progression in the interval 0..n, ending with n and where the Thue-Morse sequence (A010060) is constant.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 3, 3, 2, 4, 3, 2, 5, 3, 3, 6, 2, 3, 7, 4, 5, 3, 4, 3, 5, 5, 4, 4, 6, 3, 6, 7, 2, 4, 3, 5, 7, 7, 4, 6, 5, 5, 6, 3, 5, 6, 3, 6, 5, 7, 7, 5, 5, 4, 7, 4, 8, 6, 4, 4, 6, 6, 7, 8, 2, 3, 8, 5, 6, 3, 5, 5, 9, 7, 7, 7, 6, 4, 6, 7, 5, 5, 8, 5, 6, 6, 4

Offset: 0

Rémy Sigrist, Dec 20 2021

nonn

In other words, a(n) is the greatest k > 0 such that A010060(n) = A010060(n - i*d) for i = 0..k-1 and some d > 0 (see A350285 for the least such d).

This sequence is unbounded (this is a consequence of Van der Waerden's theorem).

			For n = 12:
- the first 13 terms of A010060 are:
         0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0
         ^        ^        ^        ^        ^
- A010060(0) = A010060(3) = A010060(6) = A010060(9) = A010060(12),
- and there is no longer sequence of distinct numbers <= 12 in arithmetic progression ending in 12 with this property,
- so a(12) = 5.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, C program for A350226

Cf. A005346, A010060, A342818, A342827, A350235 (records), A350285 (least first differences).

C
```
See Links section.
```

A378197 Number of 2-colorings of length n without an arithmetic progression of length 5.

Original entry on oeis.org

1, 2, 4, 8, 16, 30, 58, 112, 216, 400, 740, 1398, 2638, 4710, 8444, 15118, 27690, 48406, 84382, 146928, 255844, 402998, 625824, 956370, 1447476, 2066828, 3225856, 5020232, 7823236, 10975318, 15264202, 21500308, 30004914, 39030820, 50728472, 65402746, 88886116

Offset: 0

Ethan Ji, Nov 19 2024

nonn

After a(178) = 0, the sequence will continue to be 0. A sequence satisfying this property cannot have a subsequence which violates it, thus there must exist a sequence of length n-1 if there exists a sequence of length n.

Michael De Vlieger, Table of n, a(n) for n = 0..178

First 0 index given by A005346.

Cf. A378195, A378196.

HasEquallySpacedKBits[bits_, k_] :=
 If[k == 1, True,
  Module[{n = Length[bits], found = False},
   Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
       bits[[start]]] == k, found = True; Break[]], {gap, 1,
     Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
   found]]
BitSequence[k_] :=
 Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
  ExtendSequence[seq_] :=
   Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
    newSeq1 = Join[seq, {1}];
    If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
    If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
    result];
  Function[targetN,
   Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
   While[n < targetN, n++;
    currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
    prevSequences = currSequences;
    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]]; ]; ]]
BitSequence[5][178]
(* Ethan Ji, Nov 19 2024 *)

A368841 Nonnegative integers whose binary expansions (without leading zeros) have no three equally spaced equal digits.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 18, 19, 20, 22, 25, 26, 27, 36, 37, 38, 41, 44, 45, 50, 51, 52, 54, 76, 82, 83, 90, 100, 101, 102, 108, 153, 165, 204

Offset: 1

Rémy Sigrist, Jan 07 2024

Also numbers k such that A368842(k) = 0.
Also numbers k such that A368857(k) < 3.
This sequence is finite by Van der Waerden's theorem.

Cf. A005346, A368842, A368857.

is(n, base = 2) = { my (d = digits(n, base)); for (i = 1, #d-2, forstep (j = i+2, #d, 2, if (d[i]==d[j] && d[i]==d[(i+j)/2], return (0);););); return (1); }

A378195 Number of 2-colorings of length n without an arithmetic progression of length 3.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 16, 6, 0

Offset: 0

Ethan Ji, Nov 19 2024

nonn

After 0, the sequence will continue to be 0. A sequence satisfying this property cannot have a subsequence which violates it, thus there must exist a sequence of length n-1 if there exists a sequence of length n.

			a(3) = 6 since we have [0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0].

First 0 index given by A005346.

Cf. A378196, A378197.

HasEquallySpacedKBits[bits_, k_] :=
 If[k == 1, True,
  Module[{n = Length[bits], found = False},
   Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
       bits[[start]]] == k, found = True; Break[]], {gap, 1,
     Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
   found]]
BitSequence[k_] :=
 Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
  ExtendSequence[seq_] :=
   Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
    newSeq1 = Join[seq, {1}];
    If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
    If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
    result];
  Function[targetN,
   Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
   While[n < targetN, n++;
    currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
    prevSequences = currSequences;
    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];];]]
BitSequence[3][9]
(* Ethan Ji, Nov 19 2024 *)

A378196 Number of 2-colorings of length n without an arithmetic progression of length 4.

Original entry on oeis.org

1, 2, 4, 8, 14, 26, 48, 78, 132, 230, 356, 548, 842, 1078, 1344, 1764, 1744, 1850, 1948, 1708, 1442, 1342, 1032, 702, 524, 316, 168, 136, 136, 144, 152, 160, 168, 176, 28, 0

Offset: 0

Ethan Ji, Nov 19 2024

nonn

After 0, the sequence will continue to be 0. A sequence satisfying this property cannot have a subsequence which violates it, thus there must exist a sequence of length n-1 if there exists a sequence of length n.

First 0 index given by A005346.

Cf. A378195, A378197.

HasEquallySpacedKBits[bits_, k_] :=
 If[k == 1, True,
  Module[{n = Length[bits], found = False},
   Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
       bits[[start]]] == k, found = True; Break[]], {gap, 1,
     Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
   found]]
BitSequence[k_] :=
 Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
  ExtendSequence[seq_] :=
   Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
    newSeq1 = Join[seq, {1}];
    If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
    If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
    result];
  Function[targetN,
   Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
   While[n < targetN, n++;
    currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
    prevSequences = currSequences;
    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];];]]
BitSequence[4][35]
(* Ethan Ji, Nov 19 2024 *)

cp's OEIS Frontend

A121894 Van der Waerden numbers: A005346(n) - 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A171081 Van der Waerden numbers w(3, n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A100042 a(n) = prime(n)*2^prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A135415 Van der Waerden numbers for 3-arithmetic progressions with n colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A171082 Van der Waerden numbers w(2;4,n).

Views

Author

Keywords

Links

Crossrefs

A350226 a(n) is the length of the longest sequence of distinct numbers in arithmetic progression in the interval 0..n, ending with n and where the Thue-Morse sequence (A010060) is constant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

A378197 Number of 2-colorings of length n without an arithmetic progression of length 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A368841 Nonnegative integers whose binary expansions (without leading zeros) have no three equally spaced equal digits.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A378195 Number of 2-colorings of length n without an arithmetic progression of length 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs