Divisibilité (exo spé assez intéressant)

[invite85d09bae]

Hello tout le monde!

En cette nouvelle année 2008 (je sais chuis un peu en retard), je vous propose un exercice que j'ai trouvé assez intéressant :

Quel est, parmi les entiers naturels de 1 à 1999, celui qui admet le plus de diviseurs? Quel est ce nombre maximum de diviseurs?

Bon j'y ai réfléchi, la réponse ne nous est pas donnée dans le livre où je l'ai trouvé, mais je pense avoir trouvé la solution (j'en suis même sûr) et je l'ai résolu d'une manière plus ou moins mathématique, sans trop de rigueur mais avec beaucoup d'intuition Je sais pas si je vous mets ma réponse à moi pour que vous puissiez discuter et voir si j'ai bon ou pas, ou si vous préférez faire l'exo vous même sans regarder ma solution au problème. Je vais quand même mettre ce que j'ai trouvé :

Tout d'abord, quelques connaissances préliminaires à avoir : 1)un entier naturel quelconque n se décompose d'une manière unique en facteurs premiers : n = p₀^a0 * p₁^a1 *.....* p_k^ak, avec p nombre premier et a entier naturel pouvant être nul.

2) De cette décomposition on peut en déduire le nombre de diviseurs de n : il vaut (a1 +1)(a2+1)(a3+1)....(ak+1) , autrement dit produit des exposants augmentéS de 1.

Ensuite, quelques réflexions pour cerner le problème et savoir exactement ce qu'on veut : on a D en FP de 2000= 2⁴ * 5³, donc tous les nombres qu'on va étudier devront être inférieurs à ce produit.

De plus, on veut celui qui a le plus de diviseurs, autrement dit, il faut que (a1 +1)(a2+1)(a3+1)....(ak+1) soit le plus grand possible, donc on recherche un nombre qui se décompose en beaucoup de p, avec les puissances à chaque fois le plus grand possible, par exemple : 2² * 3³ * 5^quelquechose ...., on se rend compte alors qu'on peut s'intéresser uniquement aux décompositions en 2, 3 5 et 7 car ensuite on monte très vite au dessus de 2000 et encore! il faudrait que les puissances soient minimales. Si on teste quelques valeurs on trouve que ce nombre doit se décomposer au mieux en 2^quelquechose*3^quelquechose*5^{un dernier quelquechose}, les quelquechoses devant être les plus grands possibles de tel sorte qu'on ne dépasse pas 2000. Il nous reste alors plus beaucoup le choix.

Le problème se résume alors en : retrouver les plus grands nombres a1, a2 et a3 tels que 2^a1*3^a2*5^a3 < 1999, on passe au logarithme et on :
a1* ln2 + a2*ln3 + a3ln5 < ln 1999. Après quelques essais, on trouve le résultat : a1 =3 a2=2 et a3=2, on a alors le nombre n = 2³ *3²*5² qui est le nombre entre 1 et 1999 qui admet le plus de diviseurs, c'est 1800 et il admet (3+1)(2+1)(2+1)=36 diviseurs!!

Si on s'y prenait autrement on voit que parmi les "petits nombres" il existe des nombres dits abondants (si je m'en souviens bien) qui ont beaucoup de diviseurs : 12 admet 6 diviseurs, on regarde 1200 il en admet 30, puis on trouve aussi 18 qui admet 6 diviseurs mais qui en plus est divisible par 9 et on a alors : 1800 qui a 36 diviseurs, je m'en doutais depuis le début mais c'est la démonstration qui m'a gêné.

Voilà pour info, c'était un exo proposé lors des championnants internationaux de jeux mathématiques et logiques, donc...tous les coups sont permis! je me demande même si ils acceptaient les réponses sans justification (j'aurais eu bon!), après tout la question ne demandait pas de démonstration....

Vous en pensez quoi? aurai-je trouvé la bonne réponse? quelqu'un a une meilleure rédaction ou une généralisation (parce que moi, c'était vraiement intuitif, le but étant de minimiser l'étendue du problème et j'ai procédé par élimination...)

J'attends vos avis et vos réponses avec impatience
-----

[invite85d09bae]

PS: j'ai essayé d'y aller un peu rigoureusement en considérant une application f qui à tout naturel n associe son nombre de diviseurs (a1+1)(a2+1)...(ak+1), il suffirait alors de trouver le maximum de cette application dans l'intervalle 1; 1999, mais on peut s'imaginer sa représentation graphique, c'est assez chaotique comme nuage de points (des nombres ont beaucoup de diviseurs, d'autres peu et d'autres pas du tout : les nombres premiers), donc je ne sais pas si quelqu'un a une piste de ce côté-ci....

[danyvio]

Intuitivement, je dirais qu'il faudrait chercher du côté de la puissance du plus petit diviseur premier existant.......

