Z/nZ;algorithme permettant de construire la suite des nombres premiers

Antho17 · 17-03-2021 14:13:35

Bonjour,

J'ai décidé de me tourner vers vous concernant une propriété que j'ai remarqué il y a plusieurs mois déjà.
Je m'intéresse à l'ensemble Z/nZ ( n entier non nul ) et à ses inversibles.
Je tiens à préciser que je n'ai plus vraiment fait de maths depuis 7-8 ans, veuillez pardonner mes approximations...

J'ai remarqué que si l'on pose n=dd' avec PGCD(d,d')=1 (ce qui est toujours faisable), alors les nombres n et r sont premiers entre eux si et seulement si r est de la forme : r=k'd+d'k avec PGCD(d,k)=PGCD(d',k')=1.
Il se crée alors des symétries autour des diviseurs de n.
Par exemple, sur le nombre $\n=30=2*3*5$, je peux écrire que les nombres premiers avec 30 sont de la forme :

15k+2k' avec PGCD(2,k)=PGCD(15,k')=1 ou encore 10k+3k' avec PGCD(3,k)=PGCD(10,k')=1 ou encore 6k+5k' avec PGCD(5,k)=PGCD(6,k')=1.
Peu importe la forme que je choisis, je récupère tous les nombres premiers avec 30 de cette façon. On note $\phi$ l'indicatrice d'Euler qui détermine le nombre de nombres premiers avec n entre 1 et n.

