Let $n \in \mathbb{N}$ be a positive integer. Can you find one of the smallest sets $S \subset \mathbb{N}$ containing $n$ such that $1 \in S$, and for every $c \in S, c \neq 1$, there exist $a \in S$ and $b \in S$ such that $a + b = c$? ($a$ can equal $b$)
For example, I think the following sets are examples of such sets for $n = 15$:
$$\{ 1, 2, 3, 6, 12, 15 \}$$ $$\{ 1, 2, 4, 5, 10, 15 \}$$
I'm looking for a way to find small sets with that property for really large $n$ (like on the order of 256 bits).
I know of a way to find an upper bound on this problem which can be readily derived from looking at the binary representation of a number: let $1b_1b_2\dots b_k$ be the representation of $n$. Then, starting with the set $\{1\}$, and a value $v = 1$, go through the bits one by one, setting $v \leftarrow v + v$ and adding $v$ to the set if the bit is zero, and setting $v \leftarrow v + v + 1$ and adding $v - 1$ and $v$ to the set if the bit is one. For example, for $54$, which has a binary representation of $110110_2$, this process finds a set with 9 elements:
$$\{1, 2, 3, 6, 12, 13, 26, 27, 54\}$$
or
$$\{1_2, 10_2, 11_2, 110_2, 1100_2, 1101_2, 11010_2, 11011_2, 110110_2\}$$
In this case, this process does not find the smallest such set, which may be a set with 8 elements:
$$\{1, 2, 3, 6, 12, 24, 48, 54\}$$
That potential solution was reached by using the fact $110_2$ "repeats" in the binary representation of 54, so for that reason, I suspect a solution to this might involve compression.
You are attempting to find the minimal length addition chain, which is a difficult problem we do not know how to solve optimally efficiently.