Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-04-2020 19:07:32

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nomnre max de diviseurs

Bonjour @ tous,

Vu ailleurs cette question un peu loufoque : Quel est le nombre plus petit que 2^2020 qui comporte le plus de diviseurs possibles ?

J'ai une réponse qui ne m'a pas pris trop de temps, sans évidemment pouvoir prouver que c'est le max.

Quel nombre proposez-vous ?

  • |
  • Répondre

#0 Pub

 #2 - 15-04-2020 19:14:18

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Nombre max de divsieurs

Allez , je tente [latex]2^{2019}[/latex] lol

Vasimolo

 #3 - 15-04-2020 23:33:15

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

Nombre max de idviseurs

Probablement 3^N avec N=ent[2020.ln(2)/ln(3)] donc 3^1274
(en fait au départ j'hésitai avec 2^1010 mais 1010 < 1274)

 #4 - 16-04-2020 00:12:03

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

nomnre max de diviseurs

Je ne comprends pas, si les facteurs ne sont pas distincts, c'est 2^2018*3, si les facteurs sont distincts, il suffit de prendre les plus petits nombres premiers de manière gloutonne sans dépasser 2^2020. Une manière pratique de le calculer sans overflow est d'additionner les logarithmes en base 2 sans dépasser 2020. (sauf erreur, on obtient 232)

Si on ne parle pas de facteurs premiers mais du nombre de diviseurs, la question est mal posée...

 #5 - 16-04-2020 08:40:39

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nombee max de diviseurs

Je viens de remplacer le mot "facteur" par "diviseur". Pardon aux lecteurs pour qui auraient pu mal interpréter.

@ Caduk: j'ai lu ton message précisément après ce que je viens d'écrire.

 #6 - 17-04-2020 08:22:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombre max de divsieurs

@ Caduk: donc 2^232 pour toi ?

Je crois qu'il y a une petite erreur dans le décompte, mais de toute façon, même si ce n'est pas très loin, ce n'est pas le max.

 #7 - 17-04-2020 12:29:01

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

nombre max dz diviseurs

Effectivement, je me suis trompé, on obtient 230 pour le nombre de facteurs premiers distincts.

Pour le nombre de diviseurs :

Si un nombre s'écrit [latex]\displaystyle n=\prod_{p_i\text{ premiers}}p_i^{\alpha_i}[/latex], le nombre de diviseurs est [latex]\displaystyle\prod_i (\alpha_i + 1)[/latex]
Si on veut que [latex]n < 2^{2020}[/latex], alors en prenant le log:
[TeX]\displaystyle \sum\alpha_i log_2(p_i) < 2020[/TeX]
Récapitulons l'exercice :
l'objectif est de résoudre le problème d'optimisation suivant :
[TeX]\displaystyle Max n=\prod_{p_i\text{ premiers}}p_i^{\alpha_i}[/TeX]

[TeX]\displaystyle \sum\alpha_i log_2(p_i) < 2020[/TeX]
[TeX]\alpha_i \geq 0 \;\ \forall i[/TeX]
[TeX]\alpha_i \in \mathbb{N}[/TeX]
Soit [latex]P[/latex] la relaxation de ce problème. (on enlève la condition que les variables soient entières, ce qui nous ramène à en chercher des approximations)
Soit [latex]P_N[/latex] ce même problème, mais uniquement sur les [latex]N[/latex] premiers nombres premiers.

On sait que pour la solution optimale de [latex]P[/latex], il existe un rang à partir duquel les [latex]\alpha_i[/latex] seront nul. En effet, si un nombre premier est supérieur à [latex]2^2020[/latex], alors sont exposant sera forcément nul.
Soit [latex]N[/latex] le coefficient du plus grand nombre premier tel que [latex]\alpha_N > 0[/latex]
Il est facile de voir que la solution de [latex]P[/latex] est la même que la solution de [latex]P_N[/latex].

Enlevons les contrainte de positivité sur le problème [latex]P_N[/latex].
Maintenant, un peu de magie : Posons [latex]\beta_i = log_2(p_i)(\alpha_i +1)[/latex]. On a alors la relation [latex]\displaystyle \sum_i \beta_i = 2020 + \sum_i log_2(p_i)[/latex]
De plus, maximiser le nombre de diviseurs est équivalent à maximiser le produit des [latex]\beta_i[/latex].

Il est bien connu que maximiser un produit connaissant la somme de ses termes revient à prendre tout les termes égaux. (car s'il existe deux termes non égaux, on peut améliorer le produit en les remplaçants par leur moyenne, donc aucune solution avec deux termes différents ne peut être optimale)

On a donc [latex]\beta_i = \dfrac{2020 + \sum_k log_2(p_k)}{N}[/latex]. Ce qui nous donne [latex]\alpha_i = \dfrac{2020 + \sum_k log_2(p_k)}{N log_2(p_i)}-1[/latex]

Cependant, une contrainte n'a pas été prise en compte : on aimerait bien que les exposants trouvés soient positifs. Ici, si on fait tendre le nombre de nombres premiers vers l'infini, on trouve que les exposants pour les petits nombres premiers tendent vers l'infini, tandis que les derniers  nombres premiers reçoivent un exposant qui tend vers -1.

Il faut donc que l'on prenne maintenant en compte la contrainte de positivité des exposants. Les solutions ou toutes les coefficients sont positifs sont forcément optimales avec les contraintes de positivité. Plus on augmente [latex]N[/latex], plus le max augmente, donc la solution optimale de [latex]P[/latex] sera celle de [latex]P_N[/latex] avec N le plus grand [latex]N[/latex] tel que [latex]\alpha_N[/latex] soit positif.

On veut donc [latex]2020 + \sum_k log_2(p_k) > Nlog_2(p_N)[/latex]
On obtient, sauf erreur, N = 1209, il faudra donc considérer 1209 nombre premiers, jusqu'à 9803 pour avoir la solution optimale avec exposants non entiers. (bien sûr, il n'y aura probablement pas besoin d'aller aussi loin pour les exposants en nombre entiers)

Calculons donc les valeurs approchées de ces exposants. La somme des logarithmes des nombres premiers jusqu'à 9803 vaut s = 14011.46907739904

On a donc :
2 : [latex]\alpha_1 = \dfrac{2020 + s}{1209\times log_2(2)} - 1= 12.271074658293106[/latex]
3 : 7.373115863785284
5 : 4.715540755768706
7 : 3.727252173931144
11 : 2.8362008911512193
13 : 2.586350722924302
...

Si on arrondi tout ces coefficients à l'entier inférieur, on obtient une solution valide en nombres entiers (mais pas optimale):
2 : 12
3 : 7
5 : 4
7 : 3
11 - 19 : 2
23 - 97 : 1

Ce qui nous donne un nombre de diviseurs de 13*8*5*4*3^4*2^17 = 22083010560 (ce qui est déjà pas mal...)
Mais on peut encore faire beaucoup mieux, il suffit de faire la somme pondérée des log pour voir que l'on est très très loin des 2020 (on obtient 169!). C'est en grande partie due au fait qu'après 97, de très nombreux nombres premiers avait une approximation très proche de 1, et ont tous été ramené à 0.
On pourrait arrondir pour faire mieux même si on n'est pas sûr que ça soit admissible (même si ça ne sera pas loin...)
Généralement, les problèmes d'optimisation continue sont facile à résoudre, et leur contrepartie en valeur entière est NP-complet, donc on est sans doute face à un problème difficile.

Je reviens plus tard pour essayer de trouver la meilleure solution possible, mais sans une grosse étude de cas informatique, je pense qu'il est dur de trouver de manière élégante et de prouver la valeur optimale, (En revanche, un solveur n'aura aucun problème à traiter un problème de cette taille)...

Edit :
Bon, je viens quand même d'arrondir pour ne pas me retrouver avec une valeur trop ridicule...

2 : 12
3 : 7
5 : 5
7 : 4
11 - 13 : 3
17 - 37 : 2
41 - 457 : 1

La somme des log fait  702.75 (on est donc toujours très loin des 2020)
Le nombre de diviseurs est donc de 13*8*6*5*4^2*3^6*2^76 = 2.749677598197082e+30, qui donne une bonne inférieure (mais très éloignée)

On peut trouver une borne supérieure en arrondissant à l'excès, on obtient 14*9*6*5*4^4*3^17*2^1121, ce qui donne un très très gros nombre, mais qui surestime beaucoup la valeur optimale.
On peut bidouiller pour rapprocher beaucoup les bornes, je vais essayer de trouver le moyen le moins moche quand j'aurais un peu de temps.

 #8 - 17-04-2020 19:13:52

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Nombbre max de diviseurs

Ce nouveau problème semble bien trop ouvert .

Après on peut avoir construit un résultat plutôt performant smile

Vasimolo

 #9 - 18-04-2020 11:28:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Nombre max de idviseurs

Une proposition non constructive : l'un des entiers inférieurs à [latex]2^{2020}[/latex] dont la décomposition en facteurs premiers contient le maximum de facteurs distincts .

Vasimolo

 #10 - 18-04-2020 12:10:07

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nolbre max de diviseurs

@ Vasimolo : le problème n'est pas aussi ouvert qu'il n'y parait.

Oui, la piste du nombre max de facteurs premiers est évidemment à suivre, ce qu'a fait Caduk pour l'instant, mais il faut faire tout de même attention à l'optimisation: est ce que par exemple plutôt que de s'orienter vers un nombre de diviseurs qui serait une puissance de 2, on ne pourrait pas regarder pour une puissance de 3 ou 5 ? Ou un mixte ?

 #11 - 18-04-2020 17:18:38

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

npmbre max de diviseurs

S’il s’agit des diviseurs (et non des facteurs), je change ma réponse: c’est le produit des 230 premiers nombres premiers dont le nombre de diviseurs est 2^230.

 #12 - 18-04-2020 17:50:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nobre max de diviseurs

@ Francky : voir mon message précédent. Ce n'est pas le présumé max, mais assez proche tout de même.

 #13 - 19-04-2020 12:53:28

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Nomre max de diviseurs

Je crois que c'est un peu de l'arnaque ce problème smile

J'ai essayé à la main de trouver le maximum de facteurs premiers distincts dans un entier inférieur à [latex]2^{2020}[/latex] , sauf erreur il y en a 230 , le dernier étant 1451 . On a alors [latex]2^{230}[/latex] diviseurs . On peut bien sûr corriger à la marge en supprimant les derniers facteurs et en augmentant les exposants des premiers premiers mais tout cela me semble bien plus lourd que "ça ne m'a pas pris trop de temps " .

Vasimolo

 #14 - 19-04-2020 16:13:47

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nombrr max de diviseurs

@ Vasimolo :

1) Tu l'auras compris, l'usage du tableur, au moins, est nécessaire.

