login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%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_