OP-00069 Open

Knuth–Stolarsky lower bound for addition chains

Let $\ell(n)$ be the length of a shortest addition chain for $n$, with $\ell(1) = 0$, and let $\nu(n)$ be the number of ones in the binary expansion of $n$. The inequality below holds for every $n$ with $\ell(n) - \lfloor \log_2 n \rfloor \le 3$, the last of these cases being Thurber's, and Schönhage proved $\ell(n) \ge \log_2 n + \log_2 \nu(n) - 2.13$.

Problem. Is $$\ell(n) \ge \lfloor \log_2 n \rfloor + \lceil \log_2 \nu(n) \rceil$$ for every $n \ge 1$?

Source: Knuth (The Art of Computer Programming, Vol. 2, §4.6.3) and Stolarsky (1969); see Altman (2018), Conjecture 1.7.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NT — Number Theory
Secondary: CO, NA
Keywords: addition chains, exponentiation, OpenProblemsInNLA
Literature checked: Oct. 2, 2026 by clemens-admin

References

@book{knuth1997,
  author    = {Knuth, Donald E.},
  title     = {The Art of Computer Programming, Vol. 2: Seminumerical Algorithms},
  edition   = {3rd},
  publisher = {Addison-Wesley},
  year      = {1997},
  note      = {Section 4.6.3},
}
@article{stolarsky1969,
  author  = {Stolarsky, Kenneth B.},
  title   = {A lower bound for the {S}cholz--{B}rauer problem},
  journal = {Canad. J. Math.},
  volume  = {21},
  year    = {1969},
  pages   = {675--683},
  doi     = {10.4153/CJM-1969-077-x},
}
@article{thurber1973,
  author  = {Thurber, Edward G.},
  title   = {The {S}cholz--{B}rauer problem on addition chains},
  journal = {Pacific J. Math.},
  volume  = {49},
  number  = {1},
  year    = {1973},
  pages   = {229--242},
  doi     = {10.2140/pjm.1973.49.229},
}
@article{schonhage1975,
  author  = {Sch{\"o}nhage, Arnold},
  title   = {A lower bound for the length of addition chains},
  journal = {Theoret. Comput. Sci.},
  volume  = {1},
  number  = {1},
  year    = {1975},
  pages   = {1--12},
  doi     = {10.1016/0304-3975(75)90008-0},
}
@article{altman2018,
  author  = {Altman, Harry},
  title   = {Internal structure of addition chains: well-ordering},
  journal = {Theoret. Comput. Sci.},
  volume  = {721},
  year    = {2018},
  pages   = {54--69},
  doi     = {10.1016/j.tcs.2017.12.002},
}
@misc{openproblemsinnla-ac08,
  author       = {Townsend, Alex},
  title        = {{AC-08}: Knuth–Stolarsky lower bound for addition chains},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-08/README.md},
  note         = {Read at commit e375a6f, 2026-09-30},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00069, "Knuth–Stolarsky lower bound for addition chains", clopen.solutions.