2) Je n'ai pas forcément le max, mais pour l'instant le meilleur.

3) Il y a des énigmes qui peuvent prendre la tête plusieurs jours, on en est loin pour celle-ci.

4) Tu peux te définir une méthode d'optimisation et en donner le résultat.

5) C'est tout.

 #15 - 19-04-2020 17:03:29

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

ombre max de diviseurs

Je retente ma chance (en passant par les logarithmes car le rabe est plus facile à identifier): c’est le produit des 230 premiers nombres premiers multiplié par 2^5 (ou 2^6 x 3 x 5 x 7 x ...... x 1451) dont le nombre de diviseurs est 7 x 2^229.

 #16 - 19-04-2020 17:32:37

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

nombre maw de diviseurs

La méthode je l'ai , mais pas les outils de calcul smile

On part du produit des 230 premiers premiers inférieurs à [latex]2^{2020}[/latex]  puis on supprime successivement les plus grands facteurs : 1451 , 1447 , 1439 ... en passant progressivement à un facteur 2 dans la liste : 2 , 3 , 5 , 7 , 11 ... tout en restant inférieur à [latex]2^{2020}[/latex] . On corrige au final à l'aide des premiers facteurs .

Je sais qu'il existe maintenant des logiciels de calcul sur très grands nombres mais ça me dépasse .

