Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Complexité d'un entier

Posté par
Imod
04-07-25 à 19:04

Bonjour à tous

Je vous propose une petite détente ouverte à laquelle je n'ai pas encore vraiment réfléchi mais qui peut être intéressante .

On construit des entiers en utilisant uniquement des nombres 1, des + , des X et des parenthèses . La complexité d'un entier n notée C(n) est le nombre minimal de 1 nécessaire pour construire n .
Par exemple C(6) = 5 car 6 = ( 1 + 1 ) X ( 1 + 1 + 1 ) et on ne peut pas obtenir « 6 » avec moins de cinq « 1 » .

Trois questions possibles :

1°) Que vaut C(2025) ?
2°) Quel est le plus petit n vérifiant C(n) = 25 ?
3°) La fonction C est-elle surjective sur N* ?

Il y en a sûrement plein d'autres mais pour moi la complexité du problème reste entière .

Amusez-vous bien

Imod

PS : Il n'est pas utile de Blanker sauf si on propose des listes d'un kilomètre de long

Posté par
LittleFox
re : Complexité d'un entier 04-07-25 à 20:58


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

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 07:53

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

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 09:23

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

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 10:05

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

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 10:46

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

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 10:52

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

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 11:06

Oui , C n'est pas croissante
Imod

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 11:19

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

Posté par
LittleFox
re : Complexité d'un entier 05-07-25 à 15:09

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


L'oeis nous dit que c'est la complexité de Mahler & Popken (1953).
L'article wikipedia répond à la surjection :
3) 2^{x}3^{(k-2x)/3}{\text{ where }}x=-k{\bmod {3}} est le nombre maximum de complexité k. Il y a donc au moins ce nombre pour chaque complexité.

Voici mon code basé sur celui de Tim Peters référencé dans l'oeis:
 Cliquez pour afficher

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 15:35

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

Posté par
LittleFox
re : Complexité d'un entier 05-07-25 à 16:10

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

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 16:19

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

Posté par
dpi
re : Complexité d'un entier 05-07-25 à 16:48

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

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 17:11

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

Posté par
Imod
re : Complexité d'un entier 05-07-25 à 17:31

@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

Posté par
LittleFox
re : Complexité d'un entier 06-07-25 à 03:25

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.

Posté par
dpi
re : Complexité d'un entier 06-07-25 à 08:44

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

Posté par
Imod
re : Complexité d'un entier 06-07-25 à 11:20

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  

Posté par
dpi
re : Complexité d'un entier 06-07-25 à 15:48

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

Posté par
dpi
re : Complexité d'un entier 07-07-25 à 08:59

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

Posté par
dpi
re : Complexité d'un entier 08-07-25 à 14:17

>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.

Posté par
dpi
re : Complexité d'un entier 08-07-25 à 15:32

On peut même corriger  OEIS
exemple:

Citation :
1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167,....

qui veut dire  que C(167) est le plus petit17
Alors que j'ai 139
En effet C(138)= C(23)+C(6) =11+5=16
Donc 139=16+1

Posté par
Imod
re : Complexité d'un entier 08-07-25 à 18:29

@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

Posté par
dpi
re : Complexité d'un entier 09-07-25 à 08:12

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

Posté par
Imod
re : Complexité d'un entier 09-07-25 à 10:16

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

Posté par
dpi
re : Complexité d'un entier 09-07-25 à 16:55

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

Posté par
Imod
re : Complexité d'un entier 09-07-25 à 17:31

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

Posté par
LittleFox
re : Complexité d'un entier 09-07-25 à 20:28

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 ."

Posté par
LittleFox
re : Complexité d'un entier 09-07-25 à 20:31

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

Posté par
dpi
re : Complexité d'un entier 10-07-25 à 08:08

>Littlefox

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

Citation :
*C(n) =C(a)+C(b)    si a et b sont les diviseurs les plus proches de n

(dans la citation a disparu ?)
qui pourtant était confirmée ...
En effet 3x46  est plus court que 6x23.
Donc il faut que je reteste mon bidule.

Posté par
Imod
re : Complexité d'un entier 10-07-25 à 10:03

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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !