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,2

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

Links

Table of n, a(n) for n=1..43.

Example

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 }

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

Prog

(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]
(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

Crossrefs

Sequence in context: A348352 A007311 A031345 * A279953 A260523 A114625

Adjacent sequences: A206699 A206700 A206701 * A206703 A206704 A206705

Keyword

nonn,nice

Author

Dan Fodor, Feb 11 2012

Extensions

More terms from Joerg Arndt, Feb 11 2012

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

Status

approved