Vasimolo

 #17 - 19-04-2020 19:09:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nombre max de diviszurs

@ Francky : ton résultat donne un log de 160,27....

Ce n'est pas mal, mais il y a mieux.

Dans ce problème, les unités de log coûtent cher. 1 unité de plus, et ton nombre est multiplié par 2,718....!

@ Vasimolo : l'idée est là, bien entendu, après c'est une histoire de patience et de goût. Je comprends que ça peut ne pas plaire à tout le monde. C'est juste un exercice de style. En semi-manuel, il faut tout de même ne pas disperser ses efforts.

 #18 - 19-04-2020 23:48:51

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

nombre max fe diviseurs

Bon, retournons à notre étude. J'imposais une contraintes de positivité sur les exposants utilisés, mais sachant qu'il sont entiers, les exposants utilisés seront supérieurs à 1.
Ont peut donc refaire le même raisonnement, avec ces nouvelles contraintes plus précises...
On veut donc trouver le plus petit N tel que [latex]2020 + \sum_k log_2(p_k) > 2\times Nlog_2(p_N)[/latex]
On obtient, sauf erreur, N = 172, il faudra donc considérer 172 nombre premiers, jusqu'à 1021 pour avoir la solution optimale avec exposants non entiers. (il est possible qu'il y ait besoin d'aller plus loin pour l'optimum pour les exposants en nombre entiers)

