- Scholz conjecture
In
mathematics , the Scholz conjecture (sometimes called the Scholz-Brauer conjecture or the Brauer-Scholz conjecture) is aconjecture from1937 stating that:"l"(2"n"−1) ≤ "n" − 1 + "l"("n")where "l"("n") is the length of the shortestaddition 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"(25−1) = 5−1+"l"(5).
Simple number-theoretic investigation into the nature of the addition chain and the binary representation of a number allows us to prove this weaker inequality::"l"(2"n"−1) ≤ "2n" − 2A proof reducing one of the "n"s to an "l"("n") has yet to be found.
References
*Scholz, A., "Jahresbericht" "Deutsche Math. Vereinigung" 1937 pp. 41-42
*Brauer, A. T., "On addition chains" "Bull. Amer. Math. Soc." 1939 pp. 637-739ee also
*
Proof of weak Scholz conjecture External links
* [http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html Shortest addition chains]
* [http://www.research.att.com/projects/OEIS?Anum=A003313 OEIS sequence A003313]
Wikimedia Foundation. 2010.
