A set $S$ of positive integers satisfies the following conditions:
- $1 \in S$ is the smallest element and $n \in S$ is the largest element in $S$.
- If $w \in S$ and $w > 1$, there exist $x, y, z \in S$ such that $w = x + y + z$.
Problem: What is the minimum number of elements $S$ can contain?
EDIT: I removed a wrong claim here. This problem seems to be known as finding the minimum cardinality of an addition chain and seems to be very difficult, even for the case where the second condition from above is replaced by $w = x + y$. The answers are known to OEIS: https://oeis.org/A079300.
In the above problem, $S$ must contain only odd numbers. Take the smallest even number $w \in S$. Since $w = x + y + z$ with $x, y, z \in S$ and $1 \le x, y, z < w$, all $x$, $y$ and $z$ must be odd. So $w$ is odd, contradiction.
If $1 = s_1 < s_2 < \dots < s_k = n$ denote the elements of $S$, it holds $\displaystyle s_i \ge \left\lceil \frac{s_{i + 1}}{3} \right\rceil$ for $1 \le i < k$. In case of $n$ being a power of $3$, these estimates are sharp and the answer is $1 + \log_3(n)$.
Note that I want to find the exact number. It is not necessary to obtain a closed-form expression though. I appreciate any help on this question.