A018788 Number of subsets of {1,...,n} containing an arithmetic progression of length 3.

0, 0, 0, 1, 3, 9, 24, 63, 150, 343, 746, 1605, 3391, 7075, 14624, 30076, 61385, 124758, 252618, 510161, 1027632, 2066304, 4148715, 8322113, 16680369, 33413592, 66904484, 133923906, 268009597, 536257466, 1072861536, 2146225299, 4293173040, 8587388627

Offset: 0

Author

David W. Wilson

Keywords

• nonn

Examples

			For n=4 the only subsets containing an arithmetic progression of length 3 are {1,2,3}, {2,3,4} and {1,2,3,4}.  Thus a(4) = 3. - _David Nacin_, Mar 03 2012
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..80 (terms up to a(40) from Alois P. Heinz)
• Wikipedia, Salem-Spencer set
• Index entries related to non-averaging sequences

Crossrefs

Cf. A051013.

Programs

Mathematica

a[n_] := a[n] = Count[Subsets[Range[n], {3, n}], {_, a_, _, b_, _, c_, _} /; b-a == c-b]; Table[Print[n, " ", a[n]]; a[n], {n, 0, 32}] (* Jean-François Alcover, May 30 2019 *)

Python

# Prints out all such sets
from itertools import combinations as comb
def containsap3(n):
    ap3list=list()
    for skip in range(1,(n+1)//2):
        for start in range (1,n+1-2*skip):
            ap3list.append(set({start,start+skip,start+2*skip}))
    s=list()
    for i in range(3,n+1):
        for temptuple in comb(range(1,n+1),i):
            tempset=set(temptuple)
            for sub in ap3list:
                if sub <= tempset:
                    s.append(tempset)
                    break
    return s #
# Counts all such sets
def a(n):
    return len(containsap3(n)) # David Nacin, Mar 03 2012

Formula

a(n) = 2^n - A051013(n). - David Nacin, Mar 03 2012

Extensions

a(33) from Alois P. Heinz, Jan 31 2014