Conjecture autour des nombres premiers

[invite251213]

En effet j'ai mal copié et j'ai entendu pas fait la version récursive surtout pas en python

Je note la petite modification qui rend l'algorithme plus propre on va dire mais je ne crois pas qu'elle est une quelconque sur la vitesse.

Le mieux serait peut être de faire un programme maple ou quelque chose du genre parce que la je ne pense pas qu'on puisse arriver a quelque chose vu la lenteur du programme.

Je pense que tu devrais plutôt coder un petit programme en C ou C++, et le compiler (si tu sais le faire, bien sur).

Sinon, regarde bien au niveau de l'algorithme de test de primalité. Il doit y avoir de trucs bien plus rapides.

Je ne sais pas, par exemple, tu pourrais teste directement si ton nombre est divisible par 3 ou 5, ou 7... en dehors de la boucle. Ça éviterait pas mal de branchements.

Un truc du genre:

if n%2 || n%3 || n%5.. || n% z then
     return 0
i=z

Au pire, j'ai trouvé ca pour les tests de primalité : http://fordom.free.fr/tuto/NP/TUTONP.htm
Faut voir ce que ca vaut et si ca améliore vraiment ton programme.

Mais de toute façon, un code complétement rempli de modulo, faut pas trop espérer. C'est une opération particulièrement lente.
-----

[invite25cbd5d2]

Aussi une petite faute de frappe:
C'est p**2 et pas p^2.

[invite4ef352d8]

à titre informatif, j'ai déjà poussé la vérification jusqu'à p=103... en utilisant des fonctions efficace (probabiliste) de teste de primalité, ca ne prend pas plus de quelques secondes...

[invite4ef352d8]

(NB : je viens d'aller jusqu'à 250 et en testant tout les entier, pas seulement les nb premiers cela prend une cinquantaine de seconde, je peux aller plus loin, mais personellement ca suffit à me convaincre que la conjecture est vrai... )

[invite25cbd5d2]

Peux tu montrer ton code ?
Moi 250 ne me suffit pas du tout

[invite986312212]

Fermat s'était convaincu que tous "ses" nombres étaient premiers alors qu'il n'en avait calculé que les quatre premiers. Il avait tort.

Il s'est aussi convaincu que "son" équation n'avait pas de solutions alors qu'il ne savait le montrer que pour l'exposant 4. Il avait raison.

[invite4ef352d8]

certe, mais ce qui me convainc, c'est pas tant d'avoir tester 250 nombres, c'est la petitesse des nombres 'i' tel que n!+i est premier. bien sur i est toujours supérieur à n (enfin sauf dans les très rare cas ou il vaut 1... ) mais il ne dépasse pas quelques n (il est très souvent inférieur à 2 ou 3n ) bref, la conjecture est non seulement vérifier pour chacun de ses n, mais avec une très très grosse marge à chaque fois...

d'autant plus que quand on teste des nombres de l'ordre de 250 il est quand même de problème de repartition de nombres premier à 500 chiffre sur un intervalle de longeur 60.000, à ce niveau là j'ai plutot fois en l'argument de densité...

