Test de primalité

JRManda · February 2020

Bonjour chers tous
Dans des travaux de recherche que je mène actuellement sur la suite généralisée de Collatz ou problème $"qx+1"$, consignés dans deux articles en cours d’évaluation au Journal International de la Théorie des nombres de Bordeaux – en ce qui concerne le premier – et à la recherche de revue ou journal mathématique pour l’évaluation du second parce que le Journal estime que celui-ci conclut sur la démonstration de la suite de Syracuse, et que la nouvelle politique du journal sur le sujet entre autres, ne permettait pas de procéder à son évaluation. Les deux papiers sont intitulés ainsi qu’il suit.
1. Bornes de la longueur des cycles non triviaux du problème $'qx+1'$ - Conséquence sur la suite de Syracuse (Octobre 2019) ;
2. Convergence et divergence des trajectoires du problème $'qx+1'$ - Application à la suite de Collatz. (Février 2020).
Je mets à votre disposition en pièce jointe un test de primalité d’un type de nombres premiers qu’on convient de les appeler nombres premiers de Collatz. Ce test découle des résultats des travaux contenus dans les deux manuscrits ci-dessus. Je le mets à votre disposition pour d’une part recueillir vos avis et contributions et d’autre part vos suggestions de revues ou journaux mathématiques auxquels je pourrais transmettre le second document pour évaluation.
Cordialement.
JRManda

nodgim · February 2020

Quand on lit " d appartient à N+3 " ou " q appartient à 2N+3 ", ça ne donne pas bien envie d'essayer de comprendre le reste.....

Si tu dis, c'est une erreur de plume, tu corriges et on n'en parle plus. Sinon, il faut expliquer.

JRManda · February 2020

$d\in (\mathbb{N}+3)$ veut dire que $d$ est un entier naturel supérieur ou égal à $3$, et $q\in (2\mathbb{N}+3)$ signifie que $q$ est un entier impair supérieur ou égal à $3$.

nodgim · February 2020

Juste comme ça, pourquoi les appelles-tu "nombres premiers de Collatz" ?

Y a-t-il un rapport avec la conjecture éponyme ?

lourrran · February 2020

$\Z/n\Z$ est un corps ssi $n$ est premier... Résultat classique. Et la propriété en question en découle directement.

Wilfrid · February 2020

En lisant ce papier écrit en mars 2020 je me demande si je viens de franchir un portail temporel sans m'en apercevoir...

Ce qui serait intéressant c'est de savoir où tu veux en venir avec les nombres premiers de Collatz.

nodgim · February 2020

C'est un peu maladroit d'appeler " nombres premiers de Collatz " ces nombres que tu décris.

Depuis Fermat, on sait que a^(p-1) = 1 [p] si a premier avec p. Si tu choisis pour " a " la valeur (p+1)/2, ça rentre bien dans le cadre de Fermat, car (p+1) / 2 est premier avec p (si p > 3).

Après, tu te poses la question de savoir si ça tombe à 1 seulement à p-1, ou bien avant, pour un diviseur de p-1. Là, on ne peut pas le deviner à l'avance, il faut le calculer.

Fin de partie · February 2020

JRManda a écrit:

$d\in (\mathbb{N}+3)$ veut dire que $d$ est un entier naturel supérieur ou égal à $3$.

$d\geq 3$ c'était pas assez bien pour toi? :-D

PS:
C'est une constante dans le shtam, la pédanterie mathématique qui fait utiliser des assemblages de symboles qui rendent pénible la lecture , voire incompréhensible, sans rien apporter de plus.

Collag3n · February 2020

Pour sa défense, Tao utilise le même genre de notation, notamment dans sa dernière publication sur Collatz.

nodgim · February 2020

L'ensemble N+3 = l'ensemble N, non ?

Même si Tao écrit ça, c'est une c....

lourrran · February 2020

$N+3$, ce n'est pas $N$ union {3}, c'est {x+3, x appartenant à $N$} ; c'est donc $N$ privé de 0,1 et 2.

raoul.S · February 2020

Finalement tous les commentaires critiques concernant les notations $\mathbb{N}+3$ et $2\mathbb{N}+3$ de JRManda pour aboutir à quoi ... ?

