login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A206702 The number of subsets X of Zn such that for all u, v in X, u+v is not in X. 0
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 (list; graph; refs; listen; history; text; internal format)
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: A294727 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 15 20:49 EDT 2018. Contains 313779 sequences. (Running on oeis4.)