Calculons donc les valeurs approchées de ces exposants. La somme des logarithmes des nombres premiers jusqu'à 9803 vaut s = 1419.5221362672123
2 : 18.997221722483793
3 : 11.616842173480492
5 : 7.612334622469808
7 : 6.12315409974139
11 : 4.780493424050071
13 : 4.404012291957928

Bon, en prenant les arrondis, on obtient

2 : 19
3 : 12
5 : 8
7 : 6
11 : 5
13 - 19 : 4
23 - 47 : 3
53 - 251 : 2
257 - 1021 : 1

Vérifions que le nombre obtenu ne dépasse pas 2^2020 (en utilisant les log)

La somme des logs donne 1882.7431753691283, ce qui nous rapproche beaucoup de 2020 par rapport au problème d'optimisation précédent, mais on est tout de même très loin de 2020.
Histoire de donner pour une fois une bonne valeur, je vais au moins donner un optimum local.

Au feeling, je propose le schéma suivant :

2 : 32
3 : 18
5 : 11
7 : 7
11 -13: 5
17 - 23 : 4
29 - 59 : 3
61 - 269: 2
271- 1061 : 1

Calculons maintenant le nombre de diviseurs que l'on obtient :
33*19*12*8*6^2*5^3*4^8*3^40*2^121 = 5.737343898026853e+68

Je pense que l'on est encore à plusieurs ordres de grandeur, mais plus si loin. Il faudrait encore chercher localement, mais c'est assez rébarbatif... Peut être formuler un problème d'optimisation en terme d'intervalles...

 #19 - 20-04-2020 07:56:47

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombre max de diivseurs

Salut Caduk,

Sauf erreur, le nombre de diviseurs de ta solution a pour log 158,32. Ce qui est plus petit que le brut des 230 premiers nombres premiers : 159,....

il y a quelque chose qui ne va pas dans la démarche.

 #20 - 20-04-2020 16:17:15

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 3446
Lieu: 94110

Nombre max de ddiviseurs

Tout d'abord, j'ai calculé la limite approximative : 2^2020 = 1,20390 * 10^608