Et bien que ces notations sont correctes...:)o

lourrran · February 2020

La ""découverte"" a-t-elle un intérêt ? Non. C'est un test de primalité qui permet de dire : tel nombre est premier ... mais qui laisse passer certains nombres premiers. Et c'est un test pas efficace du tout. Le test le plus basique nécessite $\sqrt{n}$ divisions, celui-ci en nécessite $n$

La ""découverte"" est-elle une découverte ? Non. C'est le genre de choses qu'on pouvait faire en exercice au lycée il y a une quarantaine d'années.

On peut aussi voir ceci comme une nouvelle suite. Il y a les nombres premiers, et il y a désormais les nombres premiers de JRManda ; Cette suite de nombres a-t-elle un intérêt ? bof.

Allez, je vais moi aussi donner mon nom à une série de nombres :
On s'intéresse aux nombres $n$ qui sont premiers, mais tels que ni $n-2$ ni $n+2$ ne soient premiers.
Les premiers termes de cette suite sont donc (2, 23, 37, 47, 53, 67, 79, ...)
Et je décide de nommer cette suite : les nombres premiers de Lourrran.

Dom · February 2020

Et que penser des termes de la suite des nombres premiers de Lourrram dont l’indice est un nombre premier de JRManda ?

raoul.S · February 2020

Hasard ou coïncidence ce sont les nombres premiers de raoul.S.

Dom · February 2020

C’étaient les miens mais seulement pour $p \in \mathbb N + \sqrt{2019^2}$.

Ça alors !

Fin de partie · February 2020

Les nombres premiers FDP sont les nombres premiers qui sont uniquement divisibles par $1$ et par eux-mêmes. X:-(

JRManda · February 2020

Cher Nodgim,

Ces nombres ont bel et bien un lien avec le processus généralisé de Collatz de paramètre $q>1$, $q$ impair. En effet, l'étude prouve que, sauf peut-être le premier terme $N_{0}$, les valeurs impaires prises par le processus généralisé de Collatz appartiennent aux classe d'équivalence des éléments quotients d'un sous-groupe particulier $S_{2q}$ du groupe $(\mathbb{Z}/2q\mathbb{Z}^{*}, \times )$ des éléments inversibles pour la multiplication de l'anneau $(\mathbb{Z}/2q\mathbb{Z}, +, \times)$. Le lien est que $n_{0}=\min \{n\in \mathbb{N}^{*} \mid s_{n}=1\}$ est l'ordre de ce sous-groupe $S_{2q}$.

JRManda · February 2020

Exemple : Pour le processus de Collatz de paramètre $q=7$, sauf peut-être le premier terme impair $N_{0}$, tous les autres termes impairs de la trajectoire de tout vol impair sont congru à 1, 9 et 11 modulo 14. Par conséquent, le sous-groupe $S_{2q}=\{1, 9, 11\}$ et est d'ordre $n_{0}=3$. Et donc si on applique le test à 7, on aura $s_{3}=1$.

nodgim · February 2020

Je vois.

Appliquées à l'algorithme de Collatz q = 3, les valeurs modulo 6 (si j'ai bien compris ) donnent 1 ou 5, distribuées un peu au hasard selon le nombre de départ, ça n'aide pas beaucoup pour savoir s'il existe une boucle ou pas.

JRManda · February 2020

De l’intérêt de ce test, comme éléments de réponse à lourrran, je dirai ce qui suit :

