cp's OEIS Frontend

A005837 Lexicographically earliest increasing sequence of positive numbers that contains no 4-term arithmetic progression.

%I A005837 M0621 #50 Jan 04 2016 17:32:18
%S A005837 1,2,3,5,6,8,9,10,15,16,17,19,26,27,29,30,31,34,37,49,50,51,53,54,56,
%T A005837 57,58,63,65,66,67,80,87,88,89,91,94,99,102,105,106,109,110,111,122,
%U A005837 126,136,145,149,151,152,160,163,167,169,170,171,174,176,177,183,187,188,194,196
%N A005837 Lexicographically earliest increasing sequence of positive numbers that contains no 4-term arithmetic progression.
%C A005837 a(n) = A005839(n) + 1. - _Alois P. Heinz_, Jan 31 2014
%D A005837 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005837 Alois P. Heinz and Robert Israel, <a href="/A005837/b005837.txt">Table of n, a(n) for n = 1..10000</a> (n = 1..1001 from Alois P. Heinz)
%H A005837 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.
%p A005837 Noap:= proc(N,m)
%p A005837 # N terms of earliest increasing seq with no m-term arithmetic progression
%p A005837 local A,forbid,n,c,ds,j;
%p A005837 A:= Vector(N):
%p A005837 A[1..m-1]:= <($1..m-1)>:
%p A005837 forbid:= {m}:
%p A005837 for n from m to N do
%p A005837   c:= min({$A[n-1]+1..max(max(forbid)+1, A[n-1]+1)} minus forbid);
%p A005837   A[n]:= c;
%p A005837   ds:= convert(map(t -> c-t, A[m-2..n-1]),set);
%p A005837   for j from m-2 to 2 by -1 do
%p A005837     ds:= ds intersect convert(map(t -> (c-t)/j, A[m-j-1..n-j]),set);
%p A005837     if ds = {} then break fi;
%p A005837   od;
%p A005837   forbid:= select(`>`,forbid,c) union map(`+`,ds,c);
%p A005837 od:
%p A005837 convert(A,list)
%p A005837 end proc:
%p A005837 Noap(100,4); # _Robert Israel_, Jan 04 2016
%t A005837 t = {1, 2, 3}; Do[s = Table[Append[i, n], {i, Subsets[t, {3}]}]; If[! MemberQ[Table[Differences[i, 2], {i, s}], {0, 0}], AppendTo[t, n]], {n, 4, 200}]; t (* _T. D. Noe_, Apr 17 2014 *)
%Y A005837 Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
%Y A005837 3-term AP: A005836 (>=0), A003278 (>0);
%Y A005837 4-term AP: A005839 (>=0), A005837 (>0);
%Y A005837 5-term AP: A020654 (>=0), A020655 (>0);
%Y A005837 6-term AP: A020656 (>=0), A005838 (>0);
%Y A005837 7-term AP: A020657 (>=0), A020658 (>0);
%Y A005837 8-term AP: A020659 (>=0), A020660 (>0);
%Y A005837 9-term AP: A020661 (>=0), A020662 (>0);
%Y A005837 10-term AP: A020663 (>=0), A020664 (>0).
%K A005837 nonn
%O A005837 1,2
%A A005837 _N. J. A. Sloane_, _Jeffrey Shallit_
%E A005837 Edited by _M. F. Hasler_, Jan 03 2016. Further edited (with new offset) by _N. J. A. Sloane_, Jan 04 2016