Bonjour,

Pour ceux qui ont du mal à suivre la discussion avec remy et ses
multiples tentatives de démontrer la conjecture de Goldbach avec
des primorielles, voici un résumé de l'idée forte derrière toutes
ces tentatives.

Je vais tâcher de le faire en adoptant un point de vue plus
rigoureux que ne le fait remy lui-même, et en ignorant la plupart
des maladresses qui le caractérisent (par exemple se baser sur des
exemples uniquement, ou bien commencer par définir la primorielle
avant le nombre pair 2n). Je passe aussi sur le fait que parfois 2n
doit être un produit des mêmes nombres premiers que la primorielle,
et parfois non.

Ensuite je vous proposerai un défi, pour tenter de prouver
définitivement (si c'était possible) que l'approche en question
ne pourra jamais mener à rien.

*********************************
*** 1. Résumé de l'idée forte ***
*********************************

Ce qu'a conjecturé Christian Goldbach, c'est que tout nombre
pair supérieur ou égal à 4 peut s'écrire comme somme de deux
nombres premiers.

L'approche de remy repose en fait sur deux idées principales. La
première est qu'il est plus facile de déterminer si deux nombres
sont premiers entre eux, que de déterminer si un nombre est premier
dans l'absolu.

La seconde est que si un nombre est premier avec une primorielle,
et si en outre ce nombre a une racine carrée plus petite que le
plus grand diviseur premier de la primorielle (et même strictement
plus petite que le nombre premier suivant), alors ce nombre est
nécessairement premier.

En effet, si un nombre plus grand que 1 n'est pas premier, il a
au moins deux diviseurs, et le plus petit de ces diviseurs ne peut
pas être plus grand que la racine carrée du nombre.

********************
*** 2. Notations ***
********************

Numérotons les nombres premiers : p1=2, p2=3, p3=5, p4=7, etc.

J'appelle P(x) la primorielle qui est le produit de tous les nombres
premiers inférieurs ou égaux à x. Exemples :
P(2) = 2
P(3) = 2*3 = 6
P(4) = 2*3 = 6
P(5) = 2*3*5 = 30

En pratique, le x en question sera l'un des nombres premiers, par
exemple le np-ième nombre premier noté p_np.
P(p_np) = Produit(p_k) pour k allant de 1 à np
= p1 * p2 * ... * p_np
= 2 * 3 * ... * p_np

Soit un nombre pair 2n (n est un entier quelconque). Je choisis
comme index np le plus petit nombre tel que 2n <= P(p_np). On va
regarder toutes les décompositions de P(p_np) (respectivement de 2n)
en sommes de deux nombres a et b.

Dans un premier temps, concentrons-nous uniquement sur la primorielle
elle-même : P(p_np) = a + b. Ce qui nous intéresse (le « domaine de
définition »), ce sont les décompositions telles que l'un des deux
nombres, mettons b, a sa racine carrée strictement plus petite que
le {np+1}-ième nombre premier, p_{np+1}.

****************************
*** 3. Le défi à relever ***
****************************

Il s'agit de trouver une primorielle P(p_np) dont aucune décomposition
en somme de facteurs premiers ne rentre dans le domaine de définition.

C'est-à-dire :
Quel que soit b un nombre premier strictement supérieur à p_np et
strictement inférieur à p_{np+1}^2, le nombre P(p_np) - b est un
nombre composé.

À vos programmes !

Le 15/11/2019 à 16:54, Olivier Miakinen a écrit :

> J'appelle P(x) la primorielle qui est le produit de tous les nombres
> premiers inférieurs ou égaux à x.

Juste une remarque au passage, Il y a pas mal de P dans le texte. Du
coup je ne le trouve pas super lisible. Il est d'usage de noter x# la
primorielle de x. Ca allège pas mal l'écriture et réserve le symbole "p"
ou "P" aux nombre premiers. Qu'en penses tu?

sam.

Le 15/11/2019 22:49, Samuel DEVULDER a écrit :
>> J'appelle P(x) la primorielle qui est le produit de tous les nombres
>> premiers inférieurs ou égaux à x.
> Juste une remarque au passage, Il y a pas mal de P dans le texte. Du
> coup je ne le trouve pas super lisible. Il est d'usage de noter x# la
> primorielle de x. Ca allège pas mal l'écriture et réserve le symbole "p"
> ou "P" aux nombre premiers. Qu'en penses tu?

Ça ne me gêne pas, c'est juste une question de notation. Comme je ne
la connaissais pas je suis allé voir sur Wikipédia en français où j'ai
vu les deux. C'était avant le 24 août, car je n'avais pas vu la demande
de référence faite par Anne Beauval à cette date à propos de la notation
P(n) en plus de n#.

Au lieu de P(p_np), j'écrirai donc p_np#, ou peut-être plutôt (p_np)#
pour ne pas le confondre avec p_(np#) ?

Le 16/11/2019 à 01:10, Olivier Miakinen a écrit :

> Ça ne me gêne pas, c'est juste une question de notation. Comme je ne > la connaissais pas je suis allé voir sur Wikipédia en français où j'ai
> vu les deux. C'était avant le 24 août, car je n'avais pas vu la demande
> de référence faite par Anne Beauval à cette date à propos de la notation
> P(n) en plus de n#.

Elle a l'avantage d'être postfixée comme la simple factorielle. Elle est
pas mal utilisée chez les anglais, et on la retrouve dans la plupart des
(tous les?) articles plus ou moins vieux utilisant les primorielles:





> Au lieu de P(p_np), j'écrirai donc p_np#, ou peut-être plutôt (p_np)#
> pour ne pas le confondre avec p_(np#) ?

Ce n'est pas évident sans affichage "subscript". En toute logique si on
disposait, comme sur la wiki, d'un tel affichage sur usenet, p_np# se
lirait naturellement comme (p_np)#. Du coup j'aurais tendance à dire
qu'il faut utiliser les parenthèses unique quand on veut utiliser la
primorielle dans une position sbscript/uperscript elle-même, commme là:
p_(np#).

Enfin ce n'est que mon avis.

sam.

Le 15/11/2019 à 16:54, Olivier Miakinen a écrit :
> Quel que soit b un nombre premier strictement supérieur à p_np et
> strictement inférieur à p_{np+1}^2

Ouch.. ca fait pas mal d'entiers à tester. Asymptotiquement il y a de
l'ordre (p_np)^2/(2 ln p_np) de tels entiers et donc autant de test de
non primalité.

sam.

Le 16/11/2019 08:21, Samuel DEVULDER a écrit :
>> Quel que soit b un nombre premier strictement supérieur à p_np et
>> strictement inférieur à p_{np+1}^2
> Ouch.. ca fait pas mal d'entiers à tester. Asymptotiquement il y a de
> l'ordre (p_np)^2/(2 ln p_np) de tels entiers et donc autant de test de
> non primalité.

C'est bien pour ça que remy est persuadé que cette recherche n'aboutira
jamais. Et de fait, s'il a raison et qu'on peut le prouver, cela sera
une avancée intéressante pour la conjecture. Au contraire s'il a tort
et qu'on trouve un contre-exemple, ça met à terre tous ses efforts
jusqu'à présent.

Le 16/11/2019 à 10:42, Olivier Miakinen a écrit :
> Le 16/11/2019 08:21, Samuel DEVULDER a écrit :
> C'est bien pour ça que remy est persuadé que cette recherche n'aboutira
> jamais. Et de fait, s'il a raison et qu'on peut le prouver, cela sera
> une avancée intéressante pour la conjecture. Au contraire s'il a tort
> et qu'on trouve un contre-exemple, ça met à terre tous ses efforts
> jusqu'à présent.

Bon je me suis amusé à écrire le petit programme Java dispo sur
(code en annexe en fin de message, après
la signature{*])

Et sous réserve de bugs, on se rends vite compte que sur les machines
actuelles, la recherche de contre exemples ne permet pas de prendre des
p_np trop gros. Pourquoi? Tout simplement parce que que p_np# croit très
très vite, et les tests de non-primalité sur des nombres aussi gros est
très lente, même s'il faut peu de tentatives pour trouver un p_np-b premier.

Typiquement, si p_np est de l'ordre de 12bits, alors P_np a de l'ordre
de 4000 à 5500 bits et on est là dans des nombres bien plus gros que
ceux utilisés en cryptographie et pour lesquels les implémentations de
tests de primalités sont optimisés. Du coup si on arrive à tester une
primorielle de 4000bits toutes les 10 secondes, avec 13 bits (et donc
des primorielles de 8000bits), ca prends un temps infini (plus que ma
patience en tout cas[**].)

Alors bon, ceux qui ont du temps à perdre ou ont beaucoup de chance
peuvent laisser tourner le programme pour rechercher un contre-exemple
de 13bits, mais j'ai le sentiment que le contre-exemple peut-être une
primorielle de 1Mbits (p_np de 20bits?) et que du coup ont ait aucun
test de primalité de vitesse raisonnable (car il faut pas oublier qu'il
faut faire de l'odre de n_np^2/ln(n_np) tests de primalité pour valider
le contre-exemple.)

Le 16/11/2019 13:57, Samuel DEVULDER a écrit :
> Bon je me suis amusé à écrire le petit programme Java dispo sur
> (code en annexe en fin de message, après
> la signature{*])

Bravo !

> Et sous réserve de bugs, on se rends vite compte que sur les machines
> actuelles, la recherche de contre exemples ne permet pas de prendre des
> p_np trop gros. Pourquoi? Tout simplement parce que que p_np# croit très
> très vite, et les tests de non-primalité sur des nombres aussi gros est
> très lente, même s'il faut peu de tentatives pour trouver un p_np-b premier.
> [...]

J'avais espéré qu'un contre-exemple pourrait émerger très vite, juste avec
les primorielles. Ce n'est apparemment pas le cas, alors l'idée serait
d'aller un peu plus loin et de tester des 2n qui ne sont pas eux-mêmes
des primorielles mais des diviseurs de primorielles (comme le faisait
remy).

Après un souci sur mon ordinateur j'ai commencé à explorer un peu moi
aussi, mais je n'arrive pas encore à grand-chose.

Le 17/11/2019 à 03:54, Olivier Miakinen a écrit :
> J'avais espéré qu'un contre-exemple pourrait émerger très vite, juste avec
> les primorielles.

Je me suis amusé à profiler le programme et constaté que c'est
effectivement le test de primalité sur les "Primorielle-b" qui mange
99.7% de la puissance machine.



Et pourtant les algos utilisés sont efficaces.

Alors pourquoi ca rame?

Et bien d'abord on sait que p_n est de l'ordre n*ln(n) donc le n-ieme
nombre premier n'est pas fondamentalement plus gros en nombre de bits
que n lui-même.

Ensuite une primorielle P(x) est elle même de l'ordre de exp(x+o(x)) >>
exp(x). On voit là une très belle explosion du nombre de bits. Il en
faut en fait plus de bits que *la valeur* de x.

Donc, si on a un p_n qui occupe k bits, sa primorielle p_n# occupe elle
2^k bits. Les algorithmes de tests de primalités, même ceux qui sont
polynomiaux explosent assez vite par rapport à k. Ce qui explique
pourquoi on a plus de 99% du temps passé dans le test Miller-Rabin.

Plus précisément, si on sait que ces tests sont efficaces sur des
nombres jusqu'à 4000 bits, cela signifie que k doit être inférieur à 12
pour que la primorielle ne soit pas plus grosse que le nombre de bits
typique d'usage des tests de primalité. A chaque fois qu'on augmente de
une unité le nombre de bits de p_n, chaque test de primalité double de
temps (en supposant qu'on ait un test de primalité qui soit pratiquement
linéaire, ce qui n'est pas le cas pour les gros nombres, mais passons).

Cela veut dire que pratiquement on ne peut trouver de contre-exemples
que pour les petits nombres premiers <= 4096. Sur des valeurs aussi peu
nombreuses on peut lancer un test exhaustif, et voir qu'il n'y a aucun
contre-exemple :'

Ca ne conclue pas en l?inexistence de contre-exemple, mais cela dit que
notre horizon de recherche est définitivement rikiki avec les algos
"grand public". Il faut d'autres outils que Miller-Rabin pour tester la
primalité des nombres "gros(p_n#) - petit(premier)".

> Ce n'est apparemment pas le cas, alors l'idée serait
> d'aller un peu plus loin et de tester des 2n qui ne sont pas eux-mêmes
> des primorielles mais des diviseurs de primorielles (comme le faisait
> remy).

Oulà, je suis perdu, c'est quoi ce 2n par rapport à l'énoncé du
problème? Cela remplace-t-il p_n# ? Si oui, alors le nombre de bits sera
bien plus petit. Ca rentrera mieux dans le périmètre des limitations de
la technologie à disposition.

le 2n est donc du type 2*produit(p_i^b_i, i>=1) avec b_i=0 ou 1. C'est
marrant, il y a un mapping 1 pour 1 entre ces nombres et les entiers
naturels.

Et donc à supposer que l'on génère tous les 2n de cette forme, il
faudrait trouver un tel de ces nombres tel que tous les "2n-b", b
premier plus quand que le dernier des p_i dont le b_i est non nul et
inférieur à (p_i)^2? C'est ca, ou ce serait plus compliqué?

sam.

Le Sun, 17 Nov 2019 03:54:12 +0100, Olivier Miakinen a écrit :

> Le 16/11/2019 13:57, Samuel DEVULDER a écrit :
>> Bon je me suis amusé à écrire le petit programme Java dispo sur
>> (code en annexe en fin de message, après
>> la signature{*])
> Bravo !

> J'avais espéré qu'un contre-exemple pourrait émerger très vite [...]

Je n'y crois pas trop.

Ce qui suit ne répond pas au problème posé mais prouve qu'entre deux
primorielles il y a toujours au moins un nombre premier.

[DISCLAIMER : sous réserve de grosses boulettes]

Lemme : [1,2^n] contient au moins n nombres premiers.

Preuve par récurrence.

Hn : [1,2^n] contient au moins n nombres premiers.

Initialisation

H0 est vraie {1} contient au moins 0 nombre premier
H1 est vraie [1,2] contient au moins 1 nombre premier
H2 est vraie [1,4] contient au moins 2 nombres premiers

Hérédité

Pour tout n>1, en notant P le *plus grand* nombre premier dans [1,2^n] :

Hn
=> 2 < P < 2^n (A)
=> 2P < 2^(n+1) (B)

De (A) et (B) il vient :

Hn => 2 < P < 2P < 2^(n+1)

Or par le postulat de Bertrand il existe q premier tel que P < q < 2P


Hn => il existe q premier / 2 < P < q < 2^(n+1)

P est le plus grand nombre premier de [1,2^n] par définition donc q
appartient à ]2^n,2^(n+1)]

[1,2^n] contient au moins n nombres premiers par hypothèse

]2^n,2^(n+1)] contient au moins un nombre premier

donc [1,2^(n+1)] contient au moins n+1 nombres premiers.

Hn => Hn+1

La propriété est héréditaire.

La propriété est vraie par récurrence.

Corollaire : pour tout n, [2^n,2^n+1] contient au moins un nombre premier.

Conséquence : entre deux primorielles consécutives il existe toujours au
moins un nombre premier.

Mes deux centimes sous réserve du disclaimer mentionné supra.

Le vendredi 15 novembre 2019 16:54:20 UTC+1, Olivier Miakinen a écrit :
[..]
> À vos programmes !
> --
> Olivier Miakinen

si je n'avais pas étais faire un tour sur google groupe
je n'aurais pas lue ton msg

tu a un pb qt tu poste tes msg

bon bref inutile de faire un programme
parce que si le nombre et un nombre composer
il a obligatoirement un facteur inférieure a sa racine

et comme il ne peut pas en avoir il est premier

cdl remy

Le lundi 18 novembre 2019 11:09:22 UTC+1, remy aumeunier a écrit :
> Le vendredi 15 novembre 2019 16:54:20 UTC+1, Olivier Miakinen a écrit :
> si je n'avais pas étais faire un tour sur google groupe
> je n'aurais pas lue ton msg
> tu a un pb qt tu poste tes msg
> bon bref inutile de faire un programme
> parce que si le nombre et un nombre composer
> il a obligatoirement un facteur inférieure a sa racine
> et comme il ne peut pas en avoir il est premier
> cdl remy

je viens de regarder pour le th en aparté

je te confirme qu'il existe bien toujours au moins 2
nombres premier différent pour une même primorielle

t pour fair simple je construit un nombre qui sera premier avec la
primorielle et dans les clous

2*3*5*7*11-(13*11^2+2*3^2*5*7)=107
2*3*5*7*11-(13^2*11+2^2*3*5*7)=31

donc j'ai bien 2 nombres premier différent mais cela ne veux pas dir
que j'en aurais 4,parcontre la ses une autre histoire,
je but dessus depuis un bail ,pour rappelle je suis dans le contexte
du th en aparté

donc pas sur la conjecture

cdl remy

Le Mon, 18 Nov 2019 03:19:24 -0800, remy aumeunier a écrit :

> t pour fair simple je construit un nombre qui sera premier avec la
> primorielle et dans les clous
> 2*3*5*7*11-(13*11^2+2*3^2*5*7)=107 2*3*5*7*11-(13^2*11+2^2*3*5*7)=31

Il suffit, dans p_n# - a = b , de poser a = p_n# - p_{n+1}.
Il vient immédiatement b = p_{n+1} avec 1 < b < (p_n)² comme voulu.

Et le problème de l'existence de a ne se pose pas (trop - il faut quand
même prouver qu'il existe à partir d'un certain rang n).

