Trouver les entiers qui ont le même nombre de diviseurs

[C_dur]

Bonjour,

Trouvez le nombre d'entier compris entre 1 < n < 10^7 (10 exposant 7) pour lesquels n et n+1 ont le même nombre de diviseurs?

Par exemple
# 14 à les diviseurs positifs 1, 2, 7, 14 tandis que 15 à 1, 3, 5, 15.

C'est un problème de programmation mais en brute force, cela ne fonctionne pas.
Je me demandais si il existait un algorithme répondant à ce besoin.
J'aurais bien été vérifié sur le Net mais je ne sais pas dans quelle direction chercher.

En vous remerciant d'avance,
C_dur

[XENSECP]

Ca veut rien dire ton énoncé !

[lapras]

Soit f(n) le nbre de diviseurs positifs de n.
trouver les n tels que f(n+1)=f(n).

Voila l'énoncé peut etre plus compréhensible

[jeancam]

Soit f(n) le nbre de diviseurs positifs de n.
trouver les n tels que f(n+1)=f(n).

Voila l'énoncé peut etre plus compréhensible

oui
on pourrait peut etre se contenter de montrer qu il y en a une infinité.

[C_dur]

Ca veut rien dire ton énoncé !

Sorry, j'ai refais l'énoncé et mis un exemple

[Doraki]

C'est marrant ça me rappelle un truc

Qu'est-ce que t'appelles brute force ?
Evidemment si t'essayes de factoriser tous les entiers de 1 à 10^7 c'est assez stupide et ça prend plein de temps. (si tu comptes les diviseurs de n en essayant de diviser par tous les nombres plus petits que n c'est encore plus stupide et c'est normal si ça prend des semaines)
Pour obtenir la décomposition en facteurs premiers d'un gros paquet de nombres, faut pas procéder comme ça.

Mais somme toute y'a pas d'algo super intelligent ou miraculeux à faire ici.

T'as intérêt à coder en C pour ce genre de truc aussi, sinon c'est lent.

[ThSQ]

on pourrait peut etre se contenter de montrer qu il y en a une infinité.

C'est un problème ouvert (problème d'Erdös-Sierpinski) mais ça coute rien d'essayer !

Un truc sympa est de montrer que si (n) = (n+1) alors (n) est un multiple de 2 ou 3.

[jeancam]

oui
on pourrait peut etre se contenter de montrer qu il y en a une infinité.

je propose la generalisation suivante
N(k,i) est l ensemmble des n tel que f(n)=f(n+1)=...f(n+i)=k
ou f est cette fois le nombre de divideurs premier comptés avec leur multiplicité (ex f(24)=4)
dire quand N(k,i) est non vide ou infini...
comme on trouvera pas je propose d etudier N(2,1).

[C_dur]

C'est marrant ça me rappelle un truc

J'ai découvert le project Euler il y a peu et j'essaie de résoudre les problèmes en Python et en C (juste pour le fun, je ne suis pas ingénieur ni féru de math... mais cela m'occupe l'esprit)

Evidemment si t'essayes de factoriser tous les entiers de 1 à 10^7 c'est assez stupide et ça prend plein de temps.

Je m'en suis rendu compte, merci loll

Pour obtenir la décomposition en facteurs premiers d'un gros paquet de nombres, faut pas procéder comme ça.

C'est cette méthode que je recherche

Mais somme toute y'a pas d'algo super intelligent ou miraculeux à faire ici.

Ok, donc je vais recherche du coté de la décomposition en facteurs premiers.
Les algo de math répondent souvent aux problèmes de programmation alors je me renseignais :+)

T'as intérêt à coder en C pour ce genre de truc aussi, sinon c'est lent.

Je m'amuse à comparer les résultats obtenus entre le C et Python, donc, pas de problème de ce côté là... il me reste juste à arriver à la bonne solution.
Merci et à bientôt,
a+

[Quidam]

J'ai découvert le project Euler il y a peu et j'essaie de résoudre les problèmes en Python et en C (juste pour le fun, je ne suis pas ingénieur ni féru de math... mais cela m'occupe l'esprit)

Je propose la méthode suivante.

Etant donné que le nombre de diviseurs de si les sont premiers est égal à , si p est le plus petit nombre premier entrant dans la décomposition en facteurs premiers de N et si , k premier avec p, alors le nombre de diviseurs de N est le produit du nombre de diviseurs de k et du nombre de disiseurs de (ce dernier étant égal à ).

Je décris donc la liste des entiers n, de 2 à , dans cet ordre, en définissant à la main "(nombre des diviseurs de 2)=2". Pour chaque n, je cherche son plus petit facteur premier p ; si n est premier, je note que son nombre de diviseurs est 2 ; sinon je divise n autant de fois que je peux par p pour connaitre l'exposant de p dans la décomposition et je dis que le nombre de diviseurs de n est fois le nombre de diviseurs de qui est forcément déjà calculé puisque j'ai décrit la liste dans l'ordre croissant et que