Nombres premiers

[Doraki]

je suis désolé mais 3²-(-5)² n'est pas positif, et l'exposant 3 que tu vois, il est à l'intérieur d'un terme qui est mis au carré.

[_Telemaque_]

Ca me paraît logique qu'il est possible de trouver une valeur négative au résultat final mais on peut absolument trouver une valeur positive. Du moins, je ne vois pas pourquoi on ne pourrait pas. Je n'ai pas vraiment le temps de décortiquer cette formule afin de voir quand est-ce qu'on aurait une valeur positive mais je suis persuadé que c'est possible quand je la regarde. Quoique, plus je la regarde, moins j'y crois... On ne fait qu'enlever à 1 des entiers supérieurs à 1 --'. Je vais en parler à mon prof de maths, il doit avoir bac +30 et est fan des énigmes sans réponse !

[ffpower]

Ben c'est ce que dit Doraki, c'est strictement positif si et seulement tous les termes carrés sont nuls..ce qui revient donc à résoudre un gros systeme..

[Doraki]

C'est certainement possible, mais c'est juste très très très TRES improbable en y allant au hasard.

[Ben314]

Je plussois ce que disent Doraki et ffpower : la formule est trés joli dans la théorie, mais n'a absolument aucun intérêt dans la pratique : elle ne fait que traduire à l'aide d'une formule unique une proposition logique de la forme "il existe des entiers a,b,c,d,... tels que ...."

Pour te donner un exemple, on te demande de déterminer l'ensemble E les entier n strictement positifs qui peuvent s'écrire sous la forme n=a²+b².

Je peut te répondre du tac au tac que E est trés exactement l'ensemble des valeurs strictement positives prises par la fonction de 3 variables :
(avec a,b,n entiers naturels)
As-tu l'impression qu'en écrivant cela on a vraiment fait un quelconque progrés vers la détermination de l'ensemble en question ?

[_Telemaque_]

Franchement, ce que tu dis est largement au dessus de mes petits moyens... J'ai 15 ans et suis en 2nde. Je suis loin d'être le plus nul des secondes en maths mais je suis pas vraiment le plus fort. C'est vrai qu'en suivant ton raisonnement, la formule de 4 lignes à 26 variables paraît totalement inutile et inutilisable. On ne trouvera jamais un résultat exploitable et je ne comprends toujours pas comment on peut trouver un nombre premier en utilisant une multiplication. De plus, s'il faut que je rentre 26 variables dans ma calculette pour éventuellement tomber sur un nombre premier quelconque, je crois que je vais mourir de vieillesse avant d'avoir rendu mon devoir !

[ffpower]

je ne comprends toujours pas comment on peut trouver un nombre premier en utilisant une multiplication.

Je te rassure, moi non plus
J'aurais envie de dire qu'ils ont pris par exemple le programme classique pour tester si un nombre n est premier :

"pour x allant de 2 jusqu'à n
pour y allant de 2 jusqu'à n
si xy=n alors ( n non premier.. FIN)"

et qu'ils ont réussi à coder ce programme d'une maniere ou d'une autre par un nombre fini d'opérations arithmétiques..
M'enfin ça reste assez mysterieux..

[Ben314]

La formule de départ

