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,6

Links

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

Formula

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

Example

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

Prog

(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=", ")

Crossrefs

Cf. A066369.

Sequence in context: A026980 A026955 A093900 * A203413 A301604 A141799

Adjacent sequences: A018786 A018787 A018788 * A018790 A018791 A018792

Keyword

nonn

Author

David W. Wilson

Status

approved