Finding small sets of integers in which every element is a sum of two others This is a follow-up to this question on math.stackexchange.

Let us say that a non-empty set S&nbsp;&sube;&nbsp;&#8484; is self-supporting if for every a&nbsp;&isin;&nbsp;S, there exist distinct elements b,c&nbsp;&isin;&nbsp;S such that a&nbsp;=&nbsp;b&nbsp;+&nbsp;c. For positive integers n, simple examples include the ideal S&nbsp;=&nbsp;n&#8484;, or (for n&gt;3) the integer interval [&minus;n,&nbsp;n].

We'll say that S is strongly self-supporting if S is disjoint from &minus;S: that is, if a&nbsp;&isin;&nbsp;S, then &minus;a&nbsp;&notin;&nbsp;S. Neither of the above examples are strongly self-supporting, because they are in fact closed under negation.
There exist finite sets which are strongly self-supporting: for instance, the sets
{−22,&nbsp;−20,&nbsp;−18,&nbsp;−16,&nbsp;−14,&nbsp;−12,&nbsp;−10,&nbsp;−2,&nbsp;1,&nbsp;3,&nbsp;7,&nbsp;8,&nbsp;15,&nbsp;23} and  {−10,&nbsp;−8,&nbsp;−6,&nbsp;−2,&nbsp;1,&nbsp;3,&nbsp;4,&nbsp;5}.

Question #1. For a positive integer N&gt;0, does there exist a poly(N)-time [or polylog(N)-time] algorithm to either (i)&nbsp;produce a strongly self-supporting set whose maximum absolute value is N, or (ii)&nbsp;determine that no such set exists? [Edit:&nbsp;as pointed out in the oldest answer&nbsp;+&nbsp;my comment on it, there always exists such a set for N&nbsp;&ge;&nbsp;10.]

Question #2. For N&gt;0, can you construct the strongly self-supporting set with maximum absolute value N, and which has the fewest possible elements?
I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)

Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.

We can do that easily if we construct the same for N-1, and then add N to the resulting set.

For the base case of 23, we can start with your example set.

To bring the size down, we should be able to use a similar approach: 

Construct sets which contain 1, N and N-1.

We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows: 


If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.
If N is odd construct a set for N-1 and N to resulting set.


For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 &lt; N &lt;= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.

In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.

It might be interesting to prove some lower bounds in the case N is prime.