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

0, 0, 0, 0, 1, 3, 8, 25, 64, 148, 356, 826, 1863, 4205, 9246, 19865, 42935, 90872, 190561, 399104, 829883, 1710609, 3523315, 7224223, 14755538, 30092167, 61177910, 124028647, 251168840, 507216174, 1022829206, 2061466047, 4149639752

Offset: 0

Author

David W. Wilson

Keywords

• nonn

Examples

			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
		

Links

• Sean A. Irvine, Table of n, a(n) for n = 0..39

Crossrefs

Cf. A066369.

Programs

Python

from itertools import combinations
# Prints out all such sets
def containsap4(n):
    ap4list = list()
    for skip in range(1, (n + 2) // 3):
        for start in range(1, n + 1 - 3 * skip):
            ap4list.append(
                set({start, start + skip, start + 2 * skip, start + 3 * skip})
            )
    s = list()
    for i in range(4, n + 1):
        for temptuple in combinations(range(1, n + 1), i):
            tempset = set(temptuple)
            for sub in ap4list:
                if sub <= tempset:
                    s.append(tempset)
                    break
    return s
# Counts all such sets
def a(n):
    return len(containsap4(n))  # David Nacin, Mar 05 2012
for n in range(20):
    print(a(n), end=", ")

Formula

a(n) = 2^n - A066369(n).