Si on se place sur [0,30], on a une symétrie évidente en 15 ( 15+2k premier avec 30 implique 15-2k premier avec 30 ) : on récupère tous les nombres premiers avec 30 avec un axe de symétrie en 15.
(en fait on a $\phi$(2)=1 et $\phi$(15)=8=$\phi$(30) . Donc on a $\phi(2)*\phi(15)=1*8=\phi(30)$ nombres premiers avec 30)
Mais on a aussi 2 symétries en utilisant la forme 10k+3k' : une en 10 (k=1 premier avec 3) et une en 20 (k=2 premier avec 3).
En utilisant la symétrie en 10 je vais récupérer la moitié des nombres premiers avec 30 ( et donc sur [0,30] j'en récupère 4 qui sont 1,7,13,19) et en 20 j'ai l'autre moitié (11,17,23,29)).
Je peux faire pareil en utilisant la forme 5k+6k' qui me donnera 4 axes dont chacun permet de récupérer 1/4 des nombres premiers avec 30 ( et donc sur [0,30] chaque axe me donne 2 nombres premiers avec 30).

Si on pose $n=p_1^{\alpha_1} * ....* p_k^{\alpha_k}$ (avec $\alpha_i $ entier alors on peut déduire de la formule r=k'd+d'k que $r=n*\sum_{i=1}^k k_i/p_i^{\alpha_i}$
avec PGCD$(k_i,p_i^{\alpha_i})=1$.

On peut aussi écrire quelque chose de semblable avec les nombres qui ne sont pas premiers avec n (la somme est la même mais on dit qu'il existe au moins un $k_i$ tel que PGCD$(k_i,p_i^{\alpha_i})$ soit différent de 1).
De cette façon, j'ai écris tous les nombres premiers ou non avec n et je définis 2 ensembles qui sont disjoints (l'un ou PGCD$(k_i,p_i^{\alpha_i})=1$ pour tout i allant de 1 à k, donc l'ensemble des premiers avec n, et l'autre ou il existe au moins un $k_i$ tel que PGCD$(k_i,p_i^{\alpha_i})$ soit différent de 1, l'ensemble des nombres qui ne sont pas premiers avec n.)

On peut aussi en déduire un algorithme assez simple nous fournissant la liste des nombres premiers :

on pose $n=2*3*5*7*...*p_j$. Le plus petit entier premier avec n qui est strictement supérieur à 1 est $p_{j+1}$. D'après ma formule, je peux dire que tous les nombres premiers avec n sont atteints en n/2+2q avec q premier avec n/2. Donc $p_{j+1}=n/2+2q$. ($p_{j+1}$ est un nombre premier avec n). Reste à déterminer q, q premier avec n/2. Je m'intéresse au nombre $b=(1-n/2)/2$. b est premier avec n/2 car :
$n/2 + 2*((1-n/2)/2)=n/2+1-n/2=1$ ( donc d'après Bézout b et n/2 sont premiers entre eux).
Maintenant l'application f qui va de l'ensemble des nombres premiers avec n/2 dans l'ensemble des nombres premiers avec n et qui à q associe f(q)=n/2+2q est bijective (et elle strictement croissante ) et on a f(b)=1. Donc le plus petit entier q' premier avec n/2, avec q' >b, nous donnera le plus petit entier p premier avec n, avec p>f(b)=1, donc $p_{j+1}$. On peut peut donc écrire $p_{j+1}=n/2+2q$ avec
q = min { r premier avec n/2, r >b }.

Concrètement ( sur 3 exemples car on y voit de plus en plus clair ) :

n=$p_1$=2. Je cherche $b=(1-n/2)/2=(1-1)/2=0$. ( on a bien $n/2+2b=1+2*0=1$ ). Maintenant je cherche le plus petit entier q supérieur à b=0 qui est premier avec n/2=1. Je teste pour q=1 : 1 est premier avec n/2=1, donc $p_2=n/2+2q=1+2*1=3$.

J'ai trouvé $p_2$. Maintenant je pose $n=p_1 * p_2 =2*3=6$ et je recommence le même processus.
n=6, $b=(1-n/2)/2=(1-3)/2=-1$. ( on a bien $n/2+2b=3+2*(-1)=1$). Je cherche le plus petit entier q supérieur à b=-1 qui est premier avec n/2=3.
Je teste q=0 : 0 n'est pas premier avec 3 ( 3/0 et 3/3). Donc je teste q=1 : 1 est premier avec 3 donc $p_3=n/2+2*q=3+2*1=5$.

J'ai trouvé $p_3$. Maintenant je pose $n=p_1 * p_2 * p_3 =2*3*5=30$ et je recommence le même processus.
n=30, $b=(1-n/2)/2=(1-15)/2=-7$. ( on a bien $n/2+2b=15+2*(-7)=1$). Je cherche le plus petit entier q supérieur à b=-7 qui est premier avec n/2=15.
Je teste q=-6 : -6 n'est pas premier avec 15 ( 3/-6 et 3/15). Donc je teste q=-5 : -5 n'est pas premier avec 15 ( 5/-5 et 5/15). Donc je teste q=-4 : -4 est premier avec 15 donc $p_4=n/2+2*q=15+2*(-4)=7$.

Et ainsi de suite.
Voila, je suis resté un peu perplexe quand j'ai remarqué ces propriétés, pour moi (c'est un avis personnel), c'est un résultat assez important (je me suis toujours demandé si on pouvait exprimer $p_{j+1}$ en fonction des j précédents nombres premiers, et j'ai trouvé ma réponse la dedans.)

Alors pourquoi je n'ai jamais entendu parler de ces propriétés précédemment ? Est-ce spécialisé et donc on en parle pas dans un cursus universitaire classique ? Ou alors c'est inutile donc on n'en parle pas ? (ca me permet quand même d'exprimer $p_{j+1}$, je ne pense pas que ce soit si inutile que ca ...) ou alors personne n'a remarqué cela auparavant, dans ce cas la je serai vraiment chanceux car c'est assez visible selon moi.

Je suis nouveau sur Bibmath (je me suis inscris pour me remettre à niveau en mathématiques et utiliser la banque d'exercices/sujets de Capes afin de préparer ce concours pour l'année prochaine). J'ai cependant par moments parcourus diverses discussions et j'ai pu me rendre compte que certains d'entre vous avaient un excellent niveau en mathématiques ainsi qu'une grande culture. Je ne cherche pas à avoir la démonstration de ces résultats (sauf erreur de ma part je les ai déjà prouvés).

Peut-être pourrez vous m'indiquer quelques liens/sites sur lesquels je pourrais en apprendre plus concernant ce que j'ai remarqué. J'ai déjà cherché sur le net (j'ai essayé de retrouver mon résultat dans les cours d'arithmétique, algèbre mais sans succès). Peut-être que je n'ai fait que reformuler des résultats déjà établis sans m'en rendre compte, c'est possible mais dans ce cas la je ne m'en suis pas aperçu.
J'espère que vous pourrez m'éclairer sur ce sujet.

Merci d'avance de m'avoir lu et bonne journée.

Dernière modification par Antho17 (29-03-2021 14:42:05)

Bernard-maths · 17-03-2021 19:49:49

Bonsoir !

c'est intéressant, mais pour moi c'est un peu loin ... Ne faudrait-il pas déplacer cette conversation, en "Entraide Supérieur" ?

Qu'en pense Yoshi ???

Cordialement, Bernard-maths

Dernière modification par Bernard-maths (17-03-2021 19:59:56)

yoshi · 17-03-2021 20:45:00

Re,

J'y ai pensé, mais ce n'est pas vraiment une demande d'entraide, j'ai donc trouvé que c'était bien placé en "Café Mathématique"...
@Antho17 :

Je m'excuse d'avance mais je ne maitrise pas Latex

Bin, pour ce que tu as écrit, 5 min de lecture de ce document : Code Latex suffisaient, sinon à quoi sert que "Ducroz" se soit décarcassé pour vous offrir une "mise du pied à l'étrier" ?

@+

Antho17 · 18-03-2021 09:52:44

Bonjour,

En effet pour ce qui de Latex j'ai pas vraiment cherché... Je regarderais en début d'après midi si je peux pas éditer le message pour le rendre plus lisible (je suis pas très à l'aise avec les forums, mais je pense pouvoir quand même me débrouiller).

Merci pour vos réponses et pour le lien Latex. Bonne journée

Dernière modification par Antho17 (18-03-2021 16:22:52)

LEG · 19-03-2021 09:02:38

Bonjour

Peut être que tu devrais aussi regarder de quelle forme sont les nombres premier $p'\geqslant{7}$ et tu constatera qu'il sont tous de la forme $30k + i $ avec K entier non nul et $i\in(1,7,11,13,17,19,23,29)$ 8 familles de nombres premiers en progression arithmétique de raison 30 et de premier terme $i$ ; on supprime ainsi 2 , 3 et 5 et leurs multiples, qui n'ont plus aucune utilité.

Si un entier $A$ non nul, tel que $A\leqslant{30}$ n'est pas divisible par $P\leqslant\sqrt{30}$ alors il est premier $p'$ Ératosthène, ce qui donne : $7,11,13,17,19,23,29.$

L'algorithme permettant d'extraire tous les nombres premiers de $7\: à\: n$ se trouve sur le forum programmation, ainsi que l'algorithme permettant d'extraire les nombres premiers $q\in{[n ; 2n]}$ de ces 8 familles en criblant toujours jusqu'à la limite $n$ sans avoir besoin de cribler jusqu'à $2n$ "en utilisant les congruences"

Si tu t'intéresses à ces algorithmes ... je pense que @Yoshi pourras t'indiquer les liens.

Dernière modification par LEG (19-03-2021 09:17:31)

Antho17 · 19-03-2021 11:24:33

Bonjour,

J'ai un petit soucis quand j'écris que $r=n*\sum_{i=1}^k k_i/p_i^{\alpha_i}$ , je pense qu'il faut préciser un peu plus ( ce que je veux dire c'est que si n=42 par exemple, alors les nombres premiers avec n sont de la forme $21k_1 +14k_2+6k_4$ avec PGCD($k_i,p_i$)=1 du coup si $\alpha_i=0$ ca crée un soucis dans ma somme). N'hésitez pas à me signaler mes erreurs....

Pour LEG : je ne comprends pas trop, si je cherche à dire si mes nombres premiers avec 30 sont premiers ou non pour moi je peux dire qu'ils le sont tant qu'ils sont strictement inférieurs à $p_4^2$ ( et strictement supérieur à 1). Si on exclut 49, on peut dire qu'ils le sont jusqu'au prochain terme composé qui est $7*11=77$ ( 77 est premier avec 30 mais n'est pas premier).
Donc quand tu écris que les nombres de la forme 30k+i avec i premier avec 30 sont premiers c'est pas le cas ($30*1+19=49=7*7$). Ils sont premiers avec 30. J'ai peut être mal compris ce que tu essayais de me dire, je suis pas très réveillé ce matin.
EDIT : En effet, je crois que j'ai mal compris et mal interpréter tes propos. En gros l'idée si je comprends bien, c'est que tous les nombres premiers sont de la forme 2k+k' avec k' et 2 premiers entre eux, puis si je continue ils sont de la forme $(2*3)k+k'$ avec k' premier avec 6 et ainsi de suite en fait , donc de la forme 30k+i avec i premier avec 30 mais on peut continuer et dire qu'ils sont de la forme 210k+i, 2310k+i etc et du coup on supprime des diviseurs à chaque fois qu'on multiplie par un nombre premier.Je sais pas trop si c'est ce que tu voulais me faire comprendre. Pour ce qui est du crible d'Erathostène, c'est le sentiment que j'ai eu, c'est une formalisation du crible en fait.

En fait oui je m'intéresse à ces algorithmes, après je ne sais pas si je suis en mesure de les comprendre. Ce qui m'intéresse vraiment c'est plutôt les symétries qui se créent quand on étudie les nombres premiers avec n et les diviseurs de n. Je pense que je dois pouvoir retrouver cela quelque part sur internet mais je n'ai pas trouvé pour l'instant ( ou alors j'ai pas vu..).

Merci pour ton message.

Dernière modification par Antho17 (19-03-2021 11:39:34)

LEG · 19-03-2021 12:13:26

Re
Je pense que tu n'as pas compris ce que j'ai voulu te dire

On ne s'occupe pas de regarder les entiers premiers entre eux y compris si $i$ tel que défini, est premier avec 30k c'est une évidence..
Mais de s'intéresser aux nombres premiers de la forme $30k + i$ , car refaire le crible d'Ératosthène ou le formaliser d'une façon plus compliquée n'a pas d'intérêt, pour construire la suite des nombres premiers , qui est le but de ton sujet...

Comprendre l'algorithme que j'ai fait et qui a été programmé par Yoshi n'est pas très difficile de comprendre son principe qu'i est celui d'Ératosthène , mais modulo 30

En définitive on a besoin uniquement des 8 nombres premiers $p$ appartenant à $7;31$ pour extraire la suite des nombres premiers inférieur à une limite n fixée.

selon deux méthodes
A) soit on barre les multiples de p jusqu'à la limite $n$ en utilisant les premiers inférieur à racine de $n$
B) soit on utilise les congruences , et on barre les entiers A inférieur à racine de $n$ est congru à 2n modulo P, mais avec P inférieur à racine de 2n...et on construit au fur et à mesure la suite des nombres premiers...

