D'après mes calculs:
1) C(2025) = 22.
2) C(1081) = 25. Et 1081 est le plus petit n tel que C(n) >= 25.
3) Oui, elle est surjective. C(2^p) = 2p pour p > 0 et C(3*2^p) = 2p+3 pour p >= 0.

Voici mon code

 Cliquez pour afficher

from math import log2


def compute(n_max):
    c = [n for n in range(n_max + 1)]
    for n in range(2, n_max + 1):
        if c[n] == n:
            c[n] = c[n-1] + 1
        for m in range(2, n_max//n + 1):
            c[m*n] = min(c[m*n], c[m] + c[n])

    return c


def main():
    c = compute(2025)

    print(c[2025])
    print([c[2**p] for p in range(int(log2(2025))+1)])
    print([c[3*2**p] for p in range(int(log2(2025/3))+1)])

    best = 0
    for n, v in enumerate(c):
        if v > best:
            best = v
            print(v, n)


main()

Bonjour,
1)C(2025)=45*45 =9*5*9*5 =(1+1+1+1+1+1)x(1+1+1+1+1) deux fois soit 22
2)1081=23x47= ((1111)*(11111)+(1+1+1))x((111111)x(11111)+(1+1)) soit 25

Pas de programme mais un bidule

Bonjour à tous les deux 😊
Nous sommes d'accord sur les deux premières questions ( il manque quelques « + » dans les égalités de Dpi ) . Il est clair qu'on peut traiter tous les cas de taille raisonnable avec un programme ou un bidule mais il me semble que ça risque de devenir rapidement chronophage pour de grandes valeurs . Il est facile d'obtenir des bornes supérieures pour C par exemple C(ab)<=C(a)+C(b)  mais il est beaucoup plus délicat de pointer l'autre borne . Par exemple on a clairement C(2^p)<= 2p mais pourquoi « = » ?
Imod

Même si ce n'est pas le même , ce problème m'en a rappelé un autre bien plus simple :

Pour un entier n donné , on considère toutes les sommes d'entiers naturels égales à n et on cherche le maximum que l'on peut atteindre en choisissant une de ces sommes et en multipliant tous les entiers qui la compose .

Imod

Pour le moment mon bidule fonctionne jusqu'à 90000 mais sans trop
d'itérations je peux aller à 1000000.

Pour info 1081 peut s'écrire avec 24 fois 1

Oui , C n'est pas croissante
Imod

Une remarque , en proposant à l'OEIS les premières valeurs fournies par vos machines , vous devriez obtenir quelques pistes .
Imod

Il se trouve que mon bidule est incorrect. Je ne couvre pas les cas x+y avec x et y > 1.

Après correction:
1) C(2025) = 22 . Ça reste correct.
2) 1438 est le plus petit nombre dont la complexité est 25

1081 n'a qu'une complexité de 21:

 Cliquez pour afficher

1081
1+1080 
1+2*2*2*135
1+2*2*2*3*3*3*5
1+2*2*2*3*3*3*(1+2*2)
1+(1+1)*(1+1)*(1+1)*(1+1+1)*(1+1+1)*(1+1+1)*(1+(1+1)*(1+1))

 Cliquez pour afficher

from math import log2


