Complexité d'un nombre entier

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.

Quelques exemples

• 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

On 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 = 3² 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

En 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 ?

Il 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

• (en) Guy, R. K., Expressing Numbers Using Just Ones
• (en) MAA On Line
• La suite des complexités des premiers entiers sur le site de l'Encyclopédie des suites.