La complexité d'un nombre entier est le nombre minimal de 1 nécessaires pour écrire ce nombre en n'utilisant que :
- le nombre 1 ;
- l'addition ;
- la multiplication ;
- des parenthèses.
Les informations figurant dans cet article ou cette section doivent être reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (septembre 2024).
Quelques exemples
modifier- Il est évident que 1+1=2 est l'écriture la plus simple, donc la complexité de 2 est 2.
- 4 = 1+1+1+1, mais aussi 4=(1+1)×(1+1). Cependant, aucune écriture de 4 n'est possible avec moins de quatre 1.
- 6 = 3×2 = (1+1+1)×(1+1) donc la complexité de 6 est 3+2=5.
Propriétés
modifierOn déduit assez simplement de la définition un premier résultat, en notant C(n) la complexité d'un entier n.
Propriété — Si a, b et c sont des entiers naturels tels que a = b×c, alors C(a)≤C(b)+C(c)
Cette propriété peut être combinée avec la décomposition en produit de facteurs premiers : la complexité d'un nombre est inférieure ou égale à la somme des complexités de ses facteurs premiers. Par exemple, 9 = 32 donc C(9) ≤ C(3)+C(3), donc C(9)≤6. Seule une analyse plus poussée permet de conclure que C(9) = 6.
Cependant, ce dernier résultat n'est pas optimal : la complexité de 23 est 11, celle de 2 est 2. Or 46 = (1+1+1)×(1+1+1)×((1+1)×(1+1)+1)+1 : la complexité de 46 est 12.
Un algorithme
modifierEn utilisant les propriétés ci-dessus et la remarque que chaque nombre premier est égal au nombre précédent+1, on peut s'approcher de la complexité en suivant l'algorithme récursif ci-dessous :
- si n est premier, on applique l'algorithme à n-1 (la complexité de n étant inférieure ou égale à celle de n, moins 1);
- si n n'est pas premier, on l'applique à chacun de ses facteurs premiers.
Jusqu'à obtenir des nombres dont on connaît la complexité. Ensuite, on additionne les résultats trouvés.
Cet algorithme donne un majorant de la complexité. Appliqué à 235, il donne 19 alors que la complexité de 235 est 17.
Algorithme parfait ?
modifierIl est bien sûr possible, en théorie, de trouver un algorithme pour calculer la complexité d'un nombre n : il suffit de tester toutes les combinaisons possibles de n (ou moins) signes 1 avec + , × et parenthèses. Mais la complexité (de l'algorithme, cette fois) est exponentielle. On peut réduire la complexité de l'algorithme en décomposant n en facteurs premiers, mais cela revient à résoudre le problème de la décomposition en produit de facteurs premiers d'un nombre, qui est tout aussi complexe. Et cela ne résout pas le problème du calcul de la complexité d'un nombre premier.
Bibliographie
modifier- (en) R. K. Guy, Expressing Numbers Using Just Ones
- (en) Ed Pegg, Jr. (en), Math Games: Integer Complexity, 12/04/2004, sur le site de la MAA
- (en) La suite des complexités des premiers entiers : suite A005245 de l'OEIS
