Nombres premiers.

par **zygote3333** » 03 Déc 2010, 19:09

Bonjour à toutes et à tous!
Il y'a un peu plus de trois ans j'ai "découvert" en jouant avec les entiers une manière de savoir si ceux-ci étaient premiers ou non. Je voulais donc savoir si cette méthode était connue (ce que je suppose).
J'effectue les additions suivantes:
1+1=2 premier
1+2=3 premier
2+3=5 premier
3+4=7 premier
4+5=9 pas premier car 5 qui est à droite dans l'addition appartient à une suite arithmétique dont le premier terme est 5 et la raison 3.
5+6=11 premier
6+7=13 premier
7+8=15 pas premier car 8 qui est à droite dans l'addition appartient à la suite arithmétique précédente.
8+9=17 premier
9+10=19 premier
10+11=21 pas premier pour les mêmes raisons.
11+12=23 premier
12+13=25 pas premier car 13 qui est à droite dans l'addition appartient à une nouvelle suite arithmétique de premier terme 13 et de raison 5.
On voit qu'à chaque fois que le terme de droite dans l'addition appartient à l'une de mes suites alors cette somme n'est pas un nombre premier.
Les suites apparaissent au fur et à mesure. la première part de 5 et a pour raison 3.
la seconde part de 13 et a pour raison 5.
la suivante part 25 et a pour raison 7.
Il y'a une "structure" commune qui permet de trouver toutes ces suites arithmétiques.
Je vous laisse le soin de trouver cette structure. Si quelqu'un a déjà entendu parler de cet algorithme je serais heureux qu'il me le dise.

par **Ben314** » 03 Déc 2010, 19:13

Salut,
Grosso modo, et à une virgule prés, ça s'appelle "la méthode du crible d'ératostène" : c'est pas vraiment récent comme méthode (2200 ans)

par **nee-san** » 03 Déc 2010, 19:18

pour le cripte regarde ici http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./e/erathostene.html

par **Doraki** » 03 Déc 2010, 19:25

Pourquoi tu dis que 3+4 est premier alors que 4 qui est à droite dans l'addition appartient à une suite arithmétique de premier terme 4 et de raison 28 ?

par **zygote3333** » 03 Déc 2010, 19:35

Désolé de vous décevoir mais non ça ne ressemble pas au crible d'Erasthotène.
Et pour ta suite elle n'appartient pas à l'ensemble de mes suites.

par **Doraki** » 03 Déc 2010, 19:38

J'me suis trompé j'voulais dire la suite arithmétique de premier terme 4 et de raison -17.

C'est quoi l'ensemble de tes suites ?

par **zygote3333** » 03 Déc 2010, 20:30

Une de ces suites s'écrit U(n,m)=(((2m+1)^2)+1)/2+(2m+1)n
m est l'indice qui permet de trouver la raison d'une de ces suites, il commence à partir de 1.
Par exemple la premiere suite pour m=1 est U(n,1)=5+3n.

par **Sve@r** » 03 Déc 2010, 20:46

zygote3333 a écrit:11+12=23 premier
12+13=25 pas premier car 13 qui est à droite dans l'addition appartient à une nouvelle suite arithmétique de premier terme 13 et de raison 5.
On voit qu'à chaque fois que le terme de droite dans l'addition appartient à l'une de mes suites alors cette somme n'est pas un nombre premier.
Les suites apparaissent au fur et à mesure. la première part de 5 et a pour raison 3.
la seconde part de 13 et a pour raison 5.
la suivante part 25 et a pour raison 7.
Il y'a une "structure" commune qui permet de trouver toutes ces suites arithmétiques.
Je vous laisse le soin de trouver cette structure. Si quelqu'un a déjà entendu parler de cet algorithme je serais heureux qu'il me le dise.

Mouais. Mais plus tu avanceras plus tu tomberas sur des nombres pas premiers...
13+14=27 pas premier
14+15=29 premier
15+16=31 premier
ok. Mais
100+101=201 pas premier (3 x 67)
101+102=203 pas premier (7 x 29)
102+103=205 pas premier (5 x 41)
103+104=207 pas premier (3 x 69)
104+105=209 pas premier (11x19)
105+106=211 premier (et le suivant est à 223 puis 239)...

