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  est une suite d'entiers naturels commençant par 1 et se terminant par , 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  de tout nombre  utilisant seulement 7 multiplications, au lieu des 30 multiplications que l'on obtiendrait avec une multiplication répétée :

 2 =  × 
 3 = 2 × 
 6 = 3 × 3
 12 = 6 × 6
 24 = 12 × 12
 30 = 24 × 6
 31 = 30 ×

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  est obtenu récursivement, à partir d'une chaîne d'addition pour  . Si  est pair, il peut être obtenu en une seule addition supplémentaire, par . Si  est impair, cette méthode utilise deux additions pour l'obtenir, en calculant d'abord  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 . Si   est un facteur premier de  , on peut obtenir une chaîne d'addition pour  en commençant par une chaîne pour , puis en y concaténant une chaîne pour , modifiée en multipliant chacun de ses nombres par . 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  (qu'il divise  ou non), on construit récursivement une chaîne pour , puis on concatène une chaîne pour  (modifiée comme ci-dessus) pour obtenir , 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  le plus petit entier  tel qu'il existe une chaîne d'addition de longueur  qui calcule  . Il est connu que

  ,

où  est le nombre de bits égaux à 1 dans le développement binaire de . 

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

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

 

où   est la longueur de la plus courte chaîne étoilée. Pour de nombreuses valeurs de n, et en particulier pour tout , il y a égalité :  . Mais Hansen a montré qu'il existe des valeurs de n avec , tel que  pour lequel   . 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 

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

 

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  est un nombre de Hansen (alors que 5784689 ne l'est pas). Neil Clift a en outre vérifié qu'en fait  pour tout .

Articles liés 

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

Notes et références

Bibliographie 
 
 
 
 .
 .

 .
 .
 .
 .
 .
 .

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
 

Arithmétique