|
%I #51 May 30 2020 09:21:04
%S 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,
%T 12,36,106,1,11,2,4,14,40,2,4,86,307,20,1,4,14,41,99,266,674,1505,
%U 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
%N Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.
%C 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.
%H Fausto A. C. Cariboni, <a href="/A262347/b262347.txt">Table of n, a(n) for n = 0..140</a>
%H Fausto A. C. Cariboni, <a href="/A262347/a262347.txt">All sets that yield a(n) for n = 4..130.</a>, Feb 19 2018.
%H Janusz Dybizbanski, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p15">Sequences containing no 3-term arithmetic progressions</a>, The Electronic Journal of Combinatorics, 19, no. 2 (2012).
%H <a href="http://oeis.org/wiki/Index_to_OEIS:_Section_No#non_averaging">Index entries related to non-averaging sequences</a>
%e 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.
%p G:= proc(n, cons, t)
%p option remember;
%p local consn, consr;
%p if n < t or member({},cons) then return {} fi;
%p if t = 0 then return {{}} fi;
%p consn, consr:= selectremove(has,cons,n);
%p consn:= subs(n=NULL,consn);
%p procname(n-1,consr,t) union
%p map(`union`,procname(n-1,consr union consn,t-1),{n});
%p end proc:
%p F:= proc(n)
%p local m,cons,R;
%p m:= A003002(n-1);
%p cons:= {seq(seq({i,i+j,i+2*j},i=1..n-2*j),j=1..(n-1)/2)};
%p R:= G(n,cons,m+1);
%p if R = {} then
%p A003002(n):= m;
%p G(n,cons,m);
%p else
%p A003002(n):= m+1;
%p R
%p fi
%p end proc:
%p A003002(1):= 1:
%p a[1]:= 1:
%p for n from 2 to 40 do
%p a[n]:= nops(F(n))
%p od:
%p seq(a[i],i=1..40); # _Robert Israel_, Sep 20 2015
%t A003002 = Cases[Import["https://oeis.org/A003002/b003002.txt", "Table"], {_, _}][[All, 2]];
%t a[n_] := a[n] = Count[Subsets[Range[n], {A003002[[n+1]]}], s_ /; !MatchQ[s, {___, n1_, ___, n2_, ___, n3_, ___} /; n2 - n1 == n3 - n2]];
%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* _Jean-François Alcover_, May 30 2020 *)
%Y Cf. A003002, A065825.
%Y Last elements of rows of A334187.
%K nonn
%O 0,4
%A _Nathan McNew_, Sep 18 2015
%E a(25) to a(44) from _Robert Israel_, Sep 20 2015
%E a(45) to a(75) from _Fausto A. C. Cariboni_, Jan 15 2018
%E a(0)=1 prepended by _Alois P. Heinz_, May 16 2020
|