par **zygote3333** » 03 Déc 2010, 20:48

Je suis allé jusqu'au nombre premier 797. Ma méthode marche à coup sure!!!

par **zygote3333** » 03 Déc 2010, 20:50

Sve@r a écrit:Mouais. Mais plus tu avanceras plus tu tomberas sur des nombres pas premiers...
13+14=27 pas premier
14+15=29 premier
15+16=31 premier
ok. Mais
100+101=201 pas premier (3 x 67)
101+102=203 pas premier (7 x 29)
102+103=205 pas premier (5 x 41)
103+104=207 pas premier (3 x 69)
104+105=209 pas premier (11x19)
105+106=211 premier (et le suivant est à 223 puis 239)...

14 appartient à la suite U(n,1)=5+3n. et 101,102,103,105 appartiennent aussi à l'une de mes suites.

par **Ben314** » 03 Déc 2010, 21:02

zygote3333 a écrit:Désolé de vous décevoir mais non ça ne ressemble pas au crible d'Erasthotène.
Et pour ta suite elle n'appartient pas à l'ensemble de mes suites.

Bon, revenons au B.A.BA :
1) Tu considère les entiers qui s'écrivent sous la forme n+(n+1)=2n+1 tu "barre" tout les nombres pairs, c'est à dire les multiples de 2.
2) Tu élimine les nombres n+(n+1) lorsque n+1 fait partie de la suite arithmétique de premier terme 5 et de raison 3 tu "barre" les 2n+1 tels que n=4+3k, c'est à dire tout les nombres impairs supérieurs ou égaux à 3² et qui sont multiples de 3.
3) Tu élimine les nombres n+(n+1) lorsque n+1 fait partie de la suite arithmétique de premier terme 13 et de raison 5 tu "barre" les 2n+1 tels que n=12+5k, c'est à dire tout les nombres impairs supérieurs ou égaux à 5² et qui sont multiples de 5.
4) Tu élimine les nombres n+(n+1) lorsque n+1 fait partie de la suite arithmétique de premier terme 25 et de raison 7 tu "barre" les 2n+1 tels que n=24+7k, c'est à dire tout les nombres impairs supérieurs ou égaux à 7² et qui sont multiples de 7.
ect...
Quand à ta question concernant la "structure" des suites arithmétiques que tu considère, ben on peut te répondre facilement : la k-ième suite arithmétique, c'est celle qui va consister à barrer tout les multiples du k-ième nombre premier p_k à partir de pk²... (étonant non !)

En résumé, à part que c'est moins visuel que la méthode originale du crible, je vois vraiment pas ou est la différence...

Par exemple, je parierais fort que :
100+101=201 pas premier (3 x 67) : appartient à la 1ère suite vu qu'elle élimine les multiples de 3
101+102=203 pas premier (7 x 29) : appartient à la 3em suite vu qu'elle élimine les multiples de 7
102+103=205 pas premier (5 x 41) : appartient à la 2em suite vu qu'elle élimine les multiples de 5
103+104=207 pas premier (3 x 69) : appartient à la 1ère suite vu qu'elle élimine les multiples de 3
104+105=209 pas premier (11x19) : appartient à la 4em suite vu qu'elle élimine les multiples de 11

par **zygote3333** » 03 Déc 2010, 21:52

Je crois que cette méthode est beaucoup moins gourmande en calcul.

par **Ben314** » 03 Déc 2010, 21:59

zygote3333 a écrit:Je crois que cette méthode est beaucoup moins gourmande en calcul.

Ca me surprendrait un peu, vu que... il n'y a aucune différence.
Si tu cherche à programmer "ta" méthode, tu te rendra vite compte que pour savoir si ton "n+1" fait parti d'une de "tes" suites, ben le plus rapide, c'est de regarder s'il se divise par un des nombres premiers que tu as déjà trouvé (à concurence de la racine carré du nombre en question) :

