A066369 Number of subsets of {1, ..., n} with no four terms in arithmetic progression.

1, 2, 4, 8, 15, 29, 56, 103, 192, 364, 668, 1222, 2233, 3987, 7138, 12903, 22601, 40200, 71583, 125184, 218693, 386543, 670989, 1164385, 2021678, 3462265, 5930954, 10189081, 17266616, 29654738, 50912618, 86017601, 145327544, 247555043, 415598432, 698015188

Offset: 0

Author

Jan Kristian Haugland, Dec 22 2001

Keywords

• nonn

Examples

			a(5) = 29 because there are 32 subsets and three of them contain four terms in arithmetic progression: {1, 2, 3, 4}, {2, 3, 4, 5} and {1, 2, 3, 4, 5}.
		

Crossrefs

Cf. A051013, A018789.

Programs

Python

from sympy import subsets
def noap4(n):
    avoid=list()
    for skip in range(1,(n+2)//3):
        for start in range (1,n+1-3*skip):
            avoid.append(set({start,start+skip,start+2*skip,start+3*skip}))
    s=list()
    for i in range(4):
        for smallset in subsets(range(1,n+1),i):
            s.append(smallset)
    for i in range(4,n+1):
        for temptuple in subsets(range(1,n+1),i):
            tempset=set(temptuple)
            status=True
            for avoidset in avoid:
                if avoidset <= tempset:
                    status=False
                    break
            if status:
                s.append(tempset)
    return s
# Counts all such sets
def a(n):
    return len(noap4(n)) # David Nacin, Mar 05 2012

Formula

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

Extensions

a(31)-a(35) (using data in A018789) from Alois P. Heinz, Sep 08 2019