D’abord, en complément du test de Lucas-Lehmer, ce test permet d’obtenir un type de nombres premiers autres que les nombres de Mersenne ;
Ensuite, ce test peut contribuer à améliorer le record de décomposition en produit de facteurs premiers des nombres de Mersenne $M_{p}=2^{p}-1$ avec $p$ premier et $M_{p}$ composé. En effet, comme $M_{p}$ composé, il se décompose sous la forme de produit de $k$ facteurs premiers, soit $M_{p}=m_{1}\times m_{2}\times \cdots \times m_{k}$, $k\in \left(\mathbb{N}+2\right)$. Et ici, le test se fera sur les $m_{j}$, $j=1, 2, \cdots , k$, qui sont de taille plus petite à manipuler en termes de ressources de calculateurs. Aussi, on peut trouver les facteurs premiers de $M_{p}$ même si sa valeur déborde la mémoire de l’outil de calcul utilisé, pourvu que chaque facteur premier $m_{j}$ et son carré $ m_{j}^{2}$ reste dans la plage de mémoire, puisque la suite $(s_{n})_{n\in \mathbb{N}^{*}}$ est bornée, $1\leqslant s_{n} \leqslant q^{2}$, $\forall n\in \mathbb{N}^{*}$.
Enfin, ce test est très simple et peut se faire à l’aide des quatre opérations élémentaires $(+, -, \div, \times)$.

Malgré sa simplicité apparente, j'avoue avec beaucoup d'humilité qu'il y a eu un travail scientifique, à quelque niveau que ce soit, en amont de ce test. Mais hélas, tout ce que l'homme fait est perfectible.

nodgim · February 2020

On peut en effet trouver des facteurs premiers de nombres de Mersenne avec cette méthode. Il me semble qu'il est nécessaire de tester les nombres premiers dans l'ordre, un par un. Et pour la primalité d'un Mersenne, il suffit que le test systématique dépasse la moitié du nombre premier visé. Il me semble que c'est plus rapide que la méthode actuelle. C'est de l'ordre du milliard de nombres premiers à tester, ce qui est très abordable avec les moyens actuels.

J'ai eu un peu de mal à comprendre la justification, alors que c'est tout bête : (q+1)/2 = 1/2 [q]
et donc pour 1/2^n = 1 [q], c'est 2^n = 1 [q]

nodgim · February 2020

Je me suis planté dans le message précédent. On ne peut pas vérifier la primalité d'un Mersenne avec la méthode proposée ici. Un diviseur de q-1 pourrait être très petit vis à vis de q. En revanche, la méthode permet d'éliminer plus rapidement que la méthode classique des Mersenne composés, à condition d'en tenir un registre. Elle peut donc être utile tout de même.

JRManda · February 2020

Bonjour chers tous,

Je vous tiens ci-joint le document avec la date actualisée.

Merci pour vos contributions.

JRManda

JRManda · February 2020

Bonjour chers tous,

Je remarque à juste titre que nodgim a raison de souligner que le test permet d’éliminer très rapidement le cas des nombres de Mersenne $M_{p}$ composés avec $p$, premier et qu'il restait un travail d'organisation à faire. Par conséquent, en regardant de plus près, on montre que la méthode permet de tester la primalité ou la non primalité de tout nombre de Mersenne $M_{p}$ avec $p$ premier et $p\geqslant 11$. A la seule condition que $q_{max}^{2}=\left(2^{\left \lfloor \frac{p}{2} \right \rfloor}-3\right)^{2}$ tienne dans la mémoire de l’outil de calcul.
La procédure Maple si jointe, avec paramètre d’entrée le nombre $p$ premier supérieur ou égal à 11 permet de dire si $M_{p}$ est premier (l’ensemble de ses facteurs premiers est vide) ou composé (les facteurs premiers inférieurs à $q_{max}=\sqrt M_{p}\simeq \left(2^{\left \lfloor \frac{p}{2} \right \rfloor}-3\right)$ sont alors affichés).

Remarque : On montre que si le nombre de Mersenne $M_{p}$ avec $p$ premier est composé, $M_{p}=m_{1}\times m_{2}\times \cdots \times m_{k}$, $k\geqslant 2$, alors :

Les $m_{j}$, $1\leqslant j\leqslant k$ sont tous des facteurs premiers d'ordre 1 ;
$\forall j=1, 2, \cdots k$, $m_{j}\geqslant (2p+1)$ ;
Un autre nombre de Mersenne premier ne peut pas être facteur premier de $M_{p}=2^{p}-1$ avec $p$ premier ;
Un nombre premier de la forme $N_{d}=2^{d}+1$, $d\in \N$ ne peut pas être un facteur premier de $M_{p}=2^{p}-1$ avec $p$ premier.

JRManda

Test de primalité

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 41