Plus petit entier n ayant d diviseurs
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 ?
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 ?
Réponses
-
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}$. -
@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] -
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). -
@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 -
Bon, la réparation risque de tourner usine à gaz, je ne me lance pas dedans.
-
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() -
Ritournelle :quel que soitquelle que soitquels que soientquelles que soient
-
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.
-
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
Ritournelle :$i$-ème,$j$-ème,$n$-ième.e.v.Personne n'a raison contre un enfant qui pleure.
-
lourran vient de retrouver une suite chère à Ramanujan.
-
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres