cp's OEIS Frontend

A005838 Lexicographically earliest increasing sequence of positive numbers that contains no arithmetic progression of length 6.

%I A005838 M0516 #53 May 03 2016 16:56:35
%S A005838 1,2,3,4,5,7,8,9,10,12,13,14,15,17,18,19,20,22,23,24,25,26,33,34,35,
%T A005838 36,37,39,43,44,45,46,47,49,50,51,52,59,60,62,63,64,65,66,68,69,71,73,
%U A005838 77,85,87,88,89,90,91,93,96,97,98,99,100,103,104,107,111,114,115,117,118,120
%N A005838 Lexicographically earliest increasing sequence of positive numbers that contains no arithmetic progression of length 6.
%D A005838 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005838 Robert Israel, <a href="/A005838/b005838.txt">Table of n, a(n) for n = 1..10000</a>
%H A005838 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.
%F A005838 a(n) = A020656(n) + 1.
%p A005838 N:= 100: # to get a(1)..a(N)
%p A005838 A:= Vector(N):
%p A005838 A[1..5]:= <($1..5)>:
%p A005838 forbid:= {6}:
%p A005838 for n from 6 to N do
%p A005838   c:= min({$A[n-1]+1::max(max(forbid)+1, A[n-1]+1)} minus forbid);
%p A005838   A[n]:= c;
%p A005838   ds:= convert(map(t -> c-t, A[4..n-1],set);
%p A005838   if ds = {} then next fi;
%p A005838   ds:= ds intersect convert(map(t -> (c-t)/4, A[1..n-4]),set);
%p A005838   if ds = {} then next fi;
%p A005838   ds:= ds intersect convert(map(t -> (c-t)/3, A[2..n-3]),set);
%p A005838   if ds = {} then next fi;
%p A005838   ds:= ds intersect convert(map(t -> (c-t)/2, A[3..n-2]),set);
%p A005838   forbid:= select(`>`,forbid,c) union map(`+`,ds,c);
%p A005838 od:
%p A005838 convert(A,list); # _Robert Israel_, Jan 04 2016
%o A005838 (PARI) A005838(n,show=1,i=1,o=6,u=0)={for(n=1,n,show&&print1(i,",");u+=1<<i;while(i++,for(s=1,(i-1)\(o-1),for(j=1,o-1,bittest(u,i-s*j)||next(2));next(2));next(2)));i} \\ _M. F. Hasler_, Jan 03 2016
%Y A005838 Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
%Y A005838 3-term AP: A005836 (>=0), A003278 (>0);
%Y A005838 4-term AP: A005839 (>=0), A005837 (>0);
%Y A005838 5-term AP: A020654 (>=0), A020655 (>0);
%Y A005838 6-term AP: A020656 (>=0), A005838 (>0);
%Y A005838 7-term AP: A020657 (>=0), A020658 (>0);
%Y A005838 8-term AP: A020659 (>=0), A020660 (>0);
%Y A005838 9-term AP: A020661 (>=0), A020662 (>0);
%Y A005838 10-term AP: A020663 (>=0), A020664 (>0).
%K A005838 nonn
%O A005838 1,2
%A A005838 _N. J. A. Sloane_, _Jeffrey Shallit_
%E A005838 Name and links/references edited by _M. F. Hasler_, Jan 03 2016
%E A005838 Further edited by _N. J. A. Sloane_, Jan 04 2016