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

Links

Table of n, a(n) for n=0..35.

Formula

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

Example

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}.

Prog

(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

Crossrefs

Cf. A051013, A018789.

Sequence in context: A335473 A224959 A108564 * A239555 A275544 A000078

Adjacent sequences: A066366 A066367 A066368 * A066370 A066371 A066372

Keyword

nonn

Author

Jan Kristian Haugland, Dec 22 2001

Extensions

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

Status

approved