pour ce qui est de mon code, il ma pris moins de 1 minutes à ecrire donc je ne l'ai pas conservé : il s'agit d'une boucle testant un par un tout les nombre entre n! et n!+i en utilisant une fonction de teste de primalité pré existance et nettement plus efficace que tous ce qu'on pourra essayer d'ecrire à la main en moins de quelques heures ^^. enfin c'est exactement le code de mewtow quoi (j'ai utilisé la fonction de teste de primalité de maple )


ce que je disais c'est plutot qu'on pourra pas aller plus loin que n=quelques millier, et il n'y aura vraisemblablement aucun contre exemple dans ce domaine

[invite986312212]

si Dn est l'intervalle entre le n-ième et le (n+1)-ième nombre premiers, je définis la suite D(n) par récurrence: D(1)=D1 (=1) et ensuite D(n) est le premier Dn tel que D(n)>D(n-1). C'est en somme la suite des "records" de longueur pour l'intervalle entre premiers adjacents. Est-ce qu'on connaît la vitesse de croissance de cette suite?

[invite251213]

Bon, j'ai fait quelques test, avec un code semblable à celui présenté plus haut dans le forum, et je trouve que la conjecture devient fausse pour pas mal de nombre. Ca commence à être faux au dela de 57000 pour certains nombres (pour 6666666, ca marche,par exemple)...

Mais je crois que j'ai une erreur dans mon code : ca met même pas une seconde pour calculer une valeur, même avec un grand nombre comme 57000...

Je poste mon code au cas ou.

Le test de primalité :

let test_primaute ( n ) =
let a = ref true in
if (n mod 2 = 0) && (n<>2) then
	a := false
else
begin
	let i = ref 3 and square = ref ( int_of_float( sqrt( float_of_int(n) ) ) ) in
	while ( !i <= !square ) && !a do
		a := not ( n mod !i = 0 ) ;
		i := !i+2
	done;
end;
!a
;;

La factorielle :

let factorielle (n) =
let fact = ref 1 in
for i=2 to n do
	fact := !fact * i ;
done;
!fact
;;

vérification de la conjecture :

let conjecture(n)=
let j = ref (factorielle n) in
let i = !j + (n*n) in
let a = ref false in
while (!j <= i )  && not (!a) do
	if test_primaute(!j) then
		a := true;
	j := !j + 1 ;
done;
!a
;;

Les fonctions factorielles et test de primalité semblent marcher pour les valeurs inférieures à 200 : vérifié par tests unitaires. (ou presque, j'ai regardé si en gros ca marchait, j'ai pas vérifié toutes les valeurs sorties par mon pc...).

Voici le test unitaire des fonctions factorielles et test_primalité:

for i = 2 to 200 do
	if test_primaute(i) (*ou factorille(i), c'est selon*) then
		print_endline(string_of_int(i))
done;;

[leg]

Bonjour
il y a quand même quelque chose de faux dans cette conjecture, si on prend le simple exemple de 7! + k avec k {1....49}

car 5040+49 = 5089, or: 49/3.75 =13,066666 entiers congrus 1 ou P modulo 30; avec P : 5< P <31.
et effectivement il y a bien 5 premiers parmi ces 13 entiers
mais pour 5041 + K , avec K = 2, 4 c'est impossible puisque ces deux nombres ne seraient congrus 1,P[30], puis K = 6, peut être, mais à nouveau K = 8 impossible, seule les entiers K = 6 + 4 +2 +4 +2 +4 +6 +2 +6...
le cycle de différence D entre ces entiers est de :
6.4.2.4.2.4.6.2 = 30 en partant de 1.
5041 est congrus 1[30] .

les premiers > 5 sont tous compris dans les entiers congrus 1 ou P [30], soit 26,6666% des entiers naturels positifs.

on peut donc ("si j'ai bien compris le problème") dire, qu'il y a une infinité de K, pour lequel la conjecture est vraie et une infinité de k, où la conjecture est fausse. Non?
.............................. .............................. ......
Comme on peut aussi estimer, le nombre de premiers compris entre deux premiers consécutifs, au carré :
(P_n+1)² - (P_n)² = X premiers

avec un minimum et en partant de 7, de :
exemple 11² - 7² = 72 = D
puis :
(D/3,75) - (D/4,364...) = 3 au lieu de 15

186163² - 186161² =744648

(D /3,75) - (D/4,364...) = 27939 premiers , au lieu de 30513 réel.
il y a surement des formules plus précises...
.............................. .............................. ..............

[invite18cff193]

Faut quand même relire l'énoncé.
Je parle de p! + k (k=1 à p^2) avec p nombre premier.
Que vient faire 57000! ou 10!?

[invite25cbd5d2]

J'avais pas remarqué que p est premier mais il semble que la conjecture est valide pour p quelconque.

[invite251213]

Oups... boulette. J'avais pas remarqué qu'il fallait que p soit premier.

Bon, ben résultat : après correction, ta conjecture est quand même fausse.

D'après mes tests, le premier nombre qui soit premier pour lequel la conjecture est fausse est 32779 (Sous réserve qu'il n'y ait pas d'erreurs dans les fonctions que j'ai utilisées).

C'est bien un nombre premier (en tout cas d'après ce site : http://primes.utm.edu/lists/small/10000.txt ). Et la conjecture est fausse pour celui-ci, ainsi que presque tous les suivants.

[invite251213]

En fait, non, j'ai rien dit, désolé.

Oubliez ce que j'ai dit dans le message plus haut : les programmes ne marchent pas : pour factorielle de 32779, le résultat est zéro. Faudra utiliser des flottants dans les codes plutôt que des int...

[invite18cff193]

103040!-1 est le plus grand 'factoriel premier' connu.
Je ne sais pas si tu as idée de ce que tu dis.
Fais un petit tour ici :
http://primes.utm.edu/largest.html

[invite18cff193]

Rien que pour calculer 10.000.000! (je ne parle pas de calcul de primalité) l'algo le plus puissant le fait en 1 minute.
Vaut mieux chercher à rejeter ou à confirmer la conjecture plutôt que de chercher un contre-exemple.
Il y a des arguments à faire prévaloir en faveur du rejet ou de la confirmation de la conjecture.
Connaître l'écart maximal entre P(n+1) et P(n) peut aider mais il faut garder à l'esprit que c'est entre p! et p!+k (k=1 à p^2) que l'intervalle devrait contenir (ou pas) de premiers.