Scholz conjecture

In mathematics, the Scholz conjecture (sometimes called the Scholz-Brauer conjecture or the Brauer-Scholz conjecture) is a conjecture from 1937 stating that

l(2ⁿ−1) ≤ n − 1 + l(n)

where l(n) is the shortest addition chain producing n. It has been proved for many cases, but in general remains open.

As an example, l(5)=3 (since 1+1=2, 2+2=4, 4+1=5, and there is no shorter chain) and l(31)=7 (since 1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+6=30, 30+1=31, and there is no shorter chain), so

l(2⁵−1) = 5−1+l(5).

External links

• Shortest addition chains (http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html)
• OEIS sequence A003313 (http://www.research.att.com/projects/OEIS?Anum=A003313)

References

• Scholz, A., "Jahresbericht" Deutsche Math. Vereingung 1937 pp. 41-42
• Brauer, A. T., "On addition chains" Bull. Amer. Math. Soc. 1939 pp. 637-739

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.