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
Keywords
Examples
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
Links
- Sean A. Irvine, Table of n, a(n) for n = 0..39
Crossrefs
Cf. A066369.
Programs
-
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=", ")
Formula
a(n) = 2^n - A066369(n).