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