Somme des diviseurs et nombres premiers

[Malefix]

Bonjour,

J'ai remarqué une propriété intéressante qui permet de trouver uniquement des nombres premiers.
Soit la somme des carrés des diviseurs d'un entier naturel n, on pose .
Si est un entier alors cet entier est un nombre premier.

Exemple avec :

Or et

Comme 44777358719759 est un entier il est premier.
-----

[pm42]

Question : comment fait on la somme des carrés des diviseurs sans connaitre les diviseurs ?
Et si on connait les diviseurs, est ce qu'on ne sait pas si le nombre est premier ?

Je dis ça vite fait, je n'ai pas réfléchi plus que ça et les maths, cela commence à faire loin.

[jacknicklaus]

Bonsoir
je ne comprends pas. Prenons ton exemple n = 6333441. Les diviseurs de n sont {3,19,23,4831}, la somme des carrés est 23339460, supérieur à n. Donc n-Sigma2(n) est négatif !?

Même en acceptant ceci, on trouve un résultat pour A inférieur de plusieurs ordres de grandeur à ton calcul... Il y a un truc qui cloche...

[Malefix]

Bonjour jacknicklaus,

Il faut en effet prendre la valeur absolue

Pour n=6333441 on a ainsi comme diviseurs distincts 1, 3, 19, 23, 57, 69, 437, 1311, 4831, 14 493, 91 789, 111 113, 275 367, 333 339, 2 111 147 et 6 333 441.

Donc

Donc et

Donc et

Et 44777358719759 est premier.

[A voir en vidéo sur Futura]

[MissJenny]

x et -x ont les mêmes diviseurs, donc le fait que n-sigma(n) soit négatif n'a aucune importance, si on ne compte que les diviseurs positifs dans le calcul de sigma2.

[MissJenny]

annulé ---------------------------

[gg0]

Bonjour,

J'ai remarqué une propriété intéressante qui permet de trouver uniquement des nombres premiers.

Bonjour.

On sait trouver des premiers, y compris de grande taille (disons une centaine de chiffres en décimal) avec des méthodes justifiées. Tu dis "qui permet de trouver uniquement des nombres premiers" : En as-tu la preuve ? Ou as-tu fait quelques essais et t'es-tu convaincu que ça marche toujours ?
D'ailleurs, la condition "Si est un entier " est-elle facile à réaliser ? À priori non, d'autant que plus les nombres sont grands, plus les carrés sont rares.
As-tu d'autres exemples que ? Par exemples, peux-tu nous donner, entre 1 et 6333441 tous les nombres pour lesquels est un entier (et cet entier, premier d'après toi) ?
Si tu n'as pas de preuve de cette affirmation (*), ou au moins de bonnes raisons de la croire, elle est totalement sans intérêt.


(*) est-elle de toi ? J'ai déjà vu ça ailleurs !

[gg0]

En recherchant un peu plus, j'ai vu que ça fait longtemps que tu fais des choses de ce genre, avec les . Mais comme tu te contentes de dire "ça marche", sans preuve, ça ne peut aboutir.
Cordialement.

[ThM55]

Dans l'exemple donné: est premier.

Par conséquent , puisqu'il n'y a que ces deux diviseurs. Donc A est de la forme p^2+1 où p est premier et forcément A-1 est un carré et sa racine est un nombre premier.

Mais en examinant le cas des puissances de premiers, j'ai trouvé un exemple où ce schéma évident n'explique pas le résultat. Par exemple 81 = 3^4:



Donc est composé. Or on a et 47 est bien premier.

(pour 3^3 on tombe sur 13, qui est premier donc même chose que dans l'exemple donné, et pour 3^5, A-1 n'est pas un carré). Je n'ai pas poussé mes recherches plus loin. Il faudrait faire une recherche brute pour un contre exemple.

[BordeleauD]

L'exemple avec n = 81 montre bien que la condition A-1 = k² peut aussi être remplie par des nombres composés. Du coup, on ne peut pas vraiment s'en servir comme critère de primalité sans ajouter d'autres conditions restrictives. Vous pouvez également consulter xxx lien supprimé xxx, j'espère que cela vous sera utile.

[vgondr98]

L'exemple avec n = 81 montre bien que la condition A-1 = k² peut aussi être remplie par des nombres composés. Du coup, on ne peut pas vraiment s'en servir comme critère de primalité sans ajouter d'autres conditions restrictives. Vous pouvez également consulter xxx lien supprimé xxx, j'espère que cela vous sera utile.

En quoi un lien que redirige vers un casino en ligne serait utile ?

[ThM55]

Il ne s'agit pas d'un critère de primalité. Il s'agit de savoir si le résultat de la fonction est premier quand il est entier.

[ThM55]

Je ne me suis pas relu correctement. En effet, je n'ai pas calculé mais . Toutes mes excuses pour cette distraction!

Les diviseurs de 81 sont 1,3,9,27,81 et leurs carrés sont 1,9,81,729 et 6561.

