login
A066369
Number of subsets of {1, ..., n} with no four terms in arithmetic progression.
1
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
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
Sequence in context: A374743 A224959 A108564 * A239555 A275544 A000078
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(31)-a(35) (using data in A018789) from Alois P. Heinz, Sep 08 2019
STATUS
approved