login
Cardinality of a maximal subset S of {0,1,...,n-1} that does not contain x+y (mod n) or x*y (mod n) for x,y in S.
1

%I #15 Apr 04 2014 03:40:20

%S 0,0,1,1,2,2,2,2,3,4,4,4,4,4,6,4,4,6,4,8,7,8,6,8,10,8,9,8,8,12,8,10,

%T 12,8,11,11,10,8,12,10,10,12,10,11,11,12,10,12,14,10,11,13,12,16,11,

%U 16,11,12,12,15,14,12,18,20,12,12,12,17,16,18,12,18

%N Cardinality of a maximal subset S of {0,1,...,n-1} that does not contain x+y (mod n) or x*y (mod n) for x,y in S.

%H Giovanni Resta, <a href="/A113757/b113757.txt">Table of n, a(n) for n = 1..100</a>

%H Giovanni Resta, <a href="/A113757/a113757_1.txt">Examples of maximal subsets for n <= 100</a>

%e a(5)=2 since, (a) taking S={2,3} we have that 2+2=4,2+3=0,3+3=1,2*2=4,2*3=1,3*3=4 and 0,1,4 do not belong to S; (b) there is not a similar subset S with 3 elements, so S is maximal.

%t comb[n_, s_] := Union[Mod[Flatten@ Table[{s[[i]] + s[[j]], s[[i]] s[[j]]}, {i, Length[s]}, {j, i}], n]]; ric[n_, f_, s_] := Block[{}, If[Length@s > Length@mx, mx = s]; Do[ If[Intersection[Join[s, {i}], comb[n, Join[s, {i}]]] == {}, ric[n, i, Append[s, i]]], {i, f+1, n-1}]]; a[n_] := (mx = {}; ric[n, 1, {}]; Length@mx); Array[a, 24]

%K hard,nonn

%O 1,5

%A _Giovanni Resta_, Jan 17 2006

%E Extended by _Giovanni Resta_, Apr 03 2014