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

1, 2, 3, 5, 7, 14, 16, 30, 38, 70, 81, 150, 164, 317, 365, 651, 693, 1376, 1357, 2728, 2647, 5458, 5094, 10645, 10098, 20657, 18208, 39071, 33615, 79672, 61311, 146648, 115069, 281652, 211979, 528417, 362458, 1014026, 644778, 1979453, 1146748, 3633995, 2008902

Offset: 1

Author

Dan Fodor, Feb 11 2012

Keywords

• nonn
• nice

Comments

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

Examples

			a(5) = 7 because the following 7 subsets of {0,1,2,3,4} have the required property:
  1:  { }
  2:  { 1 }
  3:  { 1, 4 }
  4:  { 2 }
  5:  { 2, 3 }
  6:  { 3 }
  7:  { 4 }
		

Programs

Haskell

import Control.Monad
--this creates the powerset of a set
ps n = filterM (\x->[True,False]) n
--given a set z, this creates the set X of (a+b) for all a, b, in Z
addset z = do x<-z
              y<-z
              [x+y]
--this check if two sets are disjoint
disjoint a [] = True
disjoint a (c:d) = (disjoint a d) && ((filter (\x->x==c) a) ==[])
--this checks if a set z is disjoint from its "adsset" in a certain Zn, n being the second argument.
good z n = disjoint z (map (\x->rem x n) (addset z))
--this generates all off Zn's subsets with the required property.
sets n = filter (\x ->good x n) (ps [0..(n-1)])
--this generates the first n terms of the sequence
sequence n = map (\x->length(sets x) ) [1..n]

Maple

b:= proc(i, n, s) local si; si:= s union {i};
      `if`(i=0, 1, b(i-1, n, s) +`if`({seq(seq(irem(k+j, n)
           , j=si), k=si)} intersect si={}, b(i-1, n, si), 0))
    end:
a:= n-> b(n-1, n, {}):
seq(a(n), n=1..25);  # Alois P. Heinz, Apr 24 2012

Mathematica

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 *)

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

Extensions

More terms from Joerg Arndt, Feb 11 2012

a(31)-a(43) from Alois P. Heinz, Apr 24 2012