Diviseur

Bonjour à tous,

étant données mes capacités limitées en ce domaine, je me permets de vous poser une petite question : quel est le plus petit nombre qui a 1 million de diviseurs ?

Amicalement,

Réponses

  • $1 000 000!$ peut etre, ou alors je me plante mais comme ça a vu de nez...
    amicalement
    sub
    ps: au cas où $100000!=1*2*3*...*999999*1000000$
  • Je ne suis pas bon arithmeticien, mais je suis déjà sûr que c'est faux ...
    Exemple, le plus petit nombre qui a 8 diviseurs n'est pas 8! mais 24 ...
  • Je suis presque sûr qu'il y a une règle récursive sous-jacente où on a le choix entre incorporer des nombres premiers supplémentaires et augmenter la puissance des nombres premiers déjà présents ...

    Ou alors il y a peut être une astuce énorme qui me passe au-dessus (ça ne m'atonnerait pas)
  • Salut,

    si les diviseurs peuvent etre identiques, il s'agit de $2^{1000000}$; autrement, si tous les diviseurs sont differents, il s'agit du produit des 1000000 premiers nombres premiers.

    @l
  • Bien dit @!
    sub
  • Salut,
    Pourquoi pas 1 dans ce cas

    a+
  • Salut @l,

    les diviseurs doivent être différents. Ceci dit, je ne suis vraiment pas sûr de ta réponse ... Voir l'exemple pour 8 diviseurs que j'ai donné : 24 n'est pas le produit des 8 premiers nombres premiers ...
  • Oui, mais $1$ c'est pas drole....

    @l
  • Cela devrait se trouver en utilisant le résultat qui suit :

    Si la décomposition en facteurs premiers N est constituée de n facteurs premiers p1, p2, ..., pn avec pour exposants respectifs a1, a2, ..., an, le nombre de diviseurs de N est (1+a1)(1+a2)...(1+an).

    Désolé, mais je ne me suis toujours pas mis au LaTeX.
  • Pose toi la question avec 3 diviseurs, puis 6 diviseurs puis 12 diviseurs, en utilisant ce que MichelR vient de proposer.
  • Effectivement, j'ai mal interprete la question; la reponse est donc $2^{999999}$
    En effet, ce nombre a uniquement $2^k$ comme diviseur pour $k$ compris entre $0$ et $999999$, soit $1000000$ de diviseurs differents.

    @l
  • Bon, ok, c'est pas encore bon.... c'est pas le plus petit.... et ce qui vient d'etre ecrit resout le probleme.... Au temps pour moi...

    @l
  • Mon point de vue diffère légèrement de celui de Michel et Eric :

    La solution doit être proche de :

    min $2^i\;3^j\;5^k\;7^l\;11^m\dots$

    tel que $1 000 000 = (i+1)(j+1)(k+1) (l+1)(m+1)\dots$

    mais il y a des exceptions (par exemple 5 ou 7). Il n'existe pas de nombre divisible par uniquement 7 nombres différents...

    Julien
  • peut etre que j'ai mal compris ce que tu viens de dire, mais 64 a bien 7 diviseurs
  • Effectivement gandhi, je me suis trompé sur les cas particuliers qui n'existent pas.

    Donc normalement le problème de minimisation précédent (cette fois compilé) doit résoudre le problème, non?

    min $2^i\;3^j\;5^k\;7^l\;11^m\dots$

    tel que $1 000 000 = (i+1)(j+1)(k+1) (l+1)(m+1)\dots$
  • ça serait pas $2^{4}*3^{4}*5^{4}*7*11*13$?
    (en utilisant le résultat de michelR)

    jjric
  • Au fait salut tout le monde,

    ça serait pas $2^{4}*3^{4}*5^{4}*7*11*13$?
    (en utilisant le résultat de michelR)

    jjric

    jjric
  • n=$p_1^e_1$$p_2^e_2$...$p_k^e_k$
    On suppose les $p_i$ premiers 2 à 2 et les $e_i\geq$1
    Un diviseur de n est de la forme $p_1^\alpha_1$...$p_k^\alpha_k$
    avec 0$\leq\alpha_i\leq$$e_i$

    Chaque r-uplet ($\alpha_1$, ..., $\alpha_k$) donne un diviseur différent.
    On a $e_i$+1 possibilités pour $\alpha_i$
    Soit en tout ($e_1$+1)...($e_k$+1) possibilités

    Ici on a ($e_1$+1)...($e_k$+1)=1 000 000

    On cherche k nombres $\geq$2 tels que leur produit vaut 1 000 000

    1 000 000=$2^65^6$

    Prenons par exemple k=2

    et $e_1$=$2^6$-1 et $e_2$=$5^6$-1 (ou vice-versa)

    Donc pour que n soit le plus possible, il faut $p_1$ et $p_2$ les plus petits possibles et prendre $p_2\leq$$p_1$

    $p_1$=3 et $p_2$=2

    n=3^($2^6-1$)*2^($5^6-1$) a 1 000 000 de diviseurs.
    Pour trouver le plus petit, je te laisse raisonner sur le choix de k
  • Goumies,
    Je pense que tout est dans le choix de $k$ mais je n'arrive pas à trouver de règle qui permette de le déterminer...

    jjric,
    il me semble que le nombre que tu proposes possède 1000 diviseurs non ?
    $(4+1)^3*(1+1)^3=1000$
  • Si je ne m'abuse, jjric, ton nombre ne possède QUE 1000=5 x 5 x 5 x 2 x 2 x 2 diviseurs.

    Je propose plutôt $2^4.3^4.5^4.7^4.11^4.13^4.17^3.19^3.23^3= 333435935858231447328177090000$.

    Il a bien le bon nombre de diviseurs et je crois que c'est bien le plus petit.
  • Bisam et que penses tu de $2^43^45^47^411^413^4$.17.19.23.29.31.37 ?
  • Ben il suffit de prendre le produit des 1 000 000 eme premiers nombres premiers... je vois pas comment on peut faire plus petit !
  • je viens de dire une connerie au temps pour moi
  • On ne t'en veut pas mon 0 :)
  • Goumies
    a la solution la plus intuitive (a mon gout) puisque $1 000 000 = 2^6 5^6$ mais comment montrer que c'est bien le plus petit ?...
  • et que pensez vous de

    $2^9* 3^4 *5^4 *7^4 *11^4 *13^4 *17 *19 *23 *29 *31$ ???
  • Ta nouvelle proposition était mieux que la mienne, Goumies, mai je crois que JulienB se rapproche dangereusement d'une solution finale !
  • Bonjour,

    Une amélioration de la solution proposée par julienB =

    F = 2^9*3^4*5^2*7^2*11^2*13^2*17*19*23*29*31*37*41*43
    nb diviseur (F) = 1036800
    F est environ 384 fois plus petit que la solution de julienB

    Est-on encore loin de l'optimum ?
  • Re-bonjour
    Addendum
    Le nombre que je propose ne répond pas exactement au problème initial de Kuja, mais au problème suivant :
    "Quel est le plus petit nombre ayant au moins 1 000 000 diviseurs"

    Si l'on fixe strictement le nombre de diviseurs à 1 000 000, la proposition de julienB me paraît optimale.
  • Souvent dans ce type de problème, on commence par majorer le nombre $\omega(n)$ de facteurs premiers {\it distincts} de $n$ par l'inégalité connue $2^{\omega(n)} \leqslant \tau(n)$, où $\tau(n)$ est, comme d'habitude, le nb de diviseurs de $n$. Ici, un entier ayant $10^6$ diviseurs a donc au plus $19$ facteurs premiers distincts, ce qui réduit le champ des recherches.

    A titre d'un autre exemple, voici un exo que l'on donne souvent en TS spécialité : déterminer deux entiers naturels ayant $10$ diviseurs communs et dont la somme vaut $672$.

    Borde.
  • Je me lance sur ton exo, Borde.
    672/2=336
    336=2^4.3.7
    Donc 336 admet 20 diviseurs... qui sont communs avec ceux de 336.
    Donc (336,336) est une solution !

    Sinon, on peut aussi écrire : 672=2^5.3.7=2^5.3^2+2^7.3=288+384
    Or le pgcd de ces 2 nombres vaut 96 donc ces deux nombres ont en commun les diviseurs : 1,2,3,4,6,8,12,16,24,32,48,96 soit 12 diviseurs.
    Donc (288,384) est une autre solution.
  • 48+624
    144+528
    240+432
    112+560
    168+504
    sont les seules décompositions avec exactement 10 diviseurs communs.


    Bonne journée à vous.

    Marc
  • Et la dernière est fausse ! elle en a 12 aussi...

    Sur ce, je file à la bourse aux minéraux.

    Marc
  • Bonsoir,

    merci à tous pour vos contributions ( et surtout à JulienB qui, secret dévoilé, partage le même bureau que moi), je regarde ça.
    D'après ce qu'on m'en a dit, la solution est un nombre qui comprend 27 chiffres ...

    Amicalement,

    ps : au passage pour Borde, bonjour, celà fait longtemps que je ne t'ai vu. Cependant, tu me vois désolé de ne pas avoir eu la solution de manière immédiate de ta part :-).
  • Salut à tout le monde,

    J'avais un peu perdu de vue ce fil...et c'est très agréable de voir les réflexes, très rapides, de certains pour résoudre l'exo que j'avais mis (exo que je considère de bon niveau, d'ailleurs).

    Pour ma part, je procède aussi comme suit : si $a,b$ sont les entiers cherchés, poser $d$ leur pgcd puis, classiquement, $a=da'$ et $b=db'$ de sorte que $\gcd(a',b') = 1$. De plus, puisque $2^{\omega(d)} \leqslant \tau(d) = 10$, il vient $\omega(d) \leqslant 3$ puis $d = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3}$ avec $(\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1) = 2 \times 5$. On peut supposer $\alpha_1 \leqslant \alpha_2 \leqslant \alpha_3$ ce quipermet d'obtenir $\alpha_1 = 0$, $\alpha_2 = 1$ et $\alpha_3 = 4$, puis $d = p_1 p_2^4$. D'autre part,$d \leqslant 672/2 = 336, ce qui entraîne que $p_2 \leqslant 3$ et donc $p_1 \leqslant 21$. Le reste est routine.

    Cette solution est plus longue que celles proposées par nos amis Bisam et Robomarc, mais, pédagogiquement, je la trouve "confortable". Il me semble qu'elle permet aux élèves de voir les réflexes à avoir sur ce genre d'exos. Qu'en pensez-vous ?

    Borde.
  • Salut à tout le monde,

    J'avais un peu perdu de vue ce fil...et c'est très agréable de voir les réflexes, très rapides, de certains pour résoudre l'exo que j'avais mis (exo que je considère de bon niveau, d'ailleurs).

    Pour ma part, je procède aussi comme suit : si $a,b$ sont les entiers cherchés, poser $d$ leur pgcd puis, classiquement, $a=da'$ et $b=db'$ de sorte que $\gcd(a',b') = 1$. De plus, puisque $2^{\omega(d)} \leqslant \tau(d) = 10$, il vient $\omega(d) \leqslant 3$ puis $d = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3}$ avec $(\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1) = 2 \times 5$. On peut supposer $\alpha_1 \leqslant \alpha_2 \leqslant \alpha_3$ ce qui permet d'obtenir $\alpha_1 = 0$, $\alpha_2 = 1$ et $\alpha_3 = 4$, puis $d = p_1 p_2^4$. D'autre part, $d \leqslant 672/2 = 336$, ce qui entraîne que $p_2 \leqslant 3$ et donc $p_1 \leqslant 21$. Le reste est routine.

    Cette solution est plus longue que celles proposées par nos amis Bisam et Robomarc, mais, pédagogiquement, je la trouve "confortable". Il me semble qu'elle permet aux élèves de voir les réflexes à avoir sur ce genre d'exos. Qu'en pensez-vous ?

    Borde.
Connectez-vous ou Inscrivez-vous pour répondre.