A185256 Stanley Sequence S(0,3).

0, 3, 4, 7, 9, 12, 13, 16, 27, 30, 31, 34, 36, 39, 40, 43, 81, 84, 85, 88, 90, 93, 94, 97, 108, 111, 112, 115, 117, 120, 121, 124, 243, 246, 247, 250, 252, 255, 256, 259, 270, 273, 274, 277, 279, 282, 283, 286, 324, 327, 328, 331, 333, 336, 337, 340, 351, 354, 355, 358, 360, 363

Offset: 1

Author

N. J. A. Sloane, Mar 19 2011

Keywords

• nonn

Comments

Given a finite increasing sequence V = [v_1, ..., v_k] containing no 3-term arithmetic progression, the Stanley Sequence S(V) is obtained by repeatedly appending the smallest term that is greater than the previous term and such that the new sequence also contains no 3-term arithmetic progression.

Examples

			After [0, 3, 4, 7, 9] the next term cannot be 10 or we would have the 3-term A.P. 4,7,10; it cannot be 11 because of 7,9,11; but 12 is OK.
		

References

• R. K. Guy, Unsolved Problems in Number Theory, E10.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..2048
• P. Erdos et al., Greedy algorithm, arithmetic progressions, subset sums and divisibility, Discrete Math., 200 (1999), 119-135.
• J. L. Gerver and L. T. Ramsey, Sets of integers with no long arithmetic progressions generated by the greedy algorithm, Math. Comp., 33 (1979), 1353-1359.
• R. A. Moy, On the growth of the counting function of Stanley sequences, arXiv:1101.0022 [math.NT], 2010-2012.
• R. A. Moy, On the growth of the counting function of Stanley sequences, Discrete Math., 311 (2011), 560-562.
• A. M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978.
• S. Savchev and F. Chen, A note on maximal progression-free sets, Discrete Math., 306 (2006), 2131-2133.
• Index entries for non-averaging sequences

Crossrefs

For other examples of Stanley Sequences see A005487, A005836, A187843, A188052, A188053, A188054, A188055, A188056, A188057.

See also A004793, A033160, A033163.

Programs

Maple

# Stanley Sequences, Discrete Math. vol. 311 (2011), see p. 560
ss:=proc(s1,M) local n,chvec,swi,p,s2,i,j,t1,mmm; t1:=nops(s1); mmm:=1000;
s2:=Array(1..t1+M,s1); chvec:=Array(0..mmm);
for i from 1 to t1 do chvec[s2[i]]:=1; od;
# Get n-th term:
for n from t1+1 to t1+M do # do 1
# Try i as next term:
for i from s2[n-1]+1 to mmm do # do 2
swi:=-1;
# Test against j-th term:
for j from 1 to n-2 do # do 3
p:=s2[n-j];
if 2*p-i < 0 then break; fi;
if chvec[2*p-i] = 1 then swi:=1; break; fi;
od; # od 3
if swi=-1 then s2[n]:=i; chvec[i]:=1; break; fi;
od; # od 2
if swi=1 then ERROR("Error, no solution at n = ",n); fi;
od; # od 1;
[seq(s2[i],i=1..t1+M)];
end;
ss([0,3],80);

Mathematica

ss[s1_, M_] := Module[{n, chvec, swi, p, s2, i, j, t1, mmm}, t1 = Length[s1]; mmm = 1000; s2 = Table[s1, {t1 + M}] // Flatten; chvec = Array[0&, mmm];
For[i = 1, i <= t1, i++, chvec[[s2[[i]] ]] = 1];
(* get n-th term *)
For[n = t1+1, n <= t1 + M, n++,
(* try i as next term *)
For[i = s2[[n-1]] + 1, i <= mmm, i++, swi = -1;
(* test against j-th term *)
For[j = 1, j <= n-2, j++, p = s2[[n - j]]; If[2*p - i < 0, Break[] ];
If[chvec[[2*p - i]] == 1, swi = 1; Break[] ] ];
If[swi == -1, s2[[n]] = i; chvec[[i]] = 1; Break[] ] ];
If[swi == 1, Print["Error, no solution at n = ", n] ] ];
Table[s2[[i]], {i, 1, t1 + M}] ];
ss[{0, 3}, 80] (* Jean-François Alcover, Sep 10 2013, translated from Maple *)

PARI

A185256(n,show=1,L=3,v=[0,3], D=v->v[2..-1]-v[1..-2])={while(#v1||next(2), 2); break)); if(type(show)=="t_VEC", v, v[n])} \\ 2nd (optional) arg: zero = silent, nonzero = verbose, vector (e.g. [] or [1]) = get the whole list [a(1..n)] as return value, else just a(n). - M. F. Hasler, Jan 18 2016