If we define $\lambda(n)=\lfloor \log_2(n) \rfloor$ and $v(n)$ as the binary digit sum of positive integer $n$ we can make a toy example of what I think is the most important conjecture in addition chains (The Knuth-Stolarsky conjecture).
We define a set of integer shifts: $1\le \sigma_1 \le \sigma_2 \le ... \le \sigma_r$.
$n=\prod_{i=1}^{r}(2^{\sigma_{i}}+1)$
$m=\prod_{i=1}^{r-1}(2^{\sigma_{i}}+1)$
$\lambda(n)-\sum_{i=1}^{r}\sigma_{i}=c$
The conjecture is that $v(n)\le 2^{r-c} $
I have a hand waving argument that if you can prove this toy example you prove a big part of the original conjecture. It's easy to prove this conjecture for small $r$ (base cases) or $c=0$. Under the assumption that $n$ is a counter example with smallest $r$ we force the structure of the product to have a certain form:
$\lambda(\prod_{i=1}^{r}(1+2^{-\sigma_{i}}))=c$
$\lambda(\prod_{i=1}^{r-1}(1+2^{-\sigma_{i}}))=c-1$
It's well known that $v$ is sub-additive and this is what people have used to try and attack this problem:
$v(a+b)\le v(a)+v(b)$
There is though a pretty trivial relationship. $v(n)\le \lambda(n)+1$. You can't have more bits in a number than it has slots for those bits. Under addition it gets more interesting:
$v(a+b) \le \lambda(a) + 1$ with $a\ge b$
$v(a+b) \le \lambda(b) + 1$ with $a\ge b, \lambda(a+b)=\lambda(a)+1$
I haven't seen these stated before and would welcome any pointers to similar things.
We can then restate our problem I think as a convex optimization problem (relaxation to reals):
maximize $ \sum_{i=1}^{r-1}\sigma_{i}$
Subject to: $2^{c-1}\le \prod_{i=1}^{r-1}(1+2^{-\sigma_{i}})<2^c$, $2^c\le (2^{-\sigma_{r-1}}+1)\prod_{i=1}^{r-1}(1+2^{-\sigma_{i}})<2^{c+1}$
So $2^{r-c}<v(n)\le \lambda(m)+1=\sum_{i=1}^{r-1}\sigma_{i}+c$.
Maybe from looking at this problem I can prove that $\sum_{i=1}^{r-1}\sigma_{i}\le2^{r-c}-c$. Computer searches (of small $r$) fail to find cases except for all $\sigma_i=1$. We can eliminate these cases by realizing that $(2^1+1)(2^1+1)=2^3+1$.
Mathematica tells me for small values of $r$ the products are convex but I haven't sat down to try and prove they are in general. This is new to me. Do people think it might be fruitful to see what tools are used in convex optimization in the hopes it helps prove this result. This is totally new to me. I have worked with linear and integer programming only. Tips on proving convexity for these products would be welcome. This doesn't seem like a trivial restatement of the problem as the last step (multiply by $2^{\sigma_r} +1$) doesn't matter. It would seem very important in the original formulation.
