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

n² = n × n

n³ = n² × n

n⁶ = n³ × n³

n¹² = n⁶ × n⁶

n²⁴ = n¹² × n¹²

n³⁰ = n²⁴ × n⁶

n³¹ = n³⁰ × n

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'=\lfloor n/2\rfloor$ . Si $n$ est pair, il peut être obtenu en une seule addition supplémentaire, par $n=n'+n'$. Si $n$ est impair, cette méthode utilise deux additions pour l'obtenir, en calculant d'abord $n-1=n'+n'$ 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\leq l(n)\leq \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)\leq 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 suite A230528 de l'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)\leq 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 n < 12509, il y a égalité : l(n) = l^*(n) . Mais Hansen a montré qu'il existe des valeurs de n avec l(n) ≠ l^*(n), tel que n = 2⁶¹⁰⁶ + 2³⁰⁴⁸ + 2²⁰³² + 2²⁰¹⁶ + 1 pour lequel l^*(n) = 6110, l(n) ≤ 6109 . 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

$l(2^{n}-1)\leq 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\leq 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\leq 64$.

Articles liés

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

Bibliographie

• Alfred Brauer, « On addition chains », Bulletin of the American Mathematical Society, vol. 45, n^o 10,‎ 1939, p. 736–739 (DOI 10.1090/S0002-9904-1939-07068-7, MR 0000245)
• Walter Hansen, « Zum Scholz-Brauerschen Problem », Journal für die reine und angewandte Mathematik, vol. 202,‎ 1959, p. 129-136
• Neill Michael Clift, « Calculating optimal addition chains », Computing, vol. 91, n^o 3,‎ 2011, p. 265–284 (DOI 10.1007/s00607-010-0118-8, lire en ligne).
• Peter Downey, Benton Leong et Ravi Sethi, « Computing sequences with addition chains », SIAM Journal on Computing, vol. 10, n^o 3,‎ 1981, p. 638–646 (DOI 10.1137/0210047).

• Donald E. Knuth, The Art of Computer Programming, vol. 2 : Seminumerical Algorithms, 1997, 3^e éd., Section 4.6.3.
• (en) Richard K. Guy, Unsolved Problems in Number Theory, New York, Springer-Verlag, 2004, 437 p. (ISBN 978-0-387-20860-2, OCLC 54611248, zbMATH 1058.11001, lire en ligne), Section C6 : "Addition Chains. Brauer Chains. Hansen Chains.".
• Achim Flammenkamp, « Shortest Addition Chains », 2020 (consulté le 1^er décembre 2020).
• François Bergeron, Jean Berstel et Srecko Brlek, « Efficient computation of addition chains », Journal de théorie des nombres de Bordeaux, vol. 6, n^o 1,‎ 1994, p. 21-38 (MR 1305286, zbMATH 0812.11072, lire en ligne, consulté le 1^er décembre 2020).
• Edward G. Thurber et Neill M. Clift, « Addition chains, vector chains, and efficient computation », Discrete Mathematics, vol. 344, n^o 2,‎ 2021, article n^o 112200 (DOI 10.1016/j.disc.2020.112200).
• Arnold Schönhage, « A Lower Bound for the Length of Addition Chains », Theoretical Computer Science, vol. 1, n^o 1,‎ 1975, p. 1-12 (lire en ligne).

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
• (en) Eric W. Weisstein, « Addition Chain », sur MathWorld