cp's OEIS Frontend

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

%I A066369 #19 May 15 2021 11:46:00
%S A066369 1,2,4,8,15,29,56,103,192,364,668,1222,2233,3987,7138,12903,22601,
%T A066369 40200,71583,125184,218693,386543,670989,1164385,2021678,3462265,
%U A066369 5930954,10189081,17266616,29654738,50912618,86017601,145327544,247555043,415598432,698015188
%N A066369 Number of subsets of {1, ..., n} with no four terms in arithmetic progression.
%F A066369 a(n) = 2^n - A018789(n).
%e A066369 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 A066369 (Python)
%o A066369 from sympy import subsets
%o A066369 def noap4(n):
%o A066369     avoid=list()
%o A066369     for skip in range(1,(n+2)//3):
%o A066369         for start in range (1,n+1-3*skip):
%o A066369             avoid.append(set({start,start+skip,start+2*skip,start+3*skip}))
%o A066369     s=list()
%o A066369     for i in range(4):
%o A066369         for smallset in subsets(range(1,n+1),i):
%o A066369             s.append(smallset)
%o A066369     for i in range(4,n+1):
%o A066369         for temptuple in subsets(range(1,n+1),i):
%o A066369             tempset=set(temptuple)
%o A066369             status=True
%o A066369             for avoidset in avoid:
%o A066369                 if avoidset <= tempset:
%o A066369                     status=False
%o A066369                     break
%o A066369             if status:
%o A066369                 s.append(tempset)
%o A066369     return s
%o A066369 # Counts all such sets
%o A066369 def a(n):
%o A066369     return len(noap4(n)) # _David Nacin_, Mar 05 2012
%Y A066369 Cf. A051013, A018789.
%K A066369 nonn
%O A066369 0,2
%A A066369 _Jan Kristian Haugland_, Dec 22 2001
%E A066369 a(31)-a(35) (using data in A018789) from _Alois P. Heinz_, Sep 08 2019