|
%I #35 Jul 31 2016 02:45:49
%S 1,2,3,5,7,14,16,30,38,70,81,150,164,317,365,651,693,1376,1357,2728,
%T 2647,5458,5094,10645,10098,20657,18208,39071,33615,79672,61311,
%U 146648,115069,281652,211979,528417,362458,1014026,644778,1979453,1146748,3633995,2008902
%N The number of subsets X of Zn such that for all u, v in X, u+v is not in X.
%C 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 a(5) = 7 because the following 7 subsets of {0,1,2,3,4} have the required property:
%e 1: { }
%e 2: { 1 }
%e 3: { 1, 4 }
%e 4: { 2 }
%e 5: { 2, 3 }
%e 6: { 3 }
%e 7: { 4 }
%p b:= proc(i, n, s) local si; si:= s union {i};
%p `if`(i=0, 1, b(i-1, n, s) +`if`({seq(seq(irem(k+j, n)
%p , j=si), k=si)} intersect si={}, b(i-1, n, si), 0))
%p end:
%p a:= n-> b(n-1, n, {}):
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Apr 24 2012
%t 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 (Haskell)
%o import Control.Monad
%o --this creates the powerset of a set
%o ps n = filterM (\x->[True,False]) n
%o --given a set z, this creates the set X of (a+b) for all a, b, in Z
%o addset z = do x<-z
%o y<-z
%o [x+y]
%o --this check if two sets are disjoint
%o disjoint a [] = True
%o disjoint a (c:d) = (disjoint a d) && ((filter (\x->x==c) a) ==[])
%o --this checks if a set z is disjoint from its "adsset" in a certain Zn, n being the second argument.
%o good z n = disjoint z (map (\x->rem x n) (addset z))
%o --this generates all off Zn's subsets with the required property.
%o sets n = filter (\x ->good x n) (ps [0..(n-1)])
%o --this generates the first n terms of the sequence
%o sequence n = map (\x->length(sets x) ) [1..n]
%o (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 nonn,nice
%O 1,2
%A _Dan Fodor_, Feb 11 2012
%E More terms from _Joerg Arndt_, Feb 11 2012
%E a(31)-a(43) from _Alois P. Heinz_, Apr 24 2012
|
