Scholz conjecture

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"n"−1) ≤ "n" − 1 + "l"("n")where "l"("n") is the length of 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"(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-739

ee 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Proof of weak Scholz conjecture — In mathematics, a weaker version of the Scholz conjecture about addition chains can be proven without advanced number theory. In fact, proving the inequality: l (2 n − 1) le; 2n − 2is simple, providing some basic observations are made.First of… …   Wikipedia

  • Scholz — is a German surname.* Rupert Scholz (born 1937), German politician * Heiko Scholz(born 1966) * Donald Thomas Scholz (born 1947), guitarist * Jackson Scholz (1897 1986), American athlete * Franz Scholz (1909 1998) priest and professor of theology… …   Wikipedia

  • Conjecture de Scholz — En mathématiques, la conjecture de Scholz, parfois appelée conjecture de Scholz Brauer ou conjecture de Brauer Scholz, fut proposée en 1937. Elle prétend que où l(n) est la longueur de la plus courte chaîne d additions (en) qui produit n, c… …   Wikipédia en Français

  • Conjecture De Scholz — En mathématiques, la conjecture de Scholz, parfois appelée conjecture de Scholz Brauer ou conjecture de Brauer Scholz, fut proposée en 1937. Elle prétend que où l(n) est la plus courte chaîne d additions qui vaut n. Elle a été démontrée dans de… …   Wikipédia en Français

  • Conjecture de scholz — En mathématiques, la conjecture de Scholz, parfois appelée conjecture de Scholz Brauer ou conjecture de Brauer Scholz, fut proposée en 1937. Elle prétend que où l(n) est la plus courte chaîne d additions qui vaut n. Elle a été démontrée dans de… …   Wikipédia en Français

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • Liste Des Conjectures Mathématiques — Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős, qui liste les conjectures de Paul… …   Wikipédia en Français

  • Liste des conjectures — mathématiques Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős, qui liste les… …   Wikipédia en Français

  • Liste des conjectures mathematiques — Liste des conjectures mathématiques Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős,… …   Wikipédia en Français

  • Liste des conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős, qui liste les conjectures de Paul… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”