Le nombre de diviseur d'un nombre c'est la multiplication de chacun des exposant d'une décomposition en facteur premiers, augmentés de 1.

Si x = a^b+c^d, alors le nombre possède (b+1)*(d+1) diviseurs.

Le but est donc de trouver ces exposants minimisant le nombre de départ.

Je n'ai pas de vrai méthode, mais sans réfléchir longuement :

Sachant que la décomposition en facteurs premiers de 1000000 est 2^6*5^6
On peut imaginer un nombre tel x = a^(2^6-1)*b^(5^6-1) qui aura 1000000 diviseurs.
Le plus petit est : [latex]2^{15624}3^{63}[/latex]

Peut-on réitérer cette méthode ? Je pense que oui, je reviendrais sur ce topic.

Edit : me revoilà.

Alors, 15625 = 5^6, on cherche donc un premier facteur tel x = a^(5-1)*b^(5-1)*c^(5-1)*d^(5-1)*e^(5-1)*f^(5-1)

et 64 = 2^6, on cherche donc un second facteur tel x = a^(2-1)*b^(2-1)*c^(2-1)*d^(2-1)*e^(2-1)*f^(2-1)

Le plus petit possible est :
[TeX]2^4 3^4 5^4 7^4 11^4 13^4 17\times19\times23\times29\times31\times37[/TeX]
Je m'aperçois que ma méthode n'est surement pas la bonne car elle sous entend que l'on pourrait continuer.

En tout cas, par tatonnement informatique, la réponse qui semble la plus petite :
[TeX]2^9 3^4 5^4 7^4 11^4 13^4 17\times19\times23\times29\times31 = 173804636288811640432320000[/TeX]

C'est un problème intéressant

J'appelle [latex]N[/latex] ce nombre. Sa décomposition en facteurs premier peut s'écrire [latex]N=2^{r_1}\times 3^{r_2}\times 5^{r_3}\times \dots\times p_n^{r_n}[/latex], avec [latex]r_1\ge r_2\ge\cdots\ge r_n[/latex] pour avoir N le plus petit possible.

Comme [latex]N[/latex] possède exactement [latex]\prod_{i=1}^n(1+r_i)[/latex] diviseurs, il faut chercher [latex]n[/latex] et les [latex]r_i[/latex] tels que [latex]\prod_{i=1}^n(1+r_i)=10^6=2^6\times 5^6[/latex]. En particulier, les [latex]1+r_i[/latex] sont à choisir parmi les diviseurs de [latex]2^6\times 5^6[/latex].

Ensuite, je pense qu'il vaut mieux choisir [latex]n[/latex] grand pour avoir des exposants plus petits, mais je n'ai pas le courage d'essayer de de le démontrer. Donc je propose le nombre suivant :

[latex]N=2^4\times 3^4\times 5^4\times 7^4\times 11^4\times 13^4 \times 17\times 19\times 23 \times 29 \times 31 \times37[/latex].

un nombre de la forme [latex]p_1^{n_1-1}\times p_2^{n_2-1}\times \ldots \times p_k^{n_k-1}[/latex] où les [latex]p_i [/latex] sont des nombres premiers, a [latex]n_1\times n_2 \times \ldots \times n_k[/latex] diviseurs : tous les [latex]p_1^{i_1}\times p_2^{i_2}\times \ldots \times p_k^{i_k-1}[/latex] avec [latex]i_1 \in 0..n_1-1, i_2 \in 0..n_2-1, \ldots, i_k \in 0..n_k-1 [/latex]

Pour trouver le plus petit nombre qui a exactement un million de diviseurs il faut donc que le produit des exposants des facteurs premiers soit un million :
[TeX]n_1\times n_2 \times \ldots \times n_k = 1000000=10^6=2^6*5^6[/TeX]
Bien évidemment on utilisera les plus petits nombres premiers et on prendra soin d'attribuer les plus gros exposants aux facteurs premiers les plus petit.


on cherche donc le minimum des [latex]2^{n_1-1} \times 3^{n_2-1} \times 5^{n_3-1} \times \ldots[/latex] avec  [latex]n_1 \le n_2 \le \ldots \le n_k[/latex] et [latex]n_1\times n_2 \ldots n_k = 2^6*5^6[/latex]

soit aussi le min des [latex](n_1-1)\log (2) + (n_2-1) \log (3) + (n_3-1) \log (5) +\ldots[/latex]

À partir de là on peut écrire un algorithme rapide sans se soucier de la taille des nombres utilisés en décomposant les [latex]n_i[/latex] en produits de [latex]2^{a_i}\times5^{b_i}[/latex] avec [latex]\sum a_i = \sum b_i = 6 [/latex]

1000000 contient 6 facteurs 5 et 6 facteurs 2.
Un nombre raisonnable ayant 1000000 de diviseurs est
[TeX]A_1 = 2^4* 3^4 *5^4 *7^4 *11^4 *13^4 *17 *19 *23 *29 *31*37[/TeX]
On voit cependant que 37 est plus grand que [latex]2^5[/latex], d'où l'amélioration suivante :
[TeX]A_2 = 2^9* 3^4 *5^4 *7^4 *11^4 *13^4 *17 *19 *23 *29 *31[/TeX]
Vouloir utiliser [latex]2^{24}[/latex] ou [latex]3^9[/latex] serait déraisonnable, donc je m'arrête là...

2^999999 ?
qui compte pour diviseur 1,2,4,8,16 ......

je me suis fait eu

mais "le meilleur meilleur moyen de resister a la tentation est d'y ceder"

Tu aime les S, toi!
anonymeS certainS nombreS

Regarde les réponses données au-dessus Celles d'EfCeBa, Emaths et Scrablor sont bonnes, et Vasimolo résume leur méthode quelques posts au-dessus de celui-ci