A211316 Maximal size of sum-free set in additive group of integers mod n.

1, 1, 2, 2, 3, 2, 4, 3, 5, 4, 6, 4, 7, 6, 8, 6, 9, 6, 10, 7, 11, 8, 12, 10, 13, 9, 14, 10, 15, 10, 16, 12, 17, 14, 18, 12, 19, 13, 20, 14, 21, 14, 22, 18, 23, 16, 24, 16, 25, 18, 26, 18, 27, 22, 28, 19, 29, 20, 30, 20, 31, 21, 32, 26, 33, 22, 34, 24, 35, 24

Offset: 2

Author

N. J. A. Sloane, Apr 24 2012

Keywords

• nonn

References

• Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, Manuscript, May 2017. See Table in Section 1.6.1.
• A. P. Street, Counting non-isomorphic sum-free sets, in Proc. First Australian Conf. Combinatorial Math., Univ. Newcastle, 1972, pp. 141-143.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 2..10000
• Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Table in Section 1.6.1.
• Ben Green and Imre Z. Ruzsa, Sum-free sets in abelian groups, arXiv:math/0307142 [math.CO], 2004.

Crossrefs

Bisection: A211317. Cf. A007865, A027748, A003627.

Programs

Haskell

a211316 n | not $ null ps = n * (head ps + 1) `div` (3 * head ps)
          | m == 0        = n'
          | otherwise     = (n - 1) `div` 3
          where ps = [p | p <- a027748_row n, mod p 3 == 2]
                (n',m) = divMod n 3
-- Reinhard Zumkeller, Apr 25 2012

Mathematica

a[n_] := Module[{f = FactorInteger[n][[All, 1]]}, For[i = 1, i <= Length[f], i++, If[Mod[f[[i]], 3]==2, Return[n*(f[[i]] + 1)/3/f[[i]]]]]; If[Mod[n, 3] == 1, n-1, n]/3]
Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Aug 02 2018, from PARI *)

PARI

a(n)=my(f=factor(n)[,1]); for(i=1,#f, if(f[i]%3==2, return(n*(f[i]+1)/3/f[i]))); if(n%3, n-1, n)/3 \\ Charles R Greathouse IV, Sep 02 2015

Formula

If n is divisible by a prime == 2 mod 3 then a(n) = n(p+1)/(3p) where p is the smallest such prime divisor; otherwise if n is divisible by 3 then a(n) = n/3; otherwise all prime divisors of n are == 1 mod 3 and a(n) = (n-1)/3.

In particular, a(2n) = n (cf. A211317).