Ma première idée avait été de faire le produit des nombres premiers.
Celui des 233 premiers (jusqu'à 1471) donne alors 2^233, soit 1.380349 * 10^70 diviseurs pour un résultat inférieur (je crois ? neutral ) à la limite imposée.

J'ai compris que c'était la proposition de Caduk et qu'on pouvait faire mieux...

Ma deuxième idée a été de me contenter des 40 premiers nombres premiers et d’élever chacun d'eux à une puissance i telle que, en moyenne, chaque résultat fasse à peu près racine 40ème de la limite soit 2^50.5, ce qui conduit à une suite 2^51, 3^32, ... jusqu'à 173^7.
Hélas, je n'ai obtenu alors que 1.00979 * 10^41 diviseurs, soit beaucoup moins qu'à mon premier essai sad ...

Troisième idée : je me suis entêté et j'ai poussé jusqu'aux 101 premiers², avec une suite de 2^20 jusqu'à 547^2.
Mais l'amélioration reste maigre : je passe seulement à 4.90016 * 10^58 diviseurs sad ...

Changement de tactique : plutôt que de commencer par le début, je pense que la meilleur solution consiste à commencer par la fin : remplacer 1471 par des puissances de 2, 1459 par des puissances de 3, 1453 par des puissances de 5, etc... jusqu'à ce que le nombre de diviseurs obtenu diminue.
Je peux ensuite réappliquer la même stratégie sur les nombres premiers suivants en les remplaçant par des puissances de 2, puis de 3, ... et ainsi de suite jusqu'à ce le remplacement par une puissance de 2 n'apporte plus de progrès au nombre de diviseurs.

Voilà pour la stratégie. En ce qui concerne la pratique...
J'ai déjà passé un bon paquet d'heures sur ce problème, par ailleurs passionnant et enrichissant. Merci smile .

PS : Il est fort plausible que je me soit planté dans les calculs... Avec des nombres dépassant les capacités de calcul offertes par mon tableur, ce n'est nullement exclu. Je m'attache surtout à l'idée finale.

(entre parenthèse, je pense que le problème aurait été aussi intéressant en se bornant à une limite un peu plus raisonnable, par exemple 2^1000 roll
)

 #21 - 20-04-2020 16:39:25

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Nombre max de idviseurs

Salut,
Je trouve un log du nombre de diviseurs un peu plus grand que 163.7755 smile

2^13 * 3^9 * 5^6 * 7^4 * 11^3 * 13^3 * 17^3 * 19^2 * 23^2 * 29^2 * 31^2 * 37^2 * 41^2 * 43^2 * 47^2 * 53^2 * 59^2 * 61^2 * 67^2 * 71 * 73 * 79 * 83 * 89 * 97 * 101  (...)   * 1327 * 1361

133906064952873793600609593406329951800649926335126845286670494649548800 diviseurs
pour le nombre :
120297987559754384432904172296775097816177153142962673524061271704223416
053733402125139721940604703903069294485981143656852785279901622748332306
912383419066360741075003362097299288228213657873769835958882964689119053
796295985321203232255271189822347896208658606226676652727663229010030463
746058725159269782939272608736180418721019834152101670891035951638910231
636646877625858765438979084935550703518488087047967242429919925459583188
892308061624101948095076832802391414191972244145565295960401872575103972
262054907429376226514982675262352911358303089727255369340684146654257969
859659323344820312735267968000000

 #22 - 21-04-2020 09:52:20

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombre max de iviseurs

Gwen: t'es le meilleur !

On va l'appeler le nombre G, celui-là.

On remarque G = 0,99923...2^2020

Avec le log de son nombre de diviseurs à 163,77551...il dépasse de 0,25 pts le mien.

Tu as fait tourner une machine ? Combien de temps de travail ?

 #23 - 21-04-2020 09:54:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

nombre max de diviseues

@ Jackv : joli effort ! c'est bien de cette façon qu'on peut optimiser.

Sinon, tu ne peux aller au delà de 230 diviseurs premiers.

 #24 - 21-04-2020 11:27:17

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Nmbre max de diviseurs

Les nombres hautement composés ont peu de puissances supérieures à 2 (1 à 8 maximum jusqu'à de très grand nombres)
Donc un petit programme m'a fait une liste d'exclusions (pas parfaite, mais valable pour de très grand nombres) en comparant les nombres de diviseurs pour le plus petit nombre possible, ca a pris 2mn car on trouve cette liste sur le net lol
Il y a une centaine de possibilités:
[10,7,5,4,3,3,2,2]
[10,8,5,4,3,3,2,2]
[11,7,5,3,3,3,2,2]
(...)
[15,9,5,4,3,3,3,3,2]
[16,8,5,4,3,3,2,2]
[16,8,5,4,3,3,3,2]
[16,9,5,4,3,3,3,2]

Un autre programme me teste ces 100 possibilités en rajoutant entre 1 et 30 "2" en plus et autant de 1 que possible pour arriver à 2^2020 à partir de la liste des 231 premiers nombres premiers.
Il sort en moins de 30s le résultat des 3000 tests.

Il faut 1/4 d'heure pour tester toutes les possibilités avec de la marge (entre 9 et 18 pour la première puissance, entre 6 et 12 pour la seconde... avec un 3 de plus éventuellement )  Le résultat est le même.

 #25 - 21-04-2020 11:44:00

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombre mmax de diviseurs

OK vu Gwen.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 88 pommes et que vous en prenez 44, combien vous en avez ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete