Misez p'tit Optimisez n°82 : maximisez produit des termes

[C.Ret]

Comme il a plut toute la matinée et qu'en ce début d'après-midi, la météo ne semble pas vouloir faire d'autre effort que de laisser toute l'eau du ciel tomber sur la ville, je suis restée au chaud, bien installée sur la table du salon avec quelques amis.

Afin de profiter au mieux de ce congé de fin de semaine, nous nous sommes mis à décomposer quelques nombres en somme de termes. très vite nous nous sommes rendu compte que pour chaque nombre, il existait un nombre important de décompositions possibles et plusieurs façons de présenter chaque décomposition.

Je ne sais plus si c'était Hewlett ou Packard qui l'avait fait remarquer ou notre nouvel ami texan des Hauts de Seine, dernier arrivé dans notre Club, mais l'idée est venue de faire le produit de ces termes. En effet, tout comme l'addition, la multiplication est commutative, et en conséquence, peu importe l'ordre des termes, nous obtenons le même résultat en effectuant leur produit.

CodeCogsEqn.png (4.8 Kio) Vu 5229 fois

Très vite, notre petite réunion amicale devient, comme nous en avons l'habitude, un petit défit où il s'agit , en un minimum d'effort et d'une façon aussi élégante que possible, de trouver la décomposition en somme qui conduit au produit maximum.

Notre discussion qui avait débutée par les considérations philosophiques sur la multiplicité et la façon de présenter les décompositions additives, pris alors un tournant et devint plus vive; surtout aux propos de certains nombres aux propriétés spécifiques.

Je ne suis pas, et de loin, la plus rapide. Mais je fût la première à proposer une décomposition simple du nombre premier 11. Comme 5+6=11, j'indiquais que 30 ( 5*6=30 ) était une proposition décente.

Mais très vite, mon confrère nippon trouva pour ce même nombre premier une décomposition bien plus efficace qu'il afficha sur un large sourire de quatre lignes. J'ai l'habitude d'être la plus lente, mais je croyait être une experte dans ce type de problème. je fut donc très vexée de constater la validité de sa proposition 2+3+6=11 et donc le produit 2*3*6=36 est correct et invalide ma proposition. Sur le coup, j'en est fait encore un peu plus d'huile noire.

C'est alors que Hewlett et Packard se sont associés pour nous imprimer une solution plus efficace encore. Je n'ai pas tout bien compris dans leur démonstration, comme à leur accoutume, ces deux là nous font des raisonnements alambiqués où tout est inutilement inversé et empilé. N'empêche que force est de constater brutalement qu'en décomposant 11 de cette façon 2.6+2.7+2.8+2.9, le produit s'élève alors à l'altitude inattendue de 2.6*2.7*2.8*2.9 soit 57.0024

Diantre !

Nous croyons avoir trouvé là le produit maximal, mais il en était rien, notre ami Commodore a fait vrombir ses floppy disks et crépité ces aiguilles pour afficher la décomposition fabuleuse de 11 en 2.70+2.72+2.78+2.80 ce qui lui permis de proposer le produit maximal tout aussi fabuleux de 57.1656966

Pauvre Commodore, il n'a jamais su calculer avec précision, en refaisant ses calculs avec le soin, le tranchant et l'exactitude qui me caractérisent (seule la rapidité me manque) je trouve un produit égal en réalité à 57.16569600 cela fait plus de 30 ans que je le connais, il a toujours était un mauvais calculeux, mais c'est un brave type résistant, enchanteur et coloré. Mes amis doivent partager ma compassion, nous n'avons rien objecté.

Mais est-ce là le produit maximal de la décomposition additive de 11 ?

J'aimerai en être sûre, n'avez vous pas autour de vous des amis qui pourrez nous renseigner.

Pourriez vous leur demander de vérifier et éventuellement , si notre petit Club n'a pas su le faire, nous proposer un produit plus grand encore.


Nous avons encore échangé en nous amusant à maximiser avec d'autres nombres et d'autres décompositions. Nous nous sommes rendu compte que le produit maximal dépend de la précision des termes de la décomposition. Si nous nous limitons à des termes entier, les produits maximums ne sont pas aussi importants qu'en utilisant des termes à une, deux, trois ou quatre décimales.



C'est alors que notre amie texane a affirmé avoir une méthode pour maximiser ce produit. Elle n'aurait besoin que du nombre et de la précision des termes de la somme (0 1 2 3 ou 4 décimales).
Ne le répétez pas, mais je crois que sa méthode est bancale, elle ne fonctionne pas pour tous les nombres !

A se sujet, si vous avez des amis qui connaissent une méthode, qu'ils n'hésitent pas à nous l'envoyer.

Mais quelque chose de simple et de rapide !
Mais surtout quelque chose d'élégant.

[Gilles59]

Excellent ;D

J'ai noté une petite coquille qui affirme que "2+3+6=30", et même si la précision du Commodore est faible je doute qu'il fasse une telle erreur...

