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

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, 36, 37, 39, 43, 44, 45, 46, 47, 49, 50, 51, 52, 59, 60, 62, 63, 64, 65, 66, 68, 69, 71, 73, 77, 85, 87, 88, 89, 90, 91, 93, 96, 97, 98, 99, 100, 103, 104, 107, 111, 114, 115, 117, 118, 120

Offset: 1

Author

N. J. A. Sloane, Jeffrey Shallit

Keywords

• nonn

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• 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.

Crossrefs

Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):

3-term AP: A005836 (>=0), A003278 (>0);

4-term AP: A005839 (>=0), A005837 (>0);

5-term AP: A020654 (>=0), A020655 (>0);

6-term AP: A020656 (>=0), A005838 (>0);

7-term AP: A020657 (>=0), A020658 (>0);

8-term AP: A020659 (>=0), A020660 (>0);

9-term AP: A020661 (>=0), A020662 (>0);

10-term AP: A020663 (>=0), A020664 (>0).

Programs

Maple

N:= 100: # to get a(1)..a(N)
A:= Vector(N):
A[1..5]:= <($1..5)>:
forbid:= {6}:
for n from 6 to N do
  c:= min({$A[n-1]+1::max(max(forbid)+1, A[n-1]+1)} minus forbid);
  A[n]:= c;
  ds:= convert(map(t -> c-t, A[4..n-1],set);
  if ds = {} then next fi;
  ds:= ds intersect convert(map(t -> (c-t)/4, A[1..n-4]),set);
  if ds = {} then next fi;
  ds:= ds intersect convert(map(t -> (c-t)/3, A[2..n-3]),set);
  if ds = {} then next fi;
  ds:= ds intersect convert(map(t -> (c-t)/2, A[3..n-2]),set);
  forbid:= select(`>`,forbid,c) union map(`+`,ds,c);
od:
convert(A,list); # Robert Israel, Jan 04 2016

PARI

A005838(n,show=1,i=1,o=6,u=0)={for(n=1,n,show&&print1(i,",");u+=1<M. F. Hasler, Jan 03 2016

Formula

a(n) = A020656(n) + 1.

Extensions

Name and links/references edited by M. F. Hasler, Jan 03 2016

Further edited by N. J. A. Sloane, Jan 04 2016