Bonjour, début de réflexion sur les chiffres de 0 à 9
0 -> 4 (+4)
1 -> 2 (+1)
2 -> 4 (+2)
3 -> 5 (+2)
4 -> 6 (+2)
5 -> 4 (-1)
6 -> 3 (-3)
7 -> 4 (-3)
8 -> 4 (-4)
9 -> 5 (-5)
On peut commencer la liste:
(+1-1):
1+5
(+2-1-1):
(2,3,4)+5+5
(+1+1-1-1): on trouve 1+1+5+5 combinaison de deux fois 1+5(déjà fait car on peut simplifier (+1-1) ...
(+1+2-3):
1+(2,3,4)+(6,7)
(+1+2-1-1-1) combinaison de (+2-1-1) et (+1-1)
(+1+1+1-3)
1+1+1+(6,7)
(+1+1+1-1-1-1) combinaison de 3 fois (+1-1)
(+4-4):
0+8
(+4-1-3):
0+5+(6,7)
(+4-1-1-1-1)
0+5+5+5+5
(+2+2-4):
(2,3,4)x2+8
(+2+2-1-3):
(2,3,4)x2+5+(6,7)
(+1+1+2-4):
1+1+(2,3,4)+8
(+1+1+1+1-4):
1x4 + 8
(+4+1-5):
0+1+9
(beaucoup de possibilités avec un +4+1, mais pas d'autre solution "première" car on ne peut pas avoir de -1 (combinaison avec +1-1) et il n'y a pas de -2
(+1+2+2-5):
0+(2,3,4)x2 + 9
(+4+2-1-5):
0+(2,3,4)+5+9
(+4+2-3-3):
0+(2,3,4)+(6,7)x2
(+4+1+1-3-3):
0+1x2+(6,7)x2
...
et ainsi de suite jusqu'à ce que l'on ne trouve plus de solutions premières...
L'une des dernières doit être quelque chose comme (+4+4+4+4-5-5-5) (mais je ne suis pas sûr)

Tout cela me laisse penser que l'on peut trouver un algorithme assez efficace facilement.

Quelques problèmes à régler:
démontrer que pour un nombre d'entiers donné (ici de 0 à 9), on peut trouver un nombre fini de combinaison (je pense qu'un peu de Bézout fera l'affaire...)
Edit:
Ca va, c'était pas trop dur, comme il y a un nombre fini d'entiers, il y a un nombre fini de différences (les +4+1+2+2+2-1-3-3-4-5 que j'ai relevées sont inférieures à 5).
Si il y a un nombre infini de combinaisons, on peut trouver un nombre tel qu'il apparait autant de fois que l'on souhaite dans la décomposition (En effet, si tout les entiers ne pouvaient pas apparaitre autant de fois que l'on veut, on aurait un nombre fini de combinaison.) En poursuivant le raisonnement, on peut trouver autant de +n et autant de -m que l'on souhaite. Les quantités des n et de m ne pourront pas dépasser leur ppcm (oui oui, j'ai confondu avec Bézout ) On aura donc un nombre fini de combinaisons...

Ça ne m'a pas l'air super clair, si tu veux des explications supplémentaires, demande...

En effet, on ne peut pas donner la liste complète, mais mon post montre deux choses: d'une part, on peut réduire toutes ces additions à des additions dites "premières" (Un peu comme les nombres premiers, on peut décomposer chaque nombre en produit de facteurs premier, là aussi, on peut décomposer une somme en somme de sommes premières (ça fait beacoup de sommes tout ça ), certes pas de manière unique, mais le problème peut se résoudre à seulement chercher ces sommes.
D'autre part, j'ai démontré que si l'on ne considère que les n premiers entiers, il n'existe qu'un nombre fini de sommes premières, on peut donc les lister...
Après, il ne faut pas s'attendre à une formule de derrière les fagots pour trouver ces sommes directement, étant donné qu'il n'y a à priori aucun lien mathématique logique entre un chiffre et le nombre de lettres le composant. C'est pour ça que l'on ne peut qu'au mieux chercher un algorithme le plus efficace possible. (malheureusement, en ce moment, je n'ai pas beaucoup de temps pour coder...)

nodgim tu autorises les soustractions, ça ne nous simplifie pas la tâche tout ça...

Ah, à partir de 58, j'ai mal lu, désolé...

On peut lister les nombres qu'on ne peut pas écrire avec cette contrainte :
0 à 5 et 7.