A262347 - OEIS

%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