cp's OEIS Frontend

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

%I A018788 #39 May 14 2021 02:47:46
%S A018788 0,0,0,1,3,9,24,63,150,343,746,1605,3391,7075,14624,30076,61385,
%T A018788 124758,252618,510161,1027632,2066304,4148715,8322113,16680369,
%U A018788 33413592,66904484,133923906,268009597,536257466,1072861536,2146225299,4293173040,8587388627
%N A018788 Number of subsets of {1,...,n} containing an arithmetic progression of length 3.
%H A018788 Fausto A. C. Cariboni, <a href="/A018788/b018788.txt">Table of n, a(n) for n = 0..80</a> (terms up to a(40) from Alois P. Heinz)
%H A018788 Wikipedia, <a href="https://en.wikipedia.org/wiki/Salem-Spencer_set">Salem-Spencer set</a>
%H A018788 <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F A018788 a(n) = 2^n - A051013(n). - _David Nacin_, Mar 03 2012
%e A018788 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
%t A018788 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 *)
%o A018788 (Python)
%o A018788 # Prints out all such sets
%o A018788 from itertools import combinations as comb
%o A018788 def containsap3(n):
%o A018788     ap3list=list()
%o A018788     for skip in range(1,(n+1)//2):
%o A018788         for start in range (1,n+1-2*skip):
%o A018788             ap3list.append(set({start,start+skip,start+2*skip}))
%o A018788     s=list()
%o A018788     for i in range(3,n+1):
%o A018788         for temptuple in comb(range(1,n+1),i):
%o A018788             tempset=set(temptuple)
%o A018788             for sub in ap3list:
%o A018788                 if sub <= tempset:
%o A018788                     s.append(tempset)
%o A018788                     break
%o A018788     return s #
%o A018788 # Counts all such sets
%o A018788 def a(n):
%o A018788     return len(containsap3(n)) # _David Nacin_, Mar 03 2012
%Y A018788 Cf. A051013.
%K A018788 nonn
%O A018788 0,5
%A A018788 _David W. Wilson_
%E A018788 a(33) from _Alois P. Heinz_, Jan 31 2014