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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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 November 23 19:03 EST 2017. Contains 295128 sequences.