Attention, "a" est premier avec la primorielle mais il n'est pas forcément
premier.

Et vous savez quoi ? On peut même prouver qu'à partir d'un autre certain n,
a' = p_n# - p_{n+2} marche aussi et va donner 1 < b' < (p_n)² comme voulu.

Le 17/11/2019 10:24, Samuel DEVULDER m'a répondu :
> Je me suis amusé à profiler le programme et constaté que c'est
> effectivement le test de primalité sur les "Primorielle-b" qui mange
> 99.7% de la puissance machine.
>
> [...]
> Ca ne conclue pas en l?inexistence de contre-exemple, mais cela dit que
> notre horizon de recherche est définitivement rikiki avec les algos
> "grand public". Il faut d'autres outils que Miller-Rabin pour tester la
> primalité des nombres "gros(p_n#) - petit(premier)".

Ok, donc on ne peut pas se limiter aux 2n qui sont des primorielles
pour essayer de donner un contre-exemple à Rémy.

> Oulà, je suis perdu, c'est quoi ce 2n par rapport à l'énoncé du
> problème? Cela remplace-t-il p_n# ? Si oui, alors le nombre de bits sera
> bien plus petit. Ca rentrera mieux dans le périmètre des limitations de
> la technologie à disposition.

Le « 2n » dans tous les documents de Rémy, c'est le nombre pair de la
conjecture de Goldbach, celui qui est censé toujours pouvoir s'écrire
comme somme de deux nombres premiers.

