login
A018789
Number of subsets of { 1, ..., n } containing an arithmetic progression of length 4.
2
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
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
KEYWORD
nonn
STATUS
approved