Plus petit entier n ayant d diviseurs

joel_5632 · June 2017

Bonjour
Comment trouver le plus petit entier n ayant exactement d diviseurs ?
Évidemment on peut prendre les entiers naturels un par un $1, 2, 3, 4, ...$ puis déterminer leurs nombres de diviseurs jusqu'à tomber sur $d$.
Trouver le nombre $d$ de diviseurs de $n$ est facile à partir de la décomposition de $n$ en nombres premiers.
Si $ n = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_k}^{e_k}$ alors $ d = (e_1+1)(e_2+1)\cdots(e_k+1)$.
On est certain que la recherche se terminera car quelque soit $d$ il y a toujours un entier ayant $d$ diviseur (ex $2^{d-1}$).
Autrement, en partant de $d$, on peut aussi chercher les entiers $e_i$ tels que
$ d = (e_1+1)$ ou
$ d = (e_1+1)(e_2+1)$ ou
$ d = (e_1+1)(e_2+1)(e_3+1)$ ou
etc. autant que possible,
puis pour chaque $n$-uplet $(e_1, e_2, \ldots, e_k)$ trié dans le sens décroissant, on forme $n = 2^{e_1}3^{e_2}\ldots$ puis on prend le plus petit des $n$ ainsi obtenus. Mais c'est nettement plus dur à réaliser.
Est-ce qu'il y a d'autres méthodes connues ?

GaBuZoMeu · June 2017

Recette :
Soit $p_1=2,p_2=3,p_3=5,\ldots$ la liste des nombres premiers dans l'ordre croissant (strictement).
Étant donné $d\geq 2$, factoriser $d=\prod_{j=1}^k p_{i(j)}$ de telle sorte que $i(j)\geq i(j+1)$ pour tout $j$ de $1$ à $k-1$. Retourner $n=\prod_{j=1}^k p_j^{p_{i(j)}-1}$. 64132

joel_5632 · June 2017

@GaBuZoMeu

Ta recette donne bien un entier n ayant d diviseurs mais ce n'est pas toujours le plus petit.

1ère col : d 
2ème col : le plus petit entier ayant d diviseurs
3ème col : Le résultat de ta méthode

 2      2      2
 3      4      4
 4      6      6
 5     16     16
 6     12     12
 7     64     64
 8     24     30    <----
 9     36     36
10     48     48
11   1024   1024
12     60     60
13   4096   4096
14    192    192
15    144    144
16    120    210   <----
17  65536  65536
18    180    180
19 262144 262144

Sinon pour info quel module python utilises tu pour avoir les fonction divisors et factor de même que la méthode factor sur un entier ?