def compute(n_max):
    n2all = {1: {1}}
    all2n = {1:1}

    for n in range(2, n_max+1):
        new_z = set()
        for i in range(1, n//2+1):
            for x in n2all[i]:
                for y in n2all[n-i]:
                    for z in (x+y, x*y):
                        if z not in all2n:
                            new_z.add(z)
        n2all[n] = new_z
        all2n |= {z:n for z in new_z}

    return n2all, all2n


def main():
    max_n = 40
    n2all, all2n = compute(max_n)
    # print(n2all, all2n)

    print(all2n.get(2025))
    print(min(n2all.get(25, set()), default=None))

    print(all2n.get(1081))
    assert (2**p in n2all[2*p] for p in range(max_n//2+1))
    assert (2**p*3 in n2all[2*p+3] for p in range((max_n-3)//2+1))


main()

Pour voir si mon bidule est validé par le tien :
C(108756 )-->complexité 35  
MERCI

J'ai bien le même résultat.

C(108756) = C(3³)+C(2²)+C(19)+C(53) = 3*3+2*2+9+13 = 35
C(53) = 1 + C(52) = 1 + C(2²) + C(13) = 1+2*2+8 = 13
C(19) = 1 + C(18) = 1 + C(2) + C(3²) = 1 + 2 + 2*3 = 9
C(13) = 1+ C(12) = 1 + C(2²) + C(3) = 1+2*2+3 = 8

D'accord avec toi pour 1081 = 1080+1
=36 x30+1 --->10+10+1
J'ai constaté que le meilleur produit  des diviseurs est celui qui prend ceux qui sont le pus proche de la racine.
ici 1081=32.88

Pour ma part j'en reste là sauf si nouvelle question pour cet exercice
vraiment beau.

On retrouve certains résultats du problème beaucoup plus simple que j'évoquais au dessus où la meilleure décomposition n'utilise que des 2 et des 3 .

Imod

@LittleFox : Pour calculer C(n) , tu décomposes n en puissances de 2 et 3 multipliées par un complément . Ensuite tu écris le complément p  sous la forme 1+q puis tu décomposes q suivant le même principe . Comment justifies-tu ces égalités ?
Imod

Je calcule les C(n) à l'avance et seulement ensuite je reviens en arrière pour obtenir la décomposition. Et il y a probablement d'autres décompositions.

C'est un peu comme chercher le chemin le plus court dans un labyrinthe en testant d'abord tous les chemins de longueur 1 puis 2 puis 3 et ainsi de suite jusqu'à atteindre la sortie et par après revenir sur ses pas pour décrire l'un des chemin les plus court.

Le égalités tiennent mais c'est un résultat, pas le calcul.

Bonjour,
Je suis parti de l'exemple de départ 6 =(1+1)x (1+1+1)  -->C(6)=5
*7 étant premier ,je rajoute donc 1 soit  C(7)=6
*8 =2x4 -->C(8)=6
*9=3x3-->C(9)=6
*10=2x5--->C(10)=7
*11 premier  je rajoute 1 --->C(11)=8
*12=3x4--->C(12)=7
*Le tableur s'incrémente en  consultant les deux diviseurs centraux  des n suivants .
*diviseurs centraux signifie les diviseurs les plus proches de la racine de n :exemple n=60  10 et 6  plutôt que 15 et 4
C(60)=7+4=12.
Cette méthode par apprentissage successif m'a permis d'arriver à
1 000 000 ce qui est suffisant en nombre de 1

Je crois qu'il ne faut pas se faire trop d'illusions sur la simplicité apparente du problème . Il y a bien sûr une récursivité et la connaissance des premiers C(n) facilite la recherche des suivants mais de là à donner une méthode systématique en partant d'une décomposition en facteurs premiers par exemple , j'ai vraiment des doutes . Je ne suis même pas convaincu par le C(2^n)=2n de LittleFox . Autant le problème inverse est facile à résoudre , c'est-à-dire trouver le plus grand entier que l'on peut écrire avec un nombre de 1 donné , autant celui de la complexité est réellement complexe . De nombreuses conjectures émises par des gens qui ne sont pas des rigolos ont été mises à mal ( Il suffit de regarder la page wiki proposée par LittleFox ) . En bref c'est une belle distraction mais il faut rester raisonnable , on pourrait à la limite proposer des contre-exemples pour des propriétés apparemment indiscutables et pourtant fausses
Imod  

Je peux donner par exemple C(171054)=37
décomposé en C(43)+C(9)+C(12)+C(26)

Il se bâtit toute une théorie sur cette complexité :

*tout entier n a une écriture  en C(n)
*tout premier p a une écriture C(p-1)+1
*C(n) =C(a)+C(b)    si a et b sont les diviseurs les plus proches de n
*C(n²)  = C(n)+2
*on cherche d'autres propriétés par exemple :
plus petit n affichant   C(n)=m   (le cas de 1081 )
*sa réciproque

>Imod
Je confirme qu'en utilisant la méthode décrite on obtient tous les C(n) .
Remarque le nombre de C égaux est parfois de plusieurs centaines.

On peut même corriger  OEIS
exemple:

@Ddpi

J'ai lu tes derniers messages et il y a beaucoup de résultats annoncés comme des vérités mais absolument pas démontrés . Je suis prêt à croire tout ce que tu dis si tu m'apportes une preuve autre qu'un tableau de chiffres qui n'ira jamais jusqu'à l'infini .

Un exemple concret que tu donnes toi même : C(139)=17 .

Faire 139 avec 17 "1" , cela devrait pouvoir s'écrire facilement

Imod

OUI
mais ce n'est pas ce que dit l'OEIS qui dans sa liste attend  167 comme premier 17 "1"
Vérifie toi-même

Ma question ne devait pas être claire : montre moi comment tu écris  139 avec 17 chiffres 1 .
Imod

OK si tu y tiens
en sachant que 139 =6x23+1
(1+1)(1+1+1)((1+1)((1+1)(1+1+1+1+1)+1)+1+1
Pour te confirmer le calcul sur Excel

+(1+1)*(1+1+1)*((1+1)*((1+1)*(1+1+1+1+1)+1)+1)+1 =139
On compte bien  17  fois 1
Donc 139 est le premier 17

En effet ça marche et c'est curieux car l'OEIS est généralement très fiable , bien vu
Imod

Non, l'OEIS est correct.

139 a une complexité de 16

139 = 1+(3*46) = 1+3*(1+3*3*5) = 1+(1+1+1)*(1+(1+1+1)*(1+1+1)*(1+1+1+1+1))

D'ailleurs si on lit un petit peu l'oeis, l'hypothèse C(p) = C(p-1)+1 qui était supposée vraie a eu son plus petit contre exemple 353942783 = 2*3 + (1 + 2^2*3^2)*(2 + 3^4(1 + 2*3^10)) trouvé en 2012.
D'autres ont suivis:

Attention, si C(n*m) <= C(n) + C(m), l'égalité elle n'est pas garantie. Même si n et m sont les diviseurs entourant la racine de m*n. Un contre-exemple: C(1*5) = 5 < C(1) + C(5) = 1 + 5. Un autre: C(23*23) = 20 < C(23) + C(23) = 11 + 11 =  22.

C(2^n*3^m) = n*C(2)+m*C(3) a été démontré par calcul pour 2^n*3^m < 10^12 et m+n > 0 mais ce n'est pas sûr que ça tienne toujours .

En fait, comme le disait Imod: "Il est facile d'obtenir des bornes supérieures pour C par exemple C(ab)<=C(a)+C(b)  mais il est beaucoup plus délicat de pointer l'autre borne ."

Lire "C(p) = C(p-1) pour p premier"

>Littlefox

Je viens de vérifier et c'est vrai
Cela remet en cause une partie de ma théorie

Pour le calcul de C(139) j'avais tout bêtement oublié de vérifier si on ne pouvait pas faire mieux

De toute façon il n'y a pas de honte à partir un peu en vrille sur cet exercice tordu qui a chatouillé des mathématiciens très compétents

Imod