Bon courage

Antho17 · 21-03-2021 12:09:05

Bonjour,

Je m'excuse si j'ai mal compris. Je vais essayer de retrouver le post ou tu expliques ton algorithme et voir si je peux le comprendre.
Je m'intéresse à la façon dont on peut déterminer les nombres premiers jusqu'à un entier n déterminé en effet et j'ai pu voir
qu'il existait déjà plusieurs méthodes permettant d'y parvenir (j'avais lu une discussion sur ce forum il me semble ou on y parvenait en utilisant un algorithme qui malheureusement était un peu trop compliqué à comprendre pour moi, et qui n'avait qu'un intérêt théorique apparemment).

Mais c'est surtout les symétries qu'on peut observer qui occupent mon attention. On peut déduire certaines propriétés sur les nombres à partir de ces axes et je pense qu'ils ont surement d'autres propriétés, relations entre eux que j'ignore.

Bonne journée.

Dernière modification par Antho17 (21-03-2021 12:10:44)

yoshi · 21-03-2021 12:50:09

Bonjour,

@LEG : Fais-tu allusion à cette discussion ?

@+

LEG · 21-03-2021 12:50:29

Bonjour

tu peux déjà regarder sur ce lien: forum programmation: http://www.bibmath.net/forums/viewtopic.php?id=13408

tu as trois programmes d'algorithme 2 en C++ et un en python qui indique directement les couples de nombres premiers p+q qui décomposent 2n en somme de deux premiers.

pour ce qui est de l'explication de l'algorithme de Goldbach , du crible qui utilise les congruences suivant le principe d'Ératosthène; tu as ce fichier qui explique très bien le décalage d'un rang des congruences sur leur successeurs, lorsque la limite n augmente de 15.

que ce soit pour la suite des entiers non nuls en partant de 1 ; ou des 8 suite arithmétique de raison 30 et de premier terme $i\in(1,7,11,13,17,19,23,29)$

https://www.cjoint.com/c/KCrizkRjovJ

ou encore :

https://www.cjoint.com/c/KCpkiO5Fs54
où dans les illustrations, les nombres premiers $p'$ sont représenté par des 1 et leurs multiples par des 0 en ce qui concerne le ECrible d'Ératosthène
pour le Gcrible de Goldbach les entiers $A\not\equiv{2n}[P]$ avec $P\leqslant\sqrt{2n}$ sont représentés par des $1$ et les $A$ congruent à $P$ représentés par des 0

tu t'apercevra alors, que les nombres premiers $q$ appartenant à $[n;2n]$ dépendent de la congruence des entiers $A$ de 1 à n,
autrement dit, ils ont pour antécédent un entier $A$ non congrus à 2n modulo $P$.

@Yoshi à quelle discussion tu fais référence ... j'espère que tu te portes bien...@+

Dernière modification par LEG (21-03-2021 13:06:58)

yoshi · 21-03-2021 13:23:13

Re,

j'avais zappé...
Il vaudrait mieux qu'il commence par là :

http://www.bibmath.net/forums/viewtopic.php?id=10154

ou

http://www.bibmath.net/forums/viewtopic.php?id=12292

@+

LEG · 21-03-2021 14:15:46

re Yoshi
oui effectivement tu as raison, d'autant que dans le deuxième lien il y a les deux programmes en python qui ont servis à unifier le troisième crible_EG_2N mod 30 avec les explications et qui ont été retranscrit en C++ qui ne lui apporteront rien à part des résultats...

Antho17 · 22-03-2021 11:33:55

Bonjour,

J'ai regardé les différents messages que vous avez posté concernant l'algorithme de LEG. Mes connaissances en informatique sont vraiment basiques ca risque d'être long pour moi de comprendre...

En revanche, j'ai ouvert ce fichier https://www.cjoint.com/c/KCrizkRjovJ tout à l'heure. J'ai l'impression (je l'ai lu rapidement sans rentrer dedans) que tu expliques clairement l'idée dedans. Je pense que je vais commencer par là pour avoir une meilleure compréhension globale des algorithmes que vous utilisez. Mais pour moi c'est compliqué, ca risque de me prendre un peu de temps pour comprendre si j'y parviens (et je ne peux y consacrer que quelques heures par jour) mais il y a des choses qui m'intéressent beaucoup dedans, donc je vais faire des efforts et essayer de mieux cerner tout cela.

Merci pour vos liens, bonne journée.

Omhaf · 22-03-2021 12:22:17

Bonjour
en Novembre dernier j'avais posté un algorithme simple pour donner la suite des nombres premiers sous post intitulé:
Nouvelle logique pour calculer les nombres premiers
La méthode s'est avérée juste et yoshi et LEG y avaient participé
Si cela intéresse notre ami Antho17 .....

Dernière modification par Omhaf (22-03-2021 12:23:00)

LEG · 22-03-2021 15:27:57

Bonjour

@Antho17 tu as raison avec ce fichier que tu regardes il te permet effectivement de comprendre l'algorithme de Goldbach utilisant les congruences

tout d'abord avec les entiers A impair et non nul, si tu veux te passer des A pairs dans ce cas tu parts directement de la suite

[1.3.5.7........61] et tu calcule le reste R de 2n = 2*61 par P > 2 premier et inférieur à racine de 2n et non de n , puisque tu vas calculer les entiers A congru à 2n (mod P) de 1 à 61, que tu marqueras d'un 0; en partant du reste R puis par pas de P ("principe Ératosthène") ; ce qui impliquera obligatoirement les nombres premiers q appartenant à [n ; 2n] .

Un $A\not\equiv{2n}[P]$ implique $B = q $ premier, tel que $2n - A = B = q$ et inversement si :
$A\equiv{2n}[P]$ implique $B\neq{q}$ premier, tel que $2n - A = B = C$ nombre Composé multiple de P

Une fois le principe compris, tu passes directement aux 8 Familles : fam (i) avec $i\in(1,7,11,13,17,19,23,29)$ famille d'entiers A en progression arithmétique de raison 30 et de premier terme (i). ce qui te permet de ne travailler qu'avec une seule famille de nombres premiers de la forme 30k + (i)
en travaillant avec une limite N = 15k par exemple 300 , donc 2N = 600 = 30k

pour les programmes @Yoshi t'expliquera au cas où tu as des questions...moi je ne suis pas Mathématicien...

Tu devrais t"en sortir sans trop de difficulté , c'est quand même de l'arithmétique élémentaire ...

Bon courage

Dernière modification par LEG (22-03-2021 15:41:41)

Antho17 · 24-03-2021 14:12:36

Bonjour,

J'ai lu ton document, bon je suis loin de tout comprendre mais je pense saisir l'idée. Par contre j'ai du mal à te suivre par moments.
Je pense que je reviendrai peut-être dessus (surement même), il y a quelques points qui ont retenu mon attention et qui pourront m'être utile si je décide de poursuivre mes réflexions sur les nombres premiers (et premiers entre eux).

J'y ai appris certaines choses que je ne connaissais pas, merci pour cela. C'est marrant mais je raisonne vraiment différemment de toi (et surement de la plupart des gens qui s'intéressent aux cribles), et encore plus depuis que j'ai remarqué ces propriétés (ca a un peu modifié ma façon de voir les nombres, maintenant je vois des symétries partout ...).
Si vous avez déjà entendu parler de la propriété que j'énonce dans le post initial et que vous avez des liens de sites sur lesquels ils en parlent, je suis preneur (en fait c'est surtout ca que je recherche).

Pour Omhaf, j'ai regardé ta discussion sur ton algo, j'ai pas trop compris (j'ai un peu de mal avec la programmation, en fait il me faut expérimenter "manuellement" sur les nombres pour que je commence à voir les propriétés qui s'en dégagent et ensuite comprendre).
J'ai vu aussi que tu remarquais souvent des propriétés (beaucoup de post), tu as beaucoup d'imagination !

Bonne journée à tous.

LEG · 24-03-2021 15:29:37

Bonjour

il est clair que moi je raisonne en fonction de mes connaissances sur la répartition des nombres premiers dans des suites arithmétique de raison 30 .

Et non en tant que Mathématicien, car je ne le suis pas du tout....
je n'ai jamais étudié les bases élémentaires des mathématiques , algèbre et compagnie...

Pour cela, je pense que si tu poses des questions mathématiques , Yoshi te répondra...

Sur mes deux cribles aucun souci.... pour te répondre .
Concernant l'imagination c'est probablement qu'elle n'est pas bridée par les formules Mathématique et mon absence de connaissance Mathématique , donc je procède comme quelqu'un qui pour comprendre est obligé de décortiquer au maximum les formules en nombres entiers et réels pour les comprendre. Je procède au cas par cas.
Peut être est ce la raison que mes algorithmes n'ont jamais été trouvé.. surtout celui de Goldbach qui a des propriétés très intéressantes sur la répartition des nombres premiers, notamment entre N et 2N , au lieu du postulat de Bertrand qui ne veut rien dire ou presque...

Sachant que la fonction qui donne son estimation est une conséquence directe du TNP, et non au lieu de dire : il y a au moins un nombre premier entre N et 2N ; ce qui pour moi est absurde ...

Sur la propriété que tu cites , les nombres premiers entre eux , je ne pense pas que j'aurai pu avec cela, construire mes algorithmes; Yoshi t'en diras plus et éventuellement sur des liens que tu pourras regarder.

Mais il me semble que tu t'intéresses surtout à la construction de la suite des nombres premiers ... donc comment construire le plus simplement cette ou ces suites... Or regarder les nombres premiers entre eux , ou utiliser les multiples de 2, 3 et 5.... je ne vois pas ce que cela t'apportera en plus ....?

Voici un exemple, sur la répartition des couples de nombres premiers p+q = 2N sur différentes limites N criblées et différente Famille (i) ("avec les trois algorithmes")

https://www.cjoint.com/c/KCynyRURh4p

Cordialement
@+

Antho17 · 25-03-2021 11:07:21

Bonjour,

Je suis un peu au ralenti encore ce matin... En fait, je m'intéresse à tous les nombres pas que les mutliples de 2,3 et 5 (pas que la primorielle, qui est le produit de tous les nombres premiers jusqu'à un certain rang). Si tu exécutes le petit algo que j'ai cité au nombre $2*3*13*17$ par exemple, tu verras qu'il te donnera 5 en sortie, puis tu le re-exécutes il te donnera 7 etc ; en fait, si le nombre est de la forme 2i ou i est impair, il te donnera le plus petit nombre premier qui n'apparait pas dans la décomposition de i . Ca ressemble pour moi à une sorte d'algo de complétion de base.

Après étudier la primorielle permet d'avoir certaines propriétés sur les nombres. Le nombre b tel que je le définis à des propriétés intéressantes par exemple, parce qu'il est fonction de la primorielle (je m'en suis aperçu après mon premier post en vérifiant que je ne disais pas de choses fausses, d'ailleurs si c'est le cas merci de me le signaler).

Si on considère le nombre $n_j=p_1*p_2*....*p_j$, on peut remarquer (en gardant les notations de mon premier post avec q=min{r et $(n_j)/2$ premiers entre eux, r>b} que $2(q-b)+1=p_{j+1}$ et qu'alors :

3/(b+1) ; 5/(b+2); 7/(b+3) ; 3/(b+4) etc en fait (2k+1) divise b+k si (2k+1) n'est pas une puissance de p, sinon ce sera p qui divise 2k+1 (ou p est un premier qui intervient dans la décomposition de $n_j$; bon après si $(2k+1)=9*25$ par exemple ce sera $3*5$ qui divise b+k, bon c'est pas très clair, j'espère que ca reste compréhensible). Donc tu crées un intervalle de longueur $(p_{j+1}-1)/2$ ou aucun nombre n'est premier (c'est plutot intéressant comme propriété je trouve). Tu peux même faire un peu mieux : (edit :(2k+1) divise b+k tant que b+k est strictement inférieur à q, quand on arrive à q on a le nombre premier cherché qui n'intervient pas dans la décomposition de n ; bon c'est vraiment pas très clair, il faudrait rédiger cela un peu mieux)

si 3/(b+1), alors 3/(b-2); 5/(b+2) alors 5/(b-3); 7/(b+3) alors 7/(b-4); (2k+1) divise b+k alors (2k+1) divise b-(k+1) (toujours en faisant attention aux puissances de p et produit de puissances de nombres premiers).
Donc tu crées un intervalle de longueur $p_{j+1}$ ou tu sais qu'aucun nombre (à part b et b-1) n'est premier (attention les bornes de l'intervalle sont ouvertes). Maintenant b et b-1 sont deux termes consécutifs, l'un d'eux est divisible par 2. Donc un nombre seulement n'a pas de diviseurs connus dans cet intervalle (c'est pas pour autant qu'il est premier).

Voila c'est ce genre de choses que je trouve intéressantes, ca t'apporte beaucoup d'informations sur la structure des nombres compris entre 1 et $n_j$.

Pour ton algo, je ne comprends pas pourquoi tu te limites aux ensembles de nombres de la forme 30k+i, tu peux le généraliser je pense. (sinon pourquoi choisir 30 et pas 6 ou 210 par exemple ?).
J'ai été voir sur internet après avoir lu ton document, j'ai trouvé quelque chose qui y ressemble, je te mets le lien, peut-être que tu pourras en tirer des résultats qui t'aideront/t'intéresseront pour le perfectionner, l'améliorer je sais pas: http://denise.vella.chemla.free.fr/vfalgogc.pdf

Après bravo à toi pour arriver à comprendre cela sans formation mathématique, c'est un certain tour de force en soi.

Bonne journée

Dernière modification par Antho17 (27-03-2021 14:10:17)

LEG · 25-03-2021 13:15:40

Salut Antho
je connais le lien et le travail de Denise C
c'est un travail similaire au mien ; mais elle ne travaille pas dans les suite Arithmétique de raison 30.
ce qui est beaucoup plus long et qui raccourci la limite des cribles et leur vitesse, et n'utilise pas le même principe de fonctionnement.

si je ne travail pas modulo 6, c'est que cela n'a aucun intérêt à part avoir des multiples de 5 en plus qui ne servent à rien (au début j'ai travaillé modulo 6) ni même généraliser à l'ensemble des entiers positifs ce qui n'apporte strictement rien à la répartition des nombres premiers dans une suite arithmétique de raison, puisque l'on se débarrasse des 73% des entiers naturels contenant aucun nombre premiers à part 2 , 3 et 5, lorsque l'on s'intéresse aux nombre premiers qui peut le plus peut le moins...
regarde le crible de Harald Andrés Helfgott il utilise la racine cubique de n et en cercle...il élimine d'office les multiples des nombres premiers p < 19 , ne va donc pas lui demander d'utiliser modulo 6, ou autre tous les entiers naturels ça n'a aucun sens , à part passer du temps pour extraire la suite des nombres premiers...

si tu avais compris le principe des deux cribles tu ne me poserais pas tes questions....Il me semble que l'étude des primorielles à été étudiée depuis des lustres...
Et malgré cela personne , n'a été capable de construire la variante du crible d'Ératosthène utilisant les congruences avec des propriétés remarquables sur la répartition des nombres premiers , en fonction de ce que l'on veut regarder....notamment en ce qui me concerne , pour la conjecture de Goldbach...et sur le nombre de solutions qui vérifient un entier 2n en somme de deux premiers p+q...

Mais que cela ne t'empêche pas de construire ton propre algorithme afin d'extraire la suite des nombres premiers et pourquoi pas uniquement entre N et 2N en ne criblant jusqu'à n...
Bon courage.

Dernière modification par LEG (25-03-2021 13:18:33)

Antho17 · 26-03-2021 11:51:57

Bonjour,

Merci pour tes précisions, donc en fait tu travailles avec 30 pour optimiser ton algo et ca sert à rien d'utiliser les nombres plus grands car c'est suffisamment performant avec 30. (et oui je suis loin d'avoir compris)

J'ai essayé de trouver ce dont tu me parlais concernant Harald Andrés Helfgott. Autant le dire, les premiers documents que j'ai lu m'ont refroidis (beaucoup trop compliqué, j'y comprends rien...).
Sinon je ne cherche pas vraiment à créer d'algos, disons que ce que je présente dans mon post est une application assez directe de la formule que j'avais remarqué. Je cherche juste à savoir si quelqu'un avait déjà entendu parler de cette formule (ou quelque chose d'assez similaire) et peut me guider vers des sites qui en disent plus à ce sujet car forcément j'aimerais en savoir plus.
T'arrives à comprendre ce que fait Harald Andrés Helfgott ? Wow.. moi j'ose même pas y songer. (d'ailleurs je ne connais son nom que depuis peu, depuis que je me suis mis à chercher des sites en relation avec ce que j'avais remarqué).

Merci pour ta patience.

Bonne journée,

LEG · 26-03-2021 13:45:15

Bonjour
Re: je n'ai jamais dis que je comprenait ce que fait H Helfgott et ce quelque soit son domaine ... je t'ai simplement fait allusion à son crible , dont très peu de Mathématiciens de renommés mondiale, savent comment il s'y prend...alors imagine quelqu'un qui n'a jamais appris les maths...

pour te donner un exemple sur le modulo 30 par rapport au modulo 210 par exemple dans ces deux cribles on perdrait uniquement les multiples de 7; mais il ne serait pas plus performant voir moins rapide car le programme est beaucoup plus em.... à faire et pour rien gagner.

on en a discuté dernièrement avec Yoshi lorsque je lui est demandé si cela ne serait pas plus facile en gain de temps et de mémoire sans les multiples de 7... On a vite laissé tomber car même manuellement c'est galère à ""cause des trous que cela occasionnent""
Donc regarde le forum PROGRAMMATION et le Sujet : modifier un programme python page 2 par (leg) tu vas comprendre...

fait l'expérience en écrivant les entiers impairs sans les multiples de 7 , modulo 210 à partir de la bonne limite, tu verras qu'il te faut revenir pour vérifier sans arrêt les trous...tu n'as pas une progression linéaire mais en escalier...enfin bref , ça ne sert à rien a part passer du temps à faire le programme....sans garantie qu'il ne sautera pas des nombres premiers, si il y a un bug dans le programme qui oublie de vérifier....etc ...etc

Dernière modification par LEG (26-03-2021 13:52:01)

Forum de mathématiques - Bibm@th.net

#1 17-03-2021 14:13:35

Z/nZ;algorithme permettant de construire la suite des nombres premiers

#2 17-03-2021 19:49:49

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#3 17-03-2021 20:45:00

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#4 18-03-2021 09:52:44

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#5 19-03-2021 09:02:38

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#6 19-03-2021 11:24:33

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#7 19-03-2021 12:13:26

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#8 21-03-2021 12:09:05

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#9 21-03-2021 12:50:09

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#10 21-03-2021 12:50:29

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#11 21-03-2021 13:23:13

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#12 21-03-2021 14:15:46

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#13 22-03-2021 11:33:55

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#14 22-03-2021 12:22:17

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#15 22-03-2021 15:27:57

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#16 24-03-2021 14:12:36

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#17 24-03-2021 15:29:37

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#18 25-03-2021 11:07:21

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#19 25-03-2021 13:15:40

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#20 26-03-2021 11:51:57

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

#21 26-03-2021 13:45:15

Re : Z/nZ;algorithme permettant de construire la suite des nombres premiers

Réponse rapide

Pied de page des forums