Donc , donc . Et A-1 n'est pas un carré. Donc ce n'est pas l'exemple que je voulais. Désolé pour cette erreur.

Il y a toutefois quelque chose de très particulier dans l'exemple donné initialement, c'est comme je l'ai dit le fait que était un nombre premier, son sigma2 est donc 1+p^2. Dans le cas de n=81, c'est très différent: 7300 a un grand nombre de diviseurs.

[ThM55]

Mais ce mauvais exemple montre tout de même quelque chose d'intéressant: si est un carré, x n'est pas forcément premier car .

Autrement dit, s'il est évident que si p est premier, alors est un carré (c'est ), la réciproque est fausse comme l'exemple de 40 le montre.

Or, une recherche brute sur un ensemble d'entiers me montre que au moins de n=2 jusque n=5000, si est un carré, ce qui se produit de temps en temps et même assez souvent, alors on constate que est premier (d'où par l'implication précédente A-1 est le carré d'un premier). Pas suffisant pour démontrer la propriété mais cela montre qu'il ne sera pas aisé de trouver un contre exemple.

[ThM55]

J'ai poussé la recherche jusqu'à 16917 et tous les cas répertoriés où A-1 est un carré (ils sont nombreux) donnent un nombre premier. Mon programme est écrit "naïvement" en Python et sans optimisation, il devient trop lent pour les grands nombres. Je pourrais le réécrire en Julia avec des optimisation (pré-calcul, tests plus performants) mais je pense que cela n'apporterait pas plus. Il faut se diriger vers la recherche d'une preuve plutôt que vers celle d'un contre-exemple. Et aussi vers des références qui auraient déjà étudié cette question. Je pense qu'on doit pouvoir exploiter les propriétés de division des nombres en notant que si un nombre n est premier, son sigma2 est 1+n^2 et s'il est composé il a au moins un diviseur d différent de 1 et n, ainsi que son conjugué n/d (égal à n si n est carré). Dans ce cas puisque (d-m/d)^2 >= 0 (égalité ssi n carré), on a d^2+(m/d)^2 >= 2m. Cela permet de relier les sigma2 à la valeur de n. Il faut aussi noter que cette fonction somme des carrés des diviseurs est multiplicative, ce qui permet de trouver une formule explicite pour tout n. C'est juste une piste, je n'ai pas été plus loin.