f(a,b,c,...z)=[1-(wz+h+j-q)²-((gk+2g+k+1)(h+j)+h-z)²-(2n+p+q+z-e)²-(16(k+1)^3(k+2)(n+1)²+1-f²)²-(e^3(e+2)(a+1)²+1-o²)²-((a²-1)y²+1-x²)²-(16r²y^4(a²-1)+1-u²)²-(((a+u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²)²-(n+l+v-y)²-((a²-1)l²+1-m²)²-(ai+k+1-l-i)²-(p+l(a-n-1)+b(2an+2a-n²-2n-2)-m)²-(q+y(a-p-1)+s(2ap+2a-p²-2p-2)-x)²-(z+pl(a-p)+t(2ap-p²-1)-pm)²] [k+2]

Dit mot pour mot que :
Un entier P=k+2 (k positif) est premier si et seulement si il existe 25 entiers positifs a,b,...i,j,l,m,...,y,z tels que :
1) wz+h+j-q=0 ;
2) (gk+2g+k+1)(h+j)+h-z=0 ;
3) 2n+p+q+z-e=0 ;
4) 16(k+1)^3(k+2)(n+1)²+1-f²=0 ;
5) e^3(e+2)(a+1)²+1-o²=0 ;
6) (a²-1)y²+1-x²=0 ;
7) 16r²y^4(a²-1)+1-u²=0 ;
8) ((a+u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²=0 ;
9) n+l+v-y=0 ;
10) (a²-1)l²+1-m²=0 ;
11) ai+k+1-l-i=0 ;
12) p+l(a-n-1)+b(2an+2a-n²-2n-2)-m=0 ;
13) q+y(a-p-1)+s(2ap+2a-p²-2p-2)-x=0 ;
14) z+pl(a-p)+t(2ap-p²-1)-pm=0
Ensuite, il faut "décoder" ce que disent "en clair" chaque formule (ce qui n'est pas évident...)
Pour donner un exemple trés simple, la lettre 'v' n'apparait que dans la formule 9) ce qui signifie que la formule 9) est uniquement là pour traduire l'inégalité y>=n+l à l'aide d'une égalité.

La seule "astuce" pas évidente du tout derrière tout ça, c'est d'arriver à écrire que P est premier uniquement à l'aide de quantificateurs existentiels (il existe) et d'égalités alors que le premier truc qui vient à l'esprit, c'est d'écrire :
P est premier
qui contient des quantificateurs universels (quelque soit) et une inégalité...

[ffpower]

Pour gérer le "", avec ton astuce, on gére. C'est l'existence de c tel que :
(P-ab+c+1)(P-ab-c-1)=0
Reste le tout petit problème du "pour tout" :we:

[Ben314]

Effectivement, tel quel, le "pour tout" n'est pas traduisible directement.

Je me rapelle qu'au moment de la sortie, j'avais trouvé l'article correspondant et qu'il n'y avait rien de "super complexe" derrière, mais que ce n'était quand même pas de la traduction "mot à mot" : la série d'égalités traduisent quand même un critère "un peu malin" de primalité.

Je me demande si la "clef" n'est pas en partie dans la formule 9)
((a+u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²=0
qui est la seule contenant les lettres c et d et qui dit donc que, si A désigne l'entier (a+u²(u²-a))²-1, l'équation de Pell-Fermat X²-AY²=1 admet une solution où X est congru à x modulo u et Y est congru à n modulo 4y...

[benekire2]

Il existe tout de même une formule à 26 variables telle que ses résultats positifs sont tous les nombres premiers!

Mais je vais finir par pleurer
Si vous voulez une formule qui énumère tout les nombres premiers dans l'ordre sans répétition : Alles voir la formule que j'ai demandé de prouver dans un post "défi" , elle existe bel et bien , là n'est pas le problème.

Le problème c'est que seul Dieu peut l'utiliser. Faire le calcul pour trouver le 3 ième nombre premier rend compréhensible que le calcul du 10000 nombre premier soit très chaud (enfin long..) pour une machine !!

Elle est inutilisable la formule , et en carton, mais elle existe !

[nodjim]

Mais je vais finir par pleurer
Si vous voulez une formule qui énumère tout les nombres premiers dans l'ordre sans répétition : Alles voir la formule que j'ai demandé de prouver dans un post "défi" , elle existe bel et bien , là n'est pas le problème.

Le problème c'est que seul Dieu peut l'utiliser. Faire le calcul pour trouver le 3 ième nombre premier rend compréhensible que le calcul du 10000 nombre premier soit très chaud (enfin long..) pour une machine !!

Elle est inutilisable la formule , et en carton, mais elle existe !

La formule que tu cites a été élaborée par Minac et Willans en 1995. Et en effet, si on la passe dans une machine, ça ne donne pas grand chose, enfin ça donne bien les nb premiers, mais c'est long, très long...tente de calculer le 7 ème premier avec cette formule. Bon courage.

[Ben314]

Je vous avoue franchement que, de trés loin, ma fonction préférés pour générer les nombres premiers est celle là (bis et répétita) :
f(n)=le n-ième nombre premier. (*)
C'est trés court, parfaitement explicite (une fois qu'on a montré qu'il y avait une infinité de nombres premiers) et je vois pas en quoi c'est plus idiot que des fonctions du style :
racine(y)=le seul réel positif x tel que x²=y.
ln(t)=surface sous la courbe de y=1/x comprise entre les droites x=1 et x=t.
Aucune de ces deux formules ne me semble bien plus "explicite" que celle que j'ai donné au début.

Alors je voudrais bien savoir pourquoi cette formule (*) a l'air de vous déranger plus que celle définisant la racine carrée ou le log ?

[benekire2]

Ben > Perso elle ne me dérange pas :zen:

Seulement je comprends que ça dérange certaines personnes, demander " Papa où as tu rangé les céréales dans la cuisine" et que le père répond " C'est dans la cuisine, une fois que t'as montré qu'il y a une nombre fini de placards , ça ira mieux" ça peut gêner :mur:
Comme tu l'a souligné on défini pas mal de trucs comme ça et on fait pourtant les propriétés qu'on veut après , donc rien de gênant.
Pour ma part je répondais simplement à l'interrogation de savoir s'il existait une formule explicite "palpable" même si j'ai souligné plein de fois que elle est en carton, et que cette formule est un leurre !!

Nodjim > C'est ce que j'ai dit dans le message que tu as cité , Calculer pour n=3 est déjà une épreuve ..

[ffpower]

Bah ça reste quand même marrant de voir qu'on peut exprimer le fait d'etre premier juste avec des "il existe" et des quantités polynomiales.

Pour taper dans un truc qui a l'air plus simple que le nombres premiers : peut on expliciter un poly dont les valeurs positives sont les puissances de 2?

[Ben314]

Bah ça reste quand même marrant de voir qu'on peut exprimer le fait d'etre premier juste avec des "il existe" et des quantités polynomiales.

Pour taper dans un truc qui a l'air plus simple que le nombres premiers : peut on expliciter un poly dont les valeurs positives sont les puissances de 2?

Sauf erreur de ma part, le "théorème profond" dont est issue le fameux polynôme en 26 variables donnant comme valeurs positives les nombres premier dit que tout ensemble "calculable" peut se décrire uniquement à l'aide de quantificateurs existentiels et d'égalités.

[_Telemaque_]

Pouvez-vous mettre la formule ou juste un lien vers ce que tu as proposé, je ne l'ai pas trouvé en partie "DEFI" et ca m'a l'air intéressant de connaître ca même si ca paraît long :p

[Ben314]

Pouvez-vous mettre la formule ou juste un lien vers ce que tu as proposé, je ne l'ai pas trouvé en partie "DEFI" et ca m'a l'air intéressant de connaître ca même si ca paraît long :p

De quelle formule parle tu ?

Sinon, concernant le problème d'expliciter un polynôme dont les valeur positives sont les puissances de 2, j'ai fini par trouver le théorème auquel je pensait (et duquel découle le fameux polynôme donnant les premiers) : il est du à Youri Matiiassevitch :
voir là : http://fr.wikipedia.org/wiki/Diophantien (à "fonction diophantiennes)
et/ou là : http://fr.wikipedia.org/wiki/Dixi%C3%A8me_probl%C3%A8me_de_Hilbert ("Un ensemble est récursivement énumérable si et seulement s’il est diophantien")

En particulier, dans le premier article, il donnent un polynôme P en un certain nombre de variables tel que :
b=a^c (entiers) ssi il existe d,e,f,...,p,q tels que P(a,b,c,d,e,f,...,p,q)=0
qui, en prenant a=2 donne une réponse à ta question.

[Doraki]

Pour taper dans un truc qui a l'air plus simple que le nombres premiers : peut on expliciter un poly dont les valeurs positives sont les puissances de 2?

Si mes souvenirs sont bons c'est la preuve qu'on peut coder les exponentielles qui était la dernière étape (difficile) de la réponse au 10ème problème de Hilbert.

J'ai pas cherché mais j'suis pas sûr que je trouverais si je cherchais.

ah bah je n'avais point vu que Ben l'avait déjà dit, j'avais cru qu'il parlait qu'à télémaque.

[benekire2]

Telemaque >le nom du topic est «une formule pour les nombres premiers» posté par benekire2 si mes souvennirs sont exacts.