Seulement, comme s'attaquer au problème dans toute sa généralité est
un trop gros morceau pour lui, il tente des démonstrations partielles.
L'une d'entre elles consiste à se limiter aux cas où 2n est lui-même
une primorielle.

Dans une autre tentative de démonstration, Rémy choisissait comme 2n
un nombre n'ayant comme diviseurs premiers que des diviseurs de la
primorielle, chacun d'eux n'étant présent qu'une seule fois. Ainsi que
je le lui ai fait remarquer, ça veut dire tout simplement que 2n est
un diviseur de la primorielle. Bien entendu ça renverse un peu les
choses puisque Rémy choisit d'abord la primorielle, puis le nombre 2n,
alors qu'une vraie démonstration de Goldbach partirait du 2n en tout
premier.

> le 2n est donc du type 2*produit(p_i^b_i, i>=1) avec b_i=0 ou 1.

Plus précisément 2*produit(p_i^b_i, i>=2) puisque p_1=2 est le « 2 »
de « 2n ».

> C'est
> marrant, il y a un mapping 1 pour 1 entre ces nombres et les entiers
> naturels.

Tiens, c'est vrai. Quoique limités par une puissance de 2 lorsque
les 2n définis ici sont limités par une primorielle.

> Et donc à supposer que l'on génère tous les 2n de cette forme, il
> faudrait trouver un tel de ces nombres tel que tous les "2n-b", b
> premier plus quand que le dernier des p_i dont le b_i est non nul et
> inférieur à (p_i)^2? C'est ca, ou ce serait plus compliqué?

