login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions. 1

%I

%S 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,

%T 36,106,1,11,2,4,14,40,2,4,86,307,20,1,4,14,41,99,266,674,1505,3510,

%U 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 = 1..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).

%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

%Y Cf. A003002, A065825.

%K nonn

%O 1,3

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 19 11:02 EDT 2019. Contains 327192 sequences. (Running on oeis4.)