OFFSET
1,1
COMMENTS
A subset S of {0,1,2, ... n} is "irreducible" if it cannot be written as A + B = S for any A and B subsets of the integers with |A|, |B| >= 2. In this case, A + B is defined as the set of a + b for a in A and b in B.
Irreducible sets are also sometimes referred to as "Ostmann irreducible," "prime," or "primitive".
REFERENCES
M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Subsets, Springer 1996.
H. H. Ostmann, Additive Zahlentheorie, Springer 1956.
LINKS
Henry L. Fleischmann, Python Code
EXAMPLE
{0,1,2} is reducible since {0,1} + {0,1} = {0,1,2}. All other subsets of {0,1,2} are irreducible, so a(2) = 2. It is possible to reduce to the case of assuming every set contains only nonnegative integers and each set contains 0 by shifting the summand sets.
PROG
(Python) # See Fleischmann link.
(Python)
from itertools import combinations
from collections import Counter
from math import comb
def A349775sumsetgen(n): # generate sums of 2 subsets A, B with |A|, |B| >= 2
for l in range(2, n+2):
for a in combinations(range(n+1), l):
amax = max(a)
bmax = min(amax, n-amax)
for lb in range(2, bmax+2):
for b in combinations(range(bmax+1), lb):
yield tuple(sorted(set(x+y for x in a for y in b)))
def A349775(n):
c = Counter()
for s in set(A349775sumsetgen(n)):
c[len(s)] += 1
for i in range(n+1, 1, -1):
if c[i] < comb(n+1, i):
return i # Chai Wah Wu, Dec 14 2021
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Henry L. Fleischmann, Nov 29 2021
EXTENSIONS
a(25)-a(27) from Chai Wah Wu, Dec 14 2021
a(28) from Chai Wah Wu, Dec 17 2021
STATUS
approved