Conjecture de Scholz

Modèle:Voir homonymes Modèle:Ébauche 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(2^n-1)\le n-1+l\left(n\right)$

où l(n) est la longueur de la plus courte chaîne d'additions qui produit n, c'est-à-dire le plus petit entier m pour lequel il existe une suite $(v_0,\dots ,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(2^5-1)=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 :

$l(2^n-1)\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

• Modèle:En Shortest Addition Chains par Achim Flammenkamp, à l'université de Bielefeld
• Modèle:En Suite Modèle:OEIS2C de l'OEIS

Références

• Modèle:Article
• Modèle:Article