Allez, Hewlett va étudier cela pendant que je vais méditer ce sujet en écoutant une de mes chansons préférées et de circonstance ...
La chanson de la pluie

[C.Ret]

Merci Gilles, surtout que c'était une somme calculée par un SHARP.

Je mets ici les résultats au fur et à mesure de leur annonce :

Code : Tout sélectionner

Nombre Liste des termes                        Nb termes  Produit
11  { 2      3      3      3       }              (k=4)   54.                          Gilles59
11  { 2.7    2.7    2.8    2.8     }              (k=4)   57.1536                   
11  { 2.75   2.75   2.75   2.75    }              (k=4)   57.19140625                  gege

17  { 2      3      3      3      3      3      } (k=6)   486.                         zpalm
17  { 2.8    2.8    2.8    2.8    2.9    2.9    } (k=6)   516.925696
17  { 2.83   2.83   2.83   2.83   2.84   2.84   } (k=6)   517.347580316
17  { 2.833  2.833  2.833  2.833  2.834  2.834  } (k=6)   517.351830326                     
17  { 2.8333 2.8333 2.8333 2.8333 2.8334 2.8334 } (k=6)   517.351872855690955507577476 c.ret

Code : Tout sélectionner

42  { 3 3 3 3 3 3 3 3 3 3 3 3 3 3 }               (k=14)  4782969.
42  { 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7
      2.7 2.7 2.7 2.7 2.7 }                       (k=15)  5097655.355238390956032      c.ret   

54  { 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 }       (k=18)  387420489.
54  { 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7
      2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 2.7 }   (k=20) 423911582.75216203514294433201 zpalm gege

[gege]

Bonjour,
Pour 11 je trouve un maximum de 57.19 environ.
Un programme devrait se faire sans trop de soucis dès que ma Prime redémarre...
Intéressant !
G.E.

EDIT : Bon, finalement sur ma Prime de backup ça donne :

Code : Tout sélectionner

EXPORT sp(m)
BEGIN
LOCAL n;
ROUND(m,0)->n;
PRINT(n);
PRINT(m/n);
PRINT((m/n)^n);
END;

Et sp(11) affiche :
4
2.75
57.19140625
C'est à dire :
11=2.75+2.75+2.75+2.75 (4 termes)
Et 2.75*2.75*2.75*2.75=57.19140625

[C.Ret]

Bien, bon début. Espérons que l'HP Prime amirale sera prête en temps et heures pour nous donner d'aussi bon résultat avec les termes entiers et décimaux différents.

[Gilles59]

EDIT : Bon, finalement sur ma Prime de backup ça donne :

Code : Tout sélectionner

EXPORT sp(m)
BEGIN
LOCAL n;
ROUND(m,0)->n;
PRINT(n);
PRINT(m/n);
PRINT((m/n)^n);
END;

Je n'ai pas ma Prime sous la main... Que fait ROUND dans ton programme?

[Gilles59]

Il me semble que le produit est maximisé quand les éléments sont les plus proches possibles de 2.75
Pour une décimale et 4 termes je propose donc avec ma HP50g :

2.7*2.7*2.8*2.8 -> 57.1536

Pourquoi 4 termes? l'expérience montre que cela semble être le meilleur choix.

Pour 3 décimales : 2,750
et pour 4 décimales : 2,7500 -> 57.19140625

Pour les entiers je propose, avec la même logique :

3*3*3*2 -> 54

[zpalm]

En tapotant sur ma Prime, voici ce que j'ai obtenu:

Code : Tout sélectionner

EXPORT MPO82(n,p)
BEGIN
 LOCAL d:=1,l,m1,m2,k;
 WHILE (n/d)^d≤(n/(d+1))^(d+1) DO d:=d+1; END;
 m1:=ROUND(n/d,p);
 m2:=n-m1*d;
 k:=SIGN(m2)*ALOG(−p);
 l:=MAKELIST(m1+IFTE(m2,k+0*(m2:=(m2-k)),0),I,1,d);
 PRINT("\n"+ΣLIST(l));
 PRINT(l);
 PRINT(ΠLIST(l(0):=1));
END;

Ce qui donne pour 11 et pour 17:

[gege]

Bonjour,
Oups erreur c'est ROUND(m/fe), où e=exp(1).
Ça arrondit à l'entier le plus proche car n (le nombre d'éléments) est forcément entier.
Pour avoir un nombre fixé de décimales, ça me semble plus compliqué...
G.E.

[zpalm]

Merci C.Ret pour ce MPO et son magnifique énoncé!

Après une courte mais bonne nuit de sommeil, voici quelques explications sur les 5 lignes de mon programme. Le but est de construire une liste de d éléments de précision p, les plus proches de n/d possible et tels que leur somme soit égale à n, leur produit étant alors maximal (ce qu’il faudrait quand même démontrer…)

Code : Tout sélectionner

WHILE (n/d)^d≤(n/(d+1))^(d+1) DO d:=d+1; END;

