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[1].

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 31e de tout nombre n utilisant seulement 7 multiplications, au lieu des 30 multiplications que l'on obtiendrait avec une multiplication répétée :

n2 = n × n
n3 = n2 × n
n6 = n3 × n3
n12 = n6 × n6
n24 = n12 × n12
n30 = n24 × n6
n31 = n30 × 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[2]. Il n'existe pas 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 additons 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[3] que

,

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[4]. Il est même possible que ait une chaîne plus courte que , donc que  ; le plus petit pour lequel cela se produit est [5], les suivants sont puis , (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[4].

Brauer a prouvé que

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é[6] : l(n) = l*(n) . Mais Hansen[7] a montré qu'il existe des valeurs de n avec l(n)  l*(n), tel que n = 26106 + 23048 + 22032 + 22016 + 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

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)[5]. Neil Clift a en outre vérifié qu'en fait pour tout [4].

Articles liés

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

Notes et références

Bibliographie

  • Donald E. Knuth, The Art of Computer Programming, vol. 2 : Seminumerical Algorithms, , 3e éd., Section 4.6.3.
  • (en) Richard K. Guy, Unsolved Problems in Number Theory, New York, Springer-Verlag, , 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 », (consulté le ).
  • François Bergeron, Jean Berstel et Srecko Brlek, « Efficient computation of addition chains », Journal de théorie des nombres de Bordeaux, vol. 6, no 1, , p. 21-38 (Math Reviews 1305286, zbMATH 0812.11072, lire en ligne, consulté le ).
  • Edward G. Thurber et Neill M. Clift, « Addition chains, vector chains, and efficient computation », Discrete Mathematics, vol. 344, no 2, , article no 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, no 1, , p. 1-12 (lire en ligne).

Liens externes

  • Arithmétique et théorie des nombres
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.