Some results on addition/subtraction chains (Q1063631)

Let \(\ell (n)\) (respectively \({\bar \ell}(n))\) be the length of the shortest addition chain respectively addition/subtraction chain for n. We present several results on \({\bar \ell}(n)\). In particular, we determine \({\bar \ell}(n)\) for all n satisfying \(\bar s(\)n)\(\leq 3\) and show \(\lfloor \log n\rfloor +2\leq {\bar \ell}(n)\) for all n satisfying \(\bar s(\)n)\(\geq 3\), where \(\bar s(\)n) is the extended sum of digits of n. These results are based on analogous results for \(\ell (n)\) and on the following two inequalities: \(| n| \leq 2^{d-1} F_{f+3}<2^{k- b}\) and \(f+b\geq \log \bar s(n)\) for a chain of length \(k=d+f+b\) with d doublings, f short steps, and b back steps for n. Moreover, we show that the difference \(\ell (n)-{\bar \ell}(n)\) (respectively \({\bar \ell}(n)- \lceil \log n\rceil)\) can be made arbitrarily large. In addition, we prove that \({\bar \ell}(m)\leq {\bar \ell}(-m)\leq {\bar \ell}(m)+1\) for \(m>0\) and characterize the case \({\bar \ell}(-m)={\bar \ell}(m)\). Finally, we determine \({\bar \ell}_ k(n_ 1,...,n_ k)\), the k- dimensional generalization of \({\bar \ell}\), with the help of \({\bar \ell}(n_ 1,...,n_ k)\), the k-element generalization of \({\bar \ell}\).