The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066369 Number of subsets of {1, ..., n} with no four terms in arithmetic progression. 1


%S 1,2,4,8,15,29,56,103,192,364,668,1222,2233,3987,7138,12903,22601,

%T 40200,71583,125184,218693,386543,670989,1164385,2021678,3462265,

%U 5930954,10189081,17266616,29654738,50912618,86017601,145327544,247555043,415598432,698015188

%N Number of subsets of {1, ..., n} with no four terms in arithmetic progression.

%F a(n) = 2^n - A018789(n).

%e a(5) = 29 because there are 32 subsets and three of them contain four terms in arithmetic progression: {1, 2, 3, 4}, {2, 3, 4, 5} and {1, 2, 3, 4, 5}.

%o (Python)

%o def noap4(n):

%o .avoid=list()

%o .for skip in range(1,(n+2)//3):

%o ..for start in range (1,n+1-3*skip):

%o ...avoid.append(set({start,start+skip,start+2*skip,start+3*skip}))

%o .s=list()

%o .for i in range(4):

%o ..for smallset in comb(range(1,n+1),i):

%o ...s.append(smallset)

%o .for i in range(4,n+1):

%o ..for temptuple in comb(range(1,n+1),i):

%o ...tempset=set(temptuple)

%o ...status=True

%o ...for avoidset in avoid:

%o ....if avoidset <= tempset:

%o .....status=False

%o .....break

%o ...if status:

%o ....s.append(tempset)

%o .return s

%o #Counts all such sets

%o def a(n):

%o .return len(noap4(n)) # _David Nacin_, Mar 05 2012

%Y Cf. A051013, A018789.

%K nonn

%O 0,2

%A _Jan Kristian Haugland_, Dec 22 2001

%E a(31)-a(35) (using data in A018789) from _Alois P. Heinz_, Sep 08 2019

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 26 20:09 EDT 2020. Contains 337374 sequences. (Running on oeis4.)