A113757 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.

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, 12, 8, 11, 11, 10, 8, 12, 10, 10, 12, 10, 11, 11, 12, 10, 12, 14, 10, 11, 13, 12, 16, 11, 16, 11, 12, 12, 15, 14, 12, 18, 20, 12, 12, 12, 17, 16, 18, 12, 18

Offset

1,5

Links

Giovanni Resta, Table of n, a(n) for n = 1..100

Giovanni Resta, Examples of maximal subsets for n <= 100

Example

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.

Mathematica

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]

Crossrefs

Sequence in context: A171482 A132015 A120501 * A291270 A291267 A261221

Adjacent sequences: A113754 A113755 A113756 * A113758 A113759 A113760

Keyword

hard,nonn

Author

Giovanni Resta, Jan 17 2006

Extensions

Extended by Giovanni Resta, Apr 03 2014

Status

approved