Scholz's conjecture

Statement:

Let \(l(n)\) be the length of the shortest addition chain producing \(n\). Then \((2^n-1)\leq n-1+l(n)\).

Author	Date Published
Arnold Scholz	1937

Partial Results:

Clift in 2011 [2] showed that the conjecture is true for all \(n<5784689\).

Related Problems:

References:

[1] Scholz, Arnold (1937), "Aufgaben und Lösungen, 253", Jahresbericht der Deutschen Mathematiker-Vereinigung, 47: 41–42, ISSN 0012-0456

[2] Clift, Neill Michael (2011). "Calculating optimal addition chains". Computing. 91 (3): 265–284. doi:10.1007/s00607-010-0118-8.

[3] Brauer, Alfred (1939), "On addition chains", Bulletin of the American Mathematical Society, 45 (10): 736–739, doi:10.1090/S0002-9904-1939-07068-7, ISSN 0002-9904, MR 0000245, Zbl 0022.11106

[4] Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 169–171. ISBN 978-0-387-20860-2. Zbl 1058.11001.

Keywords:

addition chain;