On cherche le nombre optimal d’éléments d qui maximise le produit lorsque tous les éléments sont égaux.
Pour n=11 on a d=4. Pour n=17 on a d=6.

Code : Tout sélectionner

m1:=ROUND(n/d,p);

m1 est la valeur de n/d arrondie à la précision demandée
Pour n=11 et p=1 on a m1=2.8

Code : Tout sélectionner

m2:=n-m1*d;

m2 est l’écart entre le nombre n et la somme de d éléments m1.
Pour n=11 et p=1 on a m2=-0.2

Code : Tout sélectionner

k:=SIGN(m2)*ALOG(−p);

k est la valeur d’ajustement que l’on va utiliser sur certains éléments de la liste pour ramener la somme à n :
Pour n=11 et p=1 on a k=-0.1

Code : Tout sélectionner

l:=MAKELIST(m1+IFTE(m2,k+0*(m2:=(m2-k)),0),I,1,d);

l est une liste de d éléments de valeur m1, et on ajoute k aux premiers éléments de la liste jusqu’à ce l’on ait compensé l’écart m2.
Pour n=11 et p=1 on a d=4, m1=2.8, m2=-0.2, k=-0.1 ce qui donne l={2.7,2.7,2.8,2.8}, on a ajouté -0.1 aux deux premiers éléments.

EDIT: une manière plus simple de créer la liste l:

Code : Tout sélectionner

l:=MAKELIST(m1+k*(ABS(I*k)≤ABS(m2)),I,1,d);

[C.Ret]

Ah! Je vois avec plaisir que le choses prennent forme.

Je suis surpris, je m'attendais à une stratégie différente pour résoudre le cas des termes entiers et le cas des termes décimaux.
Mais c'était sans compter sur l'excellence des gens qui fréquente ce forum !!

[...]Pourquoi 4 termes? l'expérience montre que cela semble être le meilleur choix.[...]

Je ne veux pas encore donner trop d'indices afin de laisser à d'autres le plaisir de chercher et trouver.

Mais pour mettre sur la voie, le choix du nombre de termes peut être lié à ceci:

mpo82plot1lab.png (10.22 Kio) Vu 5229 fois

Merci zpalm pour les explications, encore une fois nous avons utilisé la même approche. Mais mon code est fort diffèrent.
Initialement, il ne construisait pas la liste des termes.
Mais c'est une bonne idée, j'ai donc modifié mon code initial afin de disposer moi aussi de la liste des termes.

Comme à mon habitude, j'utilise les variables globales (y compris pour la liste des termes) afin de me retrouver dans une utilisation proche de mes autres calculettes:

mpo84hpprime.png (23.4 Kio) Vu 5229 fois

Deux petites remarques:
1) - j'utilise TRUNCATE au lieu de ROUND afin de ne pas avoir à traiter le signe de la correction, l'écart étant ainsi toujours positif !
2) - le nombre de terme est calculé directement à partir des informations données ci-dessus à Gilles59. Une fois que l'on a compris à quoi correspond la courbe en cloche, il est facile de trouver sa dérivée et de trouver en quelle(s) valeur(s) celle-ci s'annule donnant la position de son maximum.

[zpalm]

@C.Ret, il semble y avoir une différence de calcul entre nos deux programmes.

Pour N=54 et D=3 ton programme retourne une liste de 19 termes :
{2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.842,2.843,2.843}
dont le produit vaut 416066711.608

Mon programme retourne une liste de 20 termes :
{2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7,2.7}
dont le produit vaut 423911582.754

Voici la dernière version de mon programme qui retourne la liste des termes dans L1:

Code : Tout sélectionner

EXPORT MPO82(n,p)
BEGIN
 LOCAL d:=1,m1,m2,k;
 WHILE (n/d)^d≤(n/(d+1))^(d+1) DO d:=d+1; END;
 m1:=ROUND(n/d,p);
 m2:=n-m1*d;
 k:=SIGN(m2)*ALOG(−p);
 L1:=MAKELIST(m1+k*(ABS(I*k)≤ABS(m2)),I,1,d);
 ΠLIST(CONCAT(L1,1));
END;

[C.Ret]

Très interessant, il y a donc un bug dans mon code.
Je pense que 54 n'est pas la seule valeur où mon code plante !

Je suis inquiet !
Je crois que je suis passé à coté de quelque chose d'important !

Que donne ta version pour une décomposition additive de 54 en termes entiers ?

54 = 3 * 18 donc le produit maximal devrait être 3^18

[gege]

Bonjour
Je trouve :
54 = 20 * 2.7
Et
2.7^20 = 423911582.752
G.E.

[C.Ret]

Oui zpalm aussi et pour les termes décimaux, c'est je crois que 423911582.75216203514294433201 (20 décimales) est la bonne solution, que malheureusement mon code ne trouve pas !
Je susi en train de le modifier, mais je me rends compte qu'il y a d'autres valeurs où il ne fonctionne pas comme je le souhaiterai.

En particuier avec 54 et des termes entiers.