|
%I #31 Dec 17 2021 00:54:41
%S 2,2,3,4,4,5,6,7,8,9,9,10,11,12,13,14,15,15,16,17,18,19,20,21,22,23,
%T 23,24
%N The maximum cardinality of an irreducible subset of {0, 1, 2, ..., n}.
%C 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.
%C Irreducible sets are also sometimes referred to as "Ostmann irreducible," "prime," or "primitive".
%D M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Subsets, Springer 1996.
%D H. H. Ostmann, Additive Zahlentheorie, Springer 1956.
%H Henry L. Fleischmann, <a href="/A349775/a349775.txt">Python Code</a>
%e {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.
%o (Python) See link.
%o (Python)
%o from itertools import combinations
%o from collections import Counter
%o from math import comb
%o def A349775sumsetgen(n): # generate sums of 2 subsets A,B with |A|,|B| >= 2
%o for l in range(2,n+2):
%o for a in combinations(range(n+1),l):
%o amax = max(a)
%o bmax = min(amax,n-amax)
%o for lb in range(2,bmax+2):
%o for b in combinations(range(bmax+1),lb):
%o yield tuple(sorted(set(x+y for x in a for y in b)))
%o def A349775(n):
%o c = Counter()
%o for s in set(A349775sumsetgen(n)):
%o c[len(s)] += 1
%o for i in range(n+1,1,-1):
%o if c[i] < comb(n+1,i):
%o return i # _Chai Wah Wu_, Dec 14 2021
%K nonn,hard,more
%O 1,1
%A _Henry L. Fleischmann_, Nov 29 2021
%E a(25)-a(27) from _Chai Wah Wu_, Dec 14 2021
%E a(28) from _Chai Wah Wu_, Dec 17 2021
|
