A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.

1, 1, 1, 3, 2, 1, 4, 10, 25, 4, 24, 7, 25, 6, 1, 4, 14, 43, 97, 220, 2, 18, 62, 232, 2, 33, 2, 12, 36, 106, 1, 11, 2, 4, 14, 40, 2, 4, 86, 307, 20, 1, 4, 14, 41, 99, 266, 674, 1505, 3510, 7726, 14, 50, 156, 2, 8, 26, 56, 2, 4, 6, 14, 48, 2, 4, 8, 16, 28, 108, 319, 1046, 4, 26, 82, 1, 2

Offset: 0

Author

Nathan McNew, Sep 18 2015

Keywords

• nonn

Comments

The sequence A003002 gives the size of the largest subset of the integers up to n that avoids three-term arithmetic progressions. This sequence gives the number of distinct subsets of [1..n] that have that size and are free of three-term arithmetic progressions.

Examples

			The largest subset of [1,6] that doesn't have any 3 terms in arithmetic progression has size 4. There are 4 such subsets with this property: {1,2,4,5}, {1,2,5,6}, {1,3,4,6} and {2,3,5,6}, so a(6)=4.
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..140
• Fausto A. C. Cariboni, All sets that yield a(n) for n = 4..130., Feb 19 2018.
• Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, The Electronic Journal of Combinatorics, 19, no. 2 (2012).
• Index entries related to non-averaging sequences

Crossrefs

Cf. A003002, A065825.

Last elements of rows of A334187.

Programs

Maple

G:= proc(n, cons, t)
option remember;
local consn, consr;
   if n < t or member({},cons) then return {} fi;
   if t = 0 then return {{}} fi;
   consn, consr:= selectremove(has,cons,n);
   consn:= subs(n=NULL,consn);
   procname(n-1,consr,t) union
      map(`union`,procname(n-1,consr union   consn,t-1),{n});
end proc:
F:= proc(n)
local m,cons,R;
   m:= A003002(n-1);
   cons:= {seq(seq({i,i+j,i+2*j},i=1..n-2*j),j=1..(n-1)/2)};
   R:= G(n,cons,m+1);
   if R = {} then
      A003002(n):= m;
      G(n,cons,m);
   else
      A003002(n):= m+1;
      R
   fi
end proc:
A003002(1):= 1:
a[1]:= 1:
for n from 2 to 40 do
  a[n]:= nops(F(n))
od:
seq(a[i],i=1..40); # Robert Israel, Sep 20 2015

Mathematica

A003002 = Cases[Import["https://oeis.org/A003002/b003002.txt", "Table"], {, }][[All, 2]];
a[n_] := a[n] = Count[Subsets[Range[n], {A003002[[n+1]]}], s_ /; !MatchQ[s, {_, n1_, _, n2_, _, n3_, _} /; n2 - n1 == n3 - n2]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, May 30 2020 *)

Extensions

a(25) to a(44) from Robert Israel, Sep 20 2015

a(45) to a(75) from Fausto A. C. Cariboni, Jan 15 2018

a(0)=1 prepended by Alois P. Heinz, May 16 2020