cp's OEIS Frontend

A018789 Number of subsets of { 1, ..., n } containing an arithmetic progression of length 4.

%I A018789 #25 Mar 20 2023 14:12:09
%S A018789 0,0,0,0,1,3,8,25,64,148,356,826,1863,4205,9246,19865,42935,90872,
%T A018789 190561,399104,829883,1710609,3523315,7224223,14755538,30092167,
%U A018789 61177910,124028647,251168840,507216174,1022829206,2061466047,4149639752
%N A018789 Number of subsets of { 1, ..., n } containing an arithmetic progression of length 4.
%H A018789 Sean A. Irvine, <a href="/A018789/b018789.txt">Table of n, a(n) for n = 0..39</a>
%F A018789 a(n) = 2^n - A066369(n).
%e A018789 In {1,2,3,4,5} the only length 4 progressions possible are 1,2,3,4 and 2,3,4,5.  There are three sets containing one or more of these: {1,2,3,4},{2,3,4,5}, and {1,2,3,4,5}.  Thus a(5) = 3. - _David Nacin_, Mar 05 2012
%o A018789 (Python)
%o A018789 from itertools import combinations
%o A018789 # Prints out all such sets
%o A018789 def containsap4(n):
%o A018789     ap4list = list()
%o A018789     for skip in range(1, (n + 2) // 3):
%o A018789         for start in range(1, n + 1 - 3 * skip):
%o A018789             ap4list.append(
%o A018789                 set({start, start + skip, start + 2 * skip, start + 3 * skip})
%o A018789             )
%o A018789     s = list()
%o A018789     for i in range(4, n + 1):
%o A018789         for temptuple in combinations(range(1, n + 1), i):
%o A018789             tempset = set(temptuple)
%o A018789             for sub in ap4list:
%o A018789                 if sub <= tempset:
%o A018789                     s.append(tempset)
%o A018789                     break
%o A018789     return s
%o A018789 # Counts all such sets
%o A018789 def a(n):
%o A018789     return len(containsap4(n))  # _David Nacin_, Mar 05 2012
%o A018789 for n in range(20):
%o A018789     print(a(n), end=", ")
%Y A018789 Cf. A066369.
%K A018789 nonn
%O A018789 0,6
%A A018789 _David W. Wilson_