A140516 For definition see comments lines.

1, 3, 6, 8, 9, 13, 16, 17, 19, 20, 21, 26, 31, 32, 36, 42, 43, 45, 49, 50, 52, 53, 54, 58, 62, 65, 66, 67, 71, 78, 80, 82, 85, 87, 89, 90, 97, 98, 103, 106, 108, 112, 113, 114, 116, 120, 122, 123, 124, 128, 129, 134, 135, 139, 141, 143, 145, 147, 148, 153, 155, 157, 161

Offset: 1

Author

Reed Kelly, Jul 01 2008

Keywords

• nonn

Comments

Inspired by Van der Waerden's Theorem, the positive integers are partitioned into two disjoint sequences, A and B, so that they obey the following rules:

Rule 1: For a given n, let A(n) and B(n) be the subsets of A and B with terms less than or equal to n. Any maximal arithmetic subsequence of A(n) must have at least as many terms as any maximal arithmetic subsequence of B(n).

Rule 2: Construct the sequences by starting at 1 and always favoring to add terms to B, unless it violates Rule 1. Add terms to A if they cannot be added to B.

The sequence listed here is the A sequence.

Examples

			A gets 1, because B cannot yet have an AS of length 1.
B gets 2, because we favor adding to B and A already has an AS of length 1.
A gets 3, because B cannot yet form an AS of length 2.
B gets 4, because A now has an AS of length 2.
B gets 5, because 2,4,5 does not contain an AS of length 3.
A gets 6, because 2,4,5,6 would contain an AS of length 3.
		

Programs

Mathematica

CheckMaxASFromEnd[A_,x_,m_] := Module[{i,n=Length[A],d,k}, If[ m>n+1, Return[False];,]; If[ And[ m<=n+1, n < 2], Return[True];,]; For[ i=n, i>0, i--, d = x-A[[i]]; bot = x-(m-1)*d; If[ bot <= 0, Break[];,]; For[ k=x-2*d, k>=x-(m-1)*d, k -= d, If[ MemberQ[A,k], If[ k == x-(m-1)*d, Return[True];,];, Break[]; ]; ]; ]; False ];
ASRace[n_] := Module[{i,m=0,A={},B={}}, For[i=1,i <= n, i++, If[ CheckMaxASFromEnd[B,i,m+1], If[ CheckMaxASFromEnd[A,i,m+1], m++, ]; A = Append[A,i];, B = Append[B,i]; ]; ]; {A,B} ];