Chaîne d'additions

En mathématiques, et particulièrement en arithmétique, une chaîne d'additions pour le calcul d'un entier positif Modèle:Mvar est une suite d'entiers naturels commençant par 1 et se terminant par Modèle:Mvar, et telle que chaque entier de la suite est la somme de deux entiers précédents. La longueur de la chaîne d'additions est le nombre de sommes nécessaires pour exprimer ces entiers ; c'est un de moins que le nombre de termes dans la suite.

Exemples

La suite (1,2,3,6,12,24,30,31) est une chaîne d'additions pour l'entier 31 de longueur 7 puisque :

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Les chaînes d'additions peuvent être utilisées pour l'exponentiation avec des exposants entiers en utilisant un nombre de multiplications égal à la longueur d'une chaîne d'addition pour l'exposant. Par exemple, la chaîne d'addition pour 31 conduit à une méthode de calcul de la puissance Modèle:31e de tout nombre Modèle:Mvar utilisant seulement 7 multiplications, au lieu des 30 multiplications que l'on obtiendrait avec une multiplication répétée :

Modèle:Mvar² = Modèle:Mvar × Modèle:Mvar

Modèle:Mvar³ = Modèle:Mvar² × Modèle:Mvar

Modèle:Mvar⁶ = Modèle:Mvar³ × Modèle:Mvar³

Modèle:Mvar¹² = Modèle:Mvar⁶ × Modèle:Mvar⁶

Modèle:Mvar²⁴ = Modèle:Mvar¹² × Modèle:Mvar¹²

Modèle:Mvar³⁰ = Modèle:Mvar²⁴ × Modèle:Mvar⁶

Modèle:Mvar³¹ = Modèle:Mvar³⁰ × Modèle:Mvar

Méthodes de construction des chaînes d'additions

Le calcul d'une chaîne d'addition de longueur minimale n'est pas facile ; une variante généralisée du problème, dans laquelle il faut trouver une chaîne pour un ensemble de valeurs, est un problème NP-complet. Il n'existe pas d'algorithme connu qui calcule une chaîne d'addition minimale pour un nombre donné en temps raisonnable ou de faible utilisation de la mémoire. En revanche, plusieurs techniques sont connues pour calculer des chaînes relativement courtes, même si elles ne sont pas toujours optimales.

Une technique bien connue pour calculer des chaînes d'addition relativement courtes est la méthode binaire, similaire à l'exponentiation par élevage au carré. Dans cette méthode, une chaîne d'addition pour le nombre $n$ est obtenu récursivement, à partir d'une chaîne d'addition pour $n^{\prime }=\lfloor n/2\rfloor$ . Si $n$ est pair, il peut être obtenu en une seule addition supplémentaire, par $n=n^{\prime }+n^{\prime }$. Si $n$ est impair, cette méthode utilise deux additions pour l'obtenir, en calculant d'abord $n-1=n^{\prime }+n^{\prime }$ puis en ajoutant 1.

La méthode par factorisation pour obtenir une chaîne d'additions est basée sur la décomposition en produit de facteurs premiers du nombre $n$. Si $p$ est un facteur premier de $n$ , on peut obtenir une chaîne d'addition pour $n$ en commençant par une chaîne pour $n/p$, puis en y concaténant une chaîne pour $p$, modifiée en multipliant chacun de ses nombres par $n/p$. La méthode factorielle et la méthode binaire peuvent être combinées dans ce qui est appelé la méthode m-aire de Brauer : on choisit un entier $m$ (qu'il divise $n$ ou non), on construit récursivement une chaîne pour $\lfloor n/m\rfloor$, puis on concatène une chaîne pour $m$ (modifiée comme ci-dessus) pour obtenir $m\lfloor n/m\rfloor$, et enfin on ajoute le reste. Des améliorations supplémentaires de ces idées conduisent à une famille de méthodes appelées les méthodes de la fenêtre glissante.

Longueur de chaîne

On note $l(n)$ le plus petit entier $s$ tel qu'il existe une chaîne d'addition de longueur $s$ qui calcule $n$ . Il est connu que

${\log }_2(n)+{\log }_2(\nu (n))-2.13\le l(n)\le {\log }_2(n)+{\log }_2(n)(1+o(1))/{\log }_2({\log }_2(n))$ ,

où $\nu (n)$ est le nombre de bits égaux à 1 dans le développement binaire de $n$.

On peut obtenir une chaîne d'addition pour $2n$ à partir d'une chaîne d'addition pour $n$ en ajoutant la somme supplémentaire $2n=n+n$, d'où il résulte que $l(2n)\le l(n)+1$. Cependant, on n'a pas toujours égalité, car dans certains cas $2n$ peut avoir une chaîne plus courte que celle obtenue de cette manière. Par exemple, $l(382)=l(191)=11$, comme observé par Knuth. Il est même possible que $2n$ ait une chaîne plus courte que $n$, donc que $l(2n)<l(n)$ ; le plus petit $n$ pour lequel cela se produit est $n=375494703$, les suivants sont $602641031$ puis $619418303$, (c'est la Modèle:OEIS).

Chaîne de Brauer

Une chaîne de Brauer ou chaîne d'additions étoilée est une chaîne d'addition dans laquelle chacune des sommes utilisées pour calculer ses termes utilise le terme immédiatement précédent. Un nombre de Brauer est un nombre pour lequel une chaîne de Brauer est optimale.

Brauer a prouvé que

$l^{*}(2^n-1)\le n-1+l^{*}(n)$

où $l^{*}$ est la longueur de la plus courte chaîne étoilée. Pour de nombreuses valeurs de n, et en particulier pour tout Modèle:Formule, il y a égalité : Modèle:Formule . Mais Hansen a montré qu'il existe des valeurs de n avec Modèle:Formule, tel que Modèle:Formule pour lequel Modèle:Formule . Le plus petit de ces entiers n est 12509. Une chaîne de Hansen est une chaîne d'additions pour laquelle il existe un sous-ensemble H de termes tel que tout élément de la chaîne utilise le plus grand élément dans H qui lui est inférieur. Un nombre de Hansen est un entier qui admet une chaîne minimale qui est une chaîne de Hansen. Par exemple,

1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082, 4164, 8328, 12492, 12509

est une chaîne de Hansen pour 12509 et ce n'est pas une chaîne étoilée.

Conjecture de Scholz

Modèle:Loupe La conjecture de Scholz (parfois appelée conjecture de Scholz-Brauer ou de Brauer-Scholz ), du nom d' Arnold Scholz et d'Alfred T. Brauer), est une conjecture datant de 1937 et indiquant que

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

Cette inégalité est connue pour être vraie pour tous les nombres dits entiers de Hansen, une généralisation des entiers de Brauer. Neill Clift a vérifié par ordinateur que tout $n\le 5784688$ est un nombre de Hansen (alors que 5784689 ne l'est pas). Neil Clift a en outre vérifié qu'en fait $l(2^n-1)=n-1+l(n)$ pour tout $n\le 64$.

Articles liés

• Chaîne d'addition-soustraction
• Chaîne d'addition vectorielle
• Chaîne de Lucas

Bibliographie

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

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Lien web.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Liens externes

• Shortest Addition Chains
• OEIS:Numbers n such that a shortest addition chain for 2*n is shorter than one for n
• OEIS:Length of shortest addition chain for n
• Modèle:MathWorld