En bref, c'est la méthode "basique" en info pour dresser une table de nombre premier et en fait, c'est... le crible d'ératostène...

par **zygote3333** » 03 Déc 2010, 23:29

Il y'a tout de même une chose qui m'intrigue et auquelle vous aurez surement une réponse à me donner. Pourquoi avec ma méthode tout est fixé à l'avance car les suites sont bien définies et donc par la même occasion la position des premiers alors qu'avec le crible d'Erasthotène on découvre au fur et à mesure leurs enplacements. En espérant n'être pas trop lourd dingue :marteau: . Cordialement.

par **darkpseudo** » 03 Déc 2010, 23:56

Dsl d'intervenir , mais pour tes suites j'aimerais bien connaître la façon avec laquel tu les as trouver ?

par **zygote3333** » 03 Déc 2010, 23:57

A la main.

par **Ben314** » 04 Déc 2010, 00:09

zygote3333 a écrit:Il y'a tout de même une chose qui m'intrigue et auquelle vous aurez surement une réponse à me donner. Pourquoi avec ma méthode tout est fixé à l'avance car les suites sont bien définies et donc par la même occasion la position des premiers alors qu'avec le crible d'Erasthotène on découvre au fur et à mesure leurs enplacements. En espérant n'être pas trop lourd dingue :marteau: . Cordialement.

C'est exactement la même chose dans le crible d'ératostène :
Mettons que tu en soit au nombre premier 17, tu est cencé "barrer" tout les multiple de 17 qui sont au dela de 17, mais tu as déjè "barré" tout les multiple de 2 (donc 2x17, 4x17, 6x17,...) ainsi que tout les multiples de 3 (donc 3x17, 9x17,...) etc
Donc le premier multiple de 17 qui n'est pas déjà "barré" est 17x17.
C'est la raison pour laquelle la méthode du crible te dit que, si par exemple tu veut trouver la liste de tout les nombres premiers inférieurs à 500, alors ce n'est plus la peine de "barrer" quoi que ce soit dés que tu en est à un nombre premier supérieur à racine(500)=22,... : Les nombres qui ne sont pas déjà barré sont tous premiers.

par **Ben314** » 04 Déc 2010, 00:16

Concernant les suites que tu enlève, pour un p premier (autre que 2) tu enlève les 'n+1' tels que 2n+1 soit un multiple de p supérieur ou égal à p².
Si tu pose m=n+1 (et donc n=m-1), cela signifie que tu enlève les m tels que 2m-1 soit multiple de p et supérieur à p².
Le premier tel m (donc le premier terme de ta suite) correspond à 2m-1=p², c'est à dire m=(p²+1)/2 et la raison de ta suite est évidement p.

p=3 -> premier terme=(3²+1)/2=5 ; raison=3
p=5 -> premier terme=(5²+1)/2=13 ; raison=5
p=7 -> premier terme=(7²+1)/2=25 ; raison=7
p=11 -> premier terme=(11²+1)/2=61 ; raison=11
p=13 -> premier terme=(13²+1)/2=85 ; raison=13
p=17 -> premier terme=(13²+1)/2=145 ; raison=17
etc...

par **nodjim** » 04 Déc 2010, 10:55

Avec ta méthode, comment sais tu si 18463148+18463149 est premier ?

par **Sve@r** » 04 Déc 2010, 13:48

nodjim a écrit:Avec ta méthode, comment sais tu si 18463148+18463149 est premier ?

Je divise le nombre final par 2 et je regarde le reste. Si c'est pas zéro alors
Je divise le nombre final par 3 et je regarde le reste. Si c'est pas zéro alors
Je divise le nombre final par 5 et je regarde le reste. Si c'est pas zéro alors
Je divise le nombre final par 7 et je regarde le reste. Si c'est pas zéro alors
Je divise le nombre final par 11 et je regarde le reste. Si c'est pas zéro alors
...
Jusqu'à ce que le diviseur devienne plus grand que le quotient. Si je suis arrivé jusque là, alors il est premier.
Ah ? Il n'y a aucune différence avec la méthode classique ??? :id:

Nombres premiers.

Nombres premiers.

Qui est en ligne