cp's OEIS Frontend

A206702 The number of subsets X of Zn such that for all u, v in X, u+v is not in X.

%I A206702 #35 Jul 31 2016 02:45:49
%S A206702 1,2,3,5,7,14,16,30,38,70,81,150,164,317,365,651,693,1376,1357,2728,
%T A206702 2647,5458,5094,10645,10098,20657,18208,39071,33615,79672,61311,
%U A206702 146648,115069,281652,211979,528417,362458,1014026,644778,1979453,1146748,3633995,2008902
%N A206702 The number of subsets X of Zn such that for all u, v in X, u+v is not in X.
%C A206702 Since the empty set and all the singletons except {0} have the required property, a(n) >= n.  And clearly a(n) <= 2^n, since there are only 2^n possible subsets. - _Michael B. Porter_, Feb 11 2012
%e A206702 a(5) = 7 because the following 7 subsets of {0,1,2,3,4} have the required property:
%e A206702   1:  { }
%e A206702   2:  { 1 }
%e A206702   3:  { 1, 4 }
%e A206702   4:  { 2 }
%e A206702   5:  { 2, 3 }
%e A206702   6:  { 3 }
%e A206702   7:  { 4 }
%p A206702 b:= proc(i, n, s) local si; si:= s union {i};
%p A206702       `if`(i=0, 1, b(i-1, n, s) +`if`({seq(seq(irem(k+j, n)
%p A206702            , j=si), k=si)} intersect si={}, b(i-1, n, si), 0))
%p A206702     end:
%p A206702 a:= n-> b(n-1, n, {}):
%p A206702 seq(a(n), n=1..25);  # _Alois P. Heinz_, Apr 24 2012
%t A206702 b[i_, n_, s_] := Module[{si = s ~Union~ {i}}, If[i == 0, 1, b[i-1, n, s] + If[ Flatten[ Table[ Table[ Mod[k+j, n], {j, si}], {k, si}]] ~ Intersection~ si == {}, b[i-1, n, si], 0]]]; a[n_] := a[n] = b[n-1, n, {}]; Table[ Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 40}] (* _Jean-François Alcover_, Jun 07 2013, translated and adapted from _Alois P. Heinz_'s Maple program *)
%o A206702 (Haskell)
%o A206702 import Control.Monad
%o A206702 --this creates the powerset of a set
%o A206702 ps n = filterM (\x->[True,False]) n
%o A206702 --given a set z, this creates the set X of (a+b) for all a, b, in Z
%o A206702 addset z = do x<-z
%o A206702               y<-z
%o A206702               [x+y]
%o A206702 --this check if two sets are disjoint
%o A206702 disjoint a [] = True
%o A206702 disjoint a (c:d) = (disjoint a d) && ((filter (\x->x==c) a) ==[])
%o A206702 --this checks if a set z is disjoint from its "adsset" in a certain Zn, n being the second argument.
%o A206702 good z n = disjoint z (map (\x->rem x n) (addset z))
%o A206702 --this generates all off Zn's subsets with the required property.
%o A206702 sets n = filter (\x ->good x n) (ps [0..(n-1)])
%o A206702 --this generates the first n terms of the sequence
%o A206702 sequence n = map (\x->length(sets x) ) [1..n]
%o A206702 (PARI) a(n)=if(n<4, return(n)); my(u,v=vector(n-2,i,[i]),s=n,t); while(#v, u=List(); for(i=1,#v, t=v[i]; for(m=t[#t]+1,n, if(setsearch(t,2*m%n)==0 && #setintersect(Set(vector(#t,k,t[k]+m)%n),t)==0 && #setintersect(vector(#t,k,m-t[#t-k+1]),t)==0, listput(u, concat(t, m))))); v=Vec(u); s+=#v); s \\ _Charles R Greathouse IV_, Jul 31 2016
%K A206702 nonn,nice
%O A206702 1,2
%A A206702 _Dan Fodor_, Feb 11 2012
%E A206702 More terms from _Joerg Arndt_, Feb 11 2012
%E A206702 a(31)-a(43) from _Alois P. Heinz_, Apr 24 2012