Chose curieuse, la suite des nombres qui vérifient la propriété (2, 3, 4, 7, 13, 21, 33, 67, ...) n'est pas répertoriée dans l'encyclopédie des suites de Sloane (https://oeis.org/), ni la suite de nombres premiers correspondants (3,7,17,43,157,479,1187,4423,5 231,...).

A mon avis c'est une conjecture très intéressante.

[Malefix]

Bonjour à tous,

@gg0 : oui elle est de moi, peut-être que j'ai retrouvé une propriété qui existe déjà mais dans ce cas j'ai redécouvert la propriété de manière indépendante.

@ThM55 : merci pour l'étude de la propriété avec ton code Python, je pense en effet qu'il s'agit d'une propriété intéressante.

[ThM55]

Je suis de cet avis aussi car il n'existe pas beaucoup de formules simples qui ne génèrent que des nombres premiers. Néanmoins, il faut situer cela dans un cadre. Des algorithmes très simples (directement à partir de la définition, crible...) génèrent systématiquement tous les nombres premiers ou tous ceux dans un intervalle. Ici, on doit faire des opérations assez similaires: trouver les diviseurs, additionner leurs carrés, faire un test pour voir si un nombre est un carré, etc. En fait tout cela est un travail sur les diviseurs, c'est un algorithme, ce n'est pas un simple calcul algébrique.

Je parlais d'une démonstration, mais il faut comprendre soit comme une démonstration de la conjecture, soit comme une démonstration de sa réfutation. Ce n'est qu'une impression mais je crois que ce sera plus productif que la recherche d'un contre-exemple (celui-ci pourrait exister mais être si grand qu'il reste hors de portée d'une recherche force brute). Tu devrais envoyer ta conjecture à un vrai mathématicien (je n'en suis pas un) spécialiste de la théorie des nombres. Déjà, le simple fait que cela génère une suite de nombre premiers qui n'est pas dans l'OEIS, c'est en soi intéressant.

[Malefix]

J'ai posté la conjecture sur mathoverflow : https://mathoverflow.net/questions/5...-prime-numbers

[MissJenny]

j'ai cherché dans le livre de Richard Guy (qui recense les problèmes ouverts en théorie des nombres) ce qu'il en disait. Ce qu'il y a de plus proche est une question posée par Erdös : si je note s au lieu de sigma, il considère la fonction n -> s(n) -1 et se demande si en itérant cette fonction on tombe toujours sur un nombre premier, ou bien si la suite grandit sans limite. Il y a d'autres problèmes autour de la somme des diviseurs (sigma) mais sigma2 ne semble pas avoir beaucoup attiré l'attention des mathématiciens.

[jacknicklaus]

J'ai poussé jusque 200000 sans trouver de contre exemple. cela prends 9 minutes, à l'ide d'un script basé sur la librairie de mathématiques des grands nombre GNU-GMP.

pour le fun : le cas N = 46250 demande un temps de calcul tout à fait énorme par rapport aux précédents et suivants. Pourquoi ? Je n'ai pas encore investigué.

[jacknicklaus]

4h 48 de calcul cette nuit pour atteindre N = 1000000. Aucun contre-exemple.

[ThM55]

Bravo, Jackniklaus! Et aussi félicitations à Malefix pour avoir formulé cette conjecture.

Pour 46250, on a .

Il a donc beaucoup de diviseurs. On peut simplifier comme suit. Sigma_2 est multiplicative (la fonction du produit de deux nombres premiers entre eux est le produit des fonctions) et a une forme simple pour les puissances de nombres premiers:

. Si est la décomposition en facteurs premiers, on a



(pas besoin donc d'énumérer les diviseurs et de sommer leurs carrés). On peut aussi remplacer les sommes par la formule classique de somme des progressions géométriques.

J'ai un peu cherché sur cette base pour une preuve, mais je pense que cela dépasse mes compétences.

[ThM55]

Il y a un commentaire sur la discussion mathoverflow, il donne peut-être un début d'explication: il y a peu de nombres composés n tels que soit un carré, une suite dans l'OEIS les énumère: https://oeis.org/A318169 . C'est ce que j'avais essayé de faire au début, avec une malencontreuse erreur de distraction. Comme cette propriété est évidemment partagée par tous les premiers, il est fort probable (certain?) que quand on tombe dessus on obtienne un nombre premier. Cela pourrait expliquer pourquoi un contre-exemple, s'il existe, doit être très grand, peut-être hors de portée du calcul, car il faut que l'un des nombres de la suite soit lui-même de la forme . La conjecture revient à démontrer que les deux suites sont disjointes ou, pour la réfuter, qu'elles ont un élément en commun.

[ThM55]

Cette remarque pourrait s'appliquer à de nombreuses suites, et cela pourrait remettre en perspective la conjecture: ainsi, je pourrais remplacer la suite par une autre, prise ou pas dans l'OEIS, une suite pas trop dense et qui croît assez vite, et puis lui appliquer . Il est probable que lorsque le résultat est un carré, ce soit celui d'un nombre premier, car il y a peu de chance que la suite choisie intersecte A318169.

[ThM55]

Autrement dit, appliquer la fonction et demander un carré crée un filtre qui fera très probablement tomber sur un premier, sauf dans de rares cas (ou jamais?). Pour le voir concrètement on peut calculer les pour n de 1 à N (à déterminer) et si aucun n'est dans la suite A318169 (6, 40, 136, 2696, 3352, 46976, 223736, 5509736, 1915798072), il n'existe pas de contre exemple inférieur à N. Pour déterminer N, on doit remarquer est que la suite des sigma_2 n'est pas strictement monotone mais elle est minorée par une suite croissante.

En somme, appliquer à une suite pas trop dense et croissante et demander un carré, cela donnera très certainement un carré de nombre premier. Cela me fait un peu penser à des tours de mentalistes qui arrivent à vous faire penser à quelque chose de précis.

[ThM55]

Pour ces raisons, notamment la croissance très rapide de la suite A318169, je ne crois pas trop à la possibilité de trouver un contre-exemple par le calcul. On pourrait essayer en "visant" un intervalle autour d'une des valeurs données dans https://oeis.org/A318169, qu'il faudrait étendre par quelques termes, et en "inversant" la fonction . Or la fonction elle-même n'est pas si simple; elle est croissante, minorée par une suite croissante, mais pas monotone et a de grandes fluctuations (voir le graphe: https://oeis.org/A001157/graph). En l'inversant autour d'une très grande valeur, on risque de devoir explorer un intervalle gigantesque, sans doute impossible.

Mais j'ai décidé d'arrêter là pour ce sujet car je crois que la réponse publiée sur mathoverflow est suffisante pour expliquer largement la constatation. Pour le reste, je peux continuer à vivre sereinement avec cette incertitude.

[jacknicklaus]

[...] je ne crois pas trop à la possibilité de trouver un contre-exemple par le calcul.[...] Mais j'ai décidé d'arrêter là pour ce sujet [...]

J'abonde en ce sens; Pour ma part, grâce aux idées de ThM55 au post#22, j'ai pu optimiser mon script et tester 10.000.000 de nombres en 1h10 environ, soit 2300 nombres par seconde en moyenne. Et aucun contre-exemple naturellement...

[MissJenny]

4h 48 de calcul cette nuit pour atteindre N = 1000000. Aucun contre-exemple.

quelle est la répartition entre carrés et non carrés?

[MissJenny]

elle est croissante, minorée par une suite croissante, mais pas monotone

c'est contradictoire

[jacknicklaus]

quelle est la répartition entre carrés et non carrés?

3% de carrés, environ.