[Quand quelqu'un met en forme ton message évite de supprimer ultérieurement cette mise en page. Merci. AD :-X]

GaBuZoMeu · June 2017

OK, je vois le problème. Je vais réfléchir (mais pas trop fort) pour voir si ça se répare facilement.
J'utilise Sage (qui est écrit en python).

joel_5632 · June 2017

@AD Désolé je n'ai pas vu que quelqu'un avait changé la mise en page

@GaBuZoMeu

J'ai fait quelques recherches avec google. La suite des plus petits entiers ayant d diviseurs pour d=1, 2, 3 ... est répertoriée ici: A005179

La suite des nombres obtenus avec ta méthode est également répertoriée A037019

Quand les 2 suites correspondent, les entiers sont qualifiés d'ordinaires, sinon extraordinaires

et un algorithme pour la génération de A005179 http://www.primepuzzles.net/problems/prob_019.htm qui correspond à la 2 ème méthode de mon 1er message

GaBuZoMeu · June 2017

Bon, la réparation risque de tourner usine à gaz, je ne me lance pas dedans.

adrien_condamine · February 2022

Bonjour je pense avoir réussi à coder un petit algorithme en Python qui permet de générer la suite des plus petits nombres ayant n diviseurs (A005179). Je ne suis qu'un élève de terminale et je ne fait même pas spécialité NSI donc pardonnez-moi pour les éventuelles redondances de code... En espérant avoir pu vous aider. Bonne journée.

def plus_petit_nbr():
    list_0 = []

    d = int(input("Quel est le nombre de diviseurs que tu veux que ton nombre ait ?\n"))
    D = d
    z = 2
    while z <= d:
        if d % z == 0:
            list_0.append(z)
            d = d / z
        else:
            z = z + 1
    list_0.sort(reverse=True)
    print(list_0)

    a = len(list_0)
    list_prem = []
    i = 1
    count = 0
    x = len(list_0)
    while count < x:
        t = 0
        for j in range(1, (i + 1), 1):
            p = i % j
            if p == 0:
                t = t + 1

        if t == 2:
            list_prem.append(i)
            count = count + 1
        i = i + 1
    x = 0
    N = 1
    for x in range(0, a):
        N = N * list_prem[x] ** (list_0[x] - 1)

    list_min = []
    list_max = []
    trash_list = []
    for x in range(a):
        if list_0[len(list_0) - 1] == list_0[len(list_0) - 1 - x]:
            list_min.append(list_0[len(list_0) - 1 - x])

        else:
            list_max.append(list_0[len(list_0) - 1 - x])
        x = x + 1

    print(list_min)
    print(list_max)
    b = len(list_min)

    for x in range(0, b - 1):
        trash_list.clear()
        list_prem.clear()
        c = list_min[(len(list_min) - 1)] * list_min[len(list_min) - 2]
        list_min.pop()
        if len(list_min) > 0:
            list_min.pop()
        list_min.append(c)
        list_min.sort(reverse=True)
        list_max.extend(list_min)
        list_max.sort(reverse=True)
        for k in range(1, len(list_max) + 1):
            trash_list.append(list_max[-k])
        trash_list.sort(reverse=True)
        list_max.pop()
        print("trash list")
        print(trash_list)
        for r in range(len(list_min) - 1):
            list_max.pop()

        i = 1
        count = 0
        x = len(trash_list)
        while count < x:
            t = 0
            for j in range(1, (i + 1), 1):
                p = i % j
                if p == 0:
                    t = t + 1

            if t == 2:
                list_prem.append(i)
                count = count + 1
            i = i + 1
        print(list_prem)
        x = 0
        n = 1
        for x in range(0, len(trash_list)):
            n = n * list_prem[x] ** (trash_list[x] - 1)
        print(n)
        if n <= N:
            N = n
    print("\n Le plus petit nombre ayant \n" + str(D) + " diviseurs est " + str(N) + "\n")
plus_petit_nbr()

Chaurien · February 2022

Ritournelle :

quel que soit

quelle que soit

quels que soient

quelles que soient

Chaurien · February 2022

Oui, elle est très curieuse cette suite https://oeis.org/A005179 dont le $n$-ème terme est le plus petit entier ayant exactement $n$ diviseurs. Les suites de l'OEIS sont le plus souvent croissantes, et ce n'est pas le cas de celle-ci.

lourrran · February 2022

Quel est le plus petit entier ayant au moins n diviseurs donnerait une suite en escaliers, mais plus naturelle.

1 2 4 6 12 12 24 24 36 48 60 60 120 120 120 120 180 180 240 240 360 360 360 360 720 720 720 720 720 720 840 840 1260 1260 1260

Et la même suite, mais dédoublonnée :

1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 10080 15120 20160 25200 27720 45360 50400 55440 83160

C'est marrant, parce que le facteur 11 apparaît (27720), puis disparaît (45360 ou 50400) pour ensuite réapparaître (définitivement ?)

J'espère que je ne me suis pas trompé dans mes petits bidouillages.

ev · February 2022

Ritournelle :

$i$-ème,

$j$-ème,

$n$-ième.

e.v.

Boécien · February 2022

lourran vient de retrouver une suite chère à Ramanujan.

lourrran · February 2022

J'avais cherché une dénomination 'simple' pour cette liste, mais je ne trouvais pas. Tout simplement celle donnée sur OEIS : Liste des entiers n, pour lesquels d(n) (le nombre de diviseurs de n) atteint un record.

Plus petit entier n ayant d diviseurs

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 12