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,4

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.

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

Example

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.

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 *)

Crossrefs

Cf. A003002, A065825.

Last elements of rows of A334187.

Sequence in context: A028412 A156699 A245183 * A182236 A077819 A030313

Adjacent sequences: A262344 A262345 A262346 * A262348 A262349 A262350

Keyword

nonn

Author

Nathan McNew, Sep 18 2015

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

Status

approved