[invite85d09bae]

Intuitivement, je dirais qu'il faudrait chercher du côté de la puissance du plus petit diviseur premier existant.......

C'est-à-dire 2? la plus grande puissance de 2 inférieure à 1999 est 1024, soit 2¹⁰ , ce qui fait 10+1 diviseurs....et si on rajoute un autre diviseur premier, c'est-à-dire 3, le suivant, il faut diminuer la puissance de 2, et le plus grand devient 2⁹*3 = 1536, qui admet 20 diviseurs... on remarque alors que si on augmente la puissance de 3, le nombre de diviseurs augmentera, et on arrive à 2⁷*3²= 1152, qui a 24 diviseurs.....si on essaye avec 3³ on a 2⁶*3³ =1728, et 32 diviseurs...si on veut plus de diviseurs, on va devoir diminuer ces puissances et rajouter une certaine puissance de 5, ce qui fait, en gardant 3², 2⁵*3² *5 = 1440 qui admet....36 diviseurs?!! et si on augmente la puissance de 5? 2³*3²*5² = 1800 qui a également 36 diviseurs! et si on continue on monte au-dessus de 1999.

En effet, c'est une solution de commencer par la puissance du plus petit diviseur premier, et en effet c'est assez intuitif....mais le résultat qui me dérange c'est qu'il existe 2 nombres qui ont le même nombre de diviseurs...1800 et 1440....???

[A voir en vidéo sur Futura]

[invite85d09bae]

EDIT : 2³*3⁵=1944, qui a 24 diviseurs, ...8*5*27=1080, qui a 32 diviseurs...

1440....= 12*12*10 en effet ca fait beaucoup de diviseurs mais était-ce une question piège du problème?? ou il existe un nombre qui a plus de 36 diviseurs et dans ce cas je me suis trompé??

[invite85d09bae]

En calculant 5ln2 + 2ln3 +ln5 je trouve que c'est effectivement inférieur à ln1999, mais c'est aussi inférieur à 3ln2 + 2ln3 + 2ln5 et pourtant ils ont le même nombre de diviseurs! le nombre de diviseurs de 1800 est, je pense, la seule solution des plus grands nombres a1, a2 et a3 tels que 2^a1*3^a2*5^a3 < 1999... j'ai dû faire une erreur quelque part...

[bubulle_01]

Et 1680 ?

Ce qui donne diviseurs.
Soit 40 diviseurs

[invite85d09bae]

merci bubulle, tu m'as bien cassé là

Personne pour une démo ou un théorème rigoureux, pour éviter les erreurs comme la mienne (je me fierai plus jamais à mon intuition ca me fait toujours la même chose )!

[bubulle_01]

J'ai réfléchi un peu.
Plus il y a de facteurs premiers, plus il y a de diviseurs.
Soit le nombre cherché.
car et
Ainsi
Or soit soit soit
On cherche ainsi le nombre tel que soit le nombre ayant le plus de diviseurs et tel que
On trouve facilement
Or
D'où
Quelques explications sont passées à la trappe, mais je pense que cela reste compréhensible pour tout le monde ^^

[invite85d09bae]

Woohow! Merci beaucoup, je comprends beaucoup mieux

[Elie520]

Bonjour tout le monde !
Je suis en terminale S spé maths, et cet exo figure dans mon bouquin, je l'ai trouvé interessant, voila pourquoi je suis là ^^

Je voudrais donc dire à Bubulle que pour moi, ton raisonnement est ici bon et je pense ta réponse juste (mais je ne certifie rien!), mais justement pour une raison : l'intervalle de travaille.
En effet, tu dis qu'il vaut mieux avoir beaucoup de facteurs.
mais avec trois facteurs a la puissance une, tu aurais un diviseur de moins que deux facteurs à la puissance 2. maintenant, pour les facteurs que nous utilisons sur notre intervalle de travail, à savoir 2, 3, 5 ou 7, je te concède que 2*3*5=30 estinférieur à 2²*3²=36.
En revanche, si l'énoncé est le même mais sur [1, 10¹⁰⁰] par exemple... Je ne suis plus sûr de ta technique. En effet, la fréquence d'apparition des nombres premiers diminue au fur et a mesure de la grande valeur des nombres. Ainsi, peut-etre qu'avec 10¹⁰⁰ (nombre choisi au hasard), nous aurions un énorme chiffre premier qu'il vaudrait mieux remultiplier par lui-meme un certain nombre de fois plutot que de prendre le suivant, car trop éloigné...
Je ne sais pas si je suis à peu près clair ou du moins compréhensible, mais c'est une question que je me pose. Maintenant, je suis peut-etre completement dans le faux...
Si quelqu'un a une idée à ce sujet, merci ^^.