Je pense que c'est ça, mais je ne suis pas sûr de comprendre toute
ta phrase. Du coup je reformule, en ajoutant la contrainte que l'on
choisisse la plus petite primorielle qui soit multiple de 2n.

L'algo serait un truc du genre :

Pour tout np :
§
Pour tout 2n de la forme produit(p_i^b_i, 1 <= b_i <= np)
avec b_1 = b_np = 1, les autres b_i valant 0 ou 1 :
§
Soit b le plus petit entier tel que b et 2n-b sont
tous les deux premiers.
Si b > p_{np+1}² :
§
Crier "EURÊKA" en courant tout nu dans Syracuse
§
§
§

************************************************** ***************

Pour ma part, j'ai tenté une autre approche, en regardant tous les
2n sans tenir compte de leur décomposition en facteurs premiers.
Je regardais le plus petit b premier tel que 2n-b était premier, et
à chaque fois que ce b était plus grand que tous ceux trouvés
précédemment j'affichais la somme 2n = b + a. J'ai aussi mis entre
crochets les fois où b dépassait le carré de p_np, où (p_np)# était
la plus petite primorielle plus grande que 2n.

Le programme finit par planter par manque de mémoire, mais j'ai
quand même obtenu les résultats suivants :

* 2# = 2
* 3# = 6
4 = 2 + 2
6 = 3 + 3
* 5# = 30
12 = 5 + 7
30 = 7 + 23
* 7# = 210
98 = 19 + 79
* 11# = 2310
220 = 23 + 197
308 = 31 + 277
556 = 47 + 509
992 = 73 + 919
* 13# = 30030
2642 = 103 + 2539
5372 = 139 + 5233
7426 = 173 + 7253
* 17# = 510510
43532 = 211 + 43321
54244 = 233 + 54011
63274 = 293 + 62981
113672 = 313 + 113359
128168 = 331 + 127837
194428 = 359 + 194069
[383 > 19² = 361] 194470 = 383 + 194087
[389 > 19² = 361] 413572 = 389 + 413183
[523 > 19² = 361] 503222 = 523 + 502699
* 19# = 9699690
[601 > 23² = 529] 1077422 = 601 + 1076821
[727 > 23² = 529] 3526958 = 727 + 3526231
[751 > 23² = 529] 3807404 = 751 + 3806653
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

Le 17/11/2019 11:02, Thomas Alexandre a écrit :
> Ce qui suit ne répond pas au problème posé mais prouve qu'entre deux
> primorielles il y a toujours au moins un nombre premier.
> [démonstration un peu longue faisant appel au postulat de Bertrand]

Tu sais qu'avec le postulat de Bertrand on peut arriver au même résultat
en une seule phrase ?

Il y a au moins un nombre premier entre p_n# et 2 * p_n#,
or (p_{n+1})# = (p_{n+1}) * p_n# >= 2 * p_n#, donc il y a
au moins un nombre premier entre p_n# et (p_{n+1})#

Mais effectivement ça ne répond pas au problème posé, pour deux raisons :

1) On ne regarde pas entre (p_{n-1})# et (p_n)#, mais entre
(p_n)# - p_{n+1}² et (p_n)#

2) Il ne suffit pas de trouver un nombre premier entre ces deux bornes,
il faut *aussi* que son complément à (p_n)# soit aussi premier.