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

$l \left( 2^n - 1 \right) \le n - 1 + l \left( n \right)$

où l(n) est la longueur de la plus courte chaîne d'additions (en) qui produit n, c'est-à-dire le plus petit entier m pour lequel il existe une suite $(v_0,\ldots,v_m)$ telle que $v 0 = 1$ , $v m = n$ , et chaque $v i$ est de la forme $v j + v k$ avec $j, k < i$ .

Elle a été démontrée dans de nombreux cas, mais pas dans le cas général.

Par exemple pour n = 5 on a égalité, car l(5)=3 (puisque 1+1=2, 2+2=4, 4+1=5 et il n'existe pas de chaîne plus courte), l(31)=7 (1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+6=30, 30+1=31), et

$l \left( 2^5 - 1 \right) = 5 - 1 + l \left( 5 \right)$ .

Des considérations élémentaires sur la nature des chaînes d'additions et le codage binaire permettent d'établir l'inégalité suivante, plus faible (en) :

$l \left( 2^n - 1 \right) \le 2 (n - 1)$ ,

mais une preuve qui permettrait de remplacer par $l (n)$ l'un des deux « $n - 1$ » du majorant n'a pas encore été trouvée.

Liens externes

(en) Shortest Addition Chains par Achim Flammenkamp, à l'université de Bielefeld
(en) Suite A003313 de l'OEIS

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Scholz conjecture » (voir la liste des auteurs)
(de) Arnold Scholz (de), « Aufgabe 252 », dans Jahresber. Deutsche Math. Vereinigung, vol. 47 « Aufgaben und Lösungen », 1937, p. 41-42 [texte intégral]
(en) Alfred Brauer, « On addition chains », dans Bull. Amer. Math. Soc., vol. 45, 1939, p. 736-739 [texte intégral]

Portail des mathématiques

Catégories :

Conjecture non résolue
Arithmétique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Conjecture de Scholz de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

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
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
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) le; n − 1 + l ( n )where l ( n ) is the length of the shortest addition chain … Wikipedia
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
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
Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Conjecture de Scholz

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Conjecture de Scholz

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link