cp's OEIS Frontend

A185256 Stanley Sequence S(0,3).

%I A185256 #53 Apr 20 2023 11:05:39
%S A185256 0,3,4,7,9,12,13,16,27,30,31,34,36,39,40,43,81,84,85,88,90,93,94,97,
%T A185256 108,111,112,115,117,120,121,124,243,246,247,250,252,255,256,259,270,
%U A185256 273,274,277,279,282,283,286,324,327,328,331,333,336,337,340,351,354,355,358,360,363
%N A185256 Stanley Sequence S(0,3).
%C A185256 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.
%D A185256 R. K. Guy, Unsolved Problems in Number Theory, E10.
%H A185256 Alois P. Heinz, <a href="/A185256/b185256.txt">Table of n, a(n) for n = 1..2048</a>
%H A185256 P. Erdos et al., <a href="http://dx.doi.org/10.1016/S0012-365X(98)00385-9">Greedy algorithm, arithmetic progressions, subset sums and divisibility</a>, Discrete Math., 200 (1999), 119-135.
%H A185256 J. L. Gerver and L. T. Ramsey, <a href="http://dx.doi.org/10.1090/S0025-5718-1979-0537982-0">Sets of integers with no long arithmetic progressions generated by the greedy algorithm</a>, Math. Comp., 33 (1979), 1353-1359.
%H A185256 R. A. Moy, <a href="http://arxiv.org/abs/1101.0022">On the growth of the counting function of Stanley sequences</a>, arXiv:1101.0022 [math.NT], 2010-2012.
%H A185256 R. A. Moy, <a href="http://dx.doi.org/10.1016/j.disc.2010.12.019">On the growth of the counting function of Stanley sequences</a>, Discrete Math., 311 (2011), 560-562.
%H A185256 A. M. Odlyzko and R. P. Stanley, <a href="https://math.mit.edu/~rstan/papers/od.pdf">Some curious sequences constructed with the greedy algorithm</a>, 1978.
%H A185256 S. Savchev and F. Chen, <a href="http://dx.doi.org/10.1016/j.disc.2006.04.008">A note on maximal progression-free sets</a>, Discrete Math., 306 (2006), 2131-2133.
%H A185256 <a href="http://oeis.org/wiki/Index_to_OEIS:_Section_No#non_averaging">Index entries for non-averaging sequences</a>
%e A185256 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.
%p A185256 # Stanley Sequences, Discrete Math. vol. 311 (2011), see p. 560
%p A185256 ss:=proc(s1,M) local n,chvec,swi,p,s2,i,j,t1,mmm; t1:=nops(s1); mmm:=1000;
%p A185256 s2:=Array(1..t1+M,s1); chvec:=Array(0..mmm);
%p A185256 for i from 1 to t1 do chvec[s2[i]]:=1; od;
%p A185256 # Get n-th term:
%p A185256 for n from t1+1 to t1+M do # do 1
%p A185256 # Try i as next term:
%p A185256 for i from s2[n-1]+1 to mmm do # do 2
%p A185256 swi:=-1;
%p A185256 # Test against j-th term:
%p A185256 for j from 1 to n-2 do # do 3
%p A185256 p:=s2[n-j];
%p A185256 if 2*p-i < 0 then break; fi;
%p A185256 if chvec[2*p-i] = 1 then swi:=1; break; fi;
%p A185256 od; # od 3
%p A185256 if swi=-1 then s2[n]:=i; chvec[i]:=1; break; fi;
%p A185256 od; # od 2
%p A185256 if swi=1 then ERROR("Error, no solution at n = ",n); fi;
%p A185256 od; # od 1;
%p A185256 [seq(s2[i],i=1..t1+M)];
%p A185256 end;
%p A185256 ss([0,3],80);
%t A185256 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];
%t A185256 For[i = 1, i <= t1, i++, chvec[[s2[[i]] ]] = 1];
%t A185256 (* get n-th term *)
%t A185256 For[n = t1+1, n <= t1 + M, n++,
%t A185256 (* try i as next term *)
%t A185256 For[i = s2[[n-1]] + 1, i <= mmm, i++, swi = -1;
%t A185256 (* test against j-th term *)
%t A185256 For[j = 1, j <= n-2, j++, p = s2[[n - j]]; If[2*p - i < 0, Break[] ];
%t A185256 If[chvec[[2*p - i]] == 1, swi = 1; Break[] ] ];
%t A185256 If[swi == -1, s2[[n]] = i; chvec[[i]] = 1; Break[] ] ];
%t A185256 If[swi == 1, Print["Error, no solution at n = ", n] ] ];
%t A185256 Table[s2[[i]], {i, 1, t1 + M}] ];
%t A185256 ss[{0, 3}, 80] (* _Jean-François Alcover_, Sep 10 2013, translated from Maple *)
%o A185256 (PARI) A185256(n,show=1,L=3,v=[0,3], D=v->v[2..-1]-v[1..-2])={while(#v<n, show&&print1(v[#v]", "); v=concat(v, v[#v]); while(v[#v]++, forvec(i=vector(L, j, [if(j<L, j, #v), #v]), #Set(D(vecextract(v, i)))>1||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
%Y A185256 For other examples of Stanley Sequences see A005487, A005836, A187843, A188052, A188053, A188054, A188055, A188056, A188057.
%Y A185256 See also A004793, A033160, A033163.
%K A185256 nonn
%O A185256 1,2
%A A185256 _N. J. A. Sloane_, Mar 19 2011