Je suis tombé sur une formule qui génère les nombres premiers de la forme 12k+7 dans l'ordre. J'aimerais bien savoir la démontrer mais je n'ai pas idée de comment faire, je pense que c'est par récurrence mais pas sûr. Je vais essayer d'expliciter le problème avec mes mots j'espère que vous me comprendrez, je reprends doucement les maths niveau lycée. Peut-être que c'est complètement trivial j'en sais rien donc je vous pose le problème ici comme je l'ai déjà fait pour d'autres problèmes.
---
Soit n un entier naturel finissant par 1 et dont l'avant dernier chiffre est impair. On prend tous les chiffres de n sauf le dernier (donc sauf 1). On obtient donc dans l'ordre les chiffres suivants : 1, 3, 5, 7, 9, 11, 13 etc On note ces chiffres n'.
On commence par retrancher 1 à 1 on obtient 0. On retranche ensuite 2 à 3 on obtient 1. On retranche 3 à 5 on obtient 2 etc. On associe donc à chaque chiffre n' un nombre à retrancher de plus en plus grand d'une unité à chaque fois et on obtient des nouveaux chiffres notés n''.
Ainsi par exemple on peut donner le tableau des premiers n, n' et n'' :
n = 11 ; n' = 1 ; n'' = 0
n = 31 ; n' = 3 ; n'' = 1
n = 51 ; n' = 5 ; n'' = 2
n = 71 ; n' = 7 ; n'' = 3
n = 91 ; n' = 9 ; n'' = 4
n = 111 ; n' = 11 ; n'' = 5
etc.
Ensuite on définit sigma(3*n+2) comme étant la somme des diviseurs de 3*n+2 (3*n+2 inclus).
On calcule ensuite le reste de la division de sigma(3*n+2)-2 par n+2 et si le résultat est de la forme 12*n''+7 alors 12*n''+7 est un nombre premier.
Par exemple si on prend n = 1031 on a n' = 103 et n'' = 51
On calcule ensuite le reste de la division de sigma(3*1031+2)-2 par 1033 et le résultat vaut 619. Or 619 est bien de la forme 12*n''+7 car on a 619 = 12*51+7. Donc 619 est un nombre premier.
Bonjour ! Tu pourrais simplifier l'algorithme ! Pour tout m entier naturel :
n" = m
n' = 2m + 1
n = 20m + 11
On calcule le reste de la division de σ(60m + 35)-2 par 20m + 13.
Si le résultat est de la forme 12k + 7 alors c'est un nombre premier.
Par exemple si on prend k = 51, on a n" = 51, n' = 103 et n = 1031. On calcule ensuite le reste de la division de σ(3095)-2 par 1033. Etc.
Je ne maîtrise pas la fonction σ donc je ne pourrai pas t'aider, j'intervenais juste pour simplifier l'algorithme (surtout le début), histoire que les calculs ne soit pas cachés dans des choses inutilement compliquées.
Dans un premier temps il faut que tu changes de point de vue. Il ne faut jamais dire :
Craw a écrit:
[...]
Je suis tombé sur une formule qui génère les nombres premiers de la forme 12k+7 dans l'ordre. J'aimerais bien savoir la démontrer mais je n'ai pas idée de comment faire, je pense que c'est par récurrence mais pas sûr.
[...]
Il faut toujours penser «je conjecture que l'algorithme suivant donne tous les nombres premiers de la forme 12k+7 en ordre croissant, j'essaye de démontrer cette conjecture.» Ça peut paraître ridicule mais il faut toujours commencer par penser ne pas avoir trouvé.
Ensuite, il va falloir (par rapport à tes messages précédents) acquérir le jargon et la manière de présenter pour que ce soit plus simple pour nous de te comprendre. Robun a commencé à te montrer comment tu aurais pu/du le faire. Mais pour faire cela il faut que tu repense ce que tu as fait.
Par exemple quand tu nous montres :
Craw a écrit:
[...] n = 11 ; n' = 1 ; n'' = 0
n = 31 ; n' = 3 ; n'' = 1
n = 51 ; n' = 5 ; n'' = 2
n = 71 ; n' = 7 ; n'' = 3
n = 91 ; n' = 9 ; n'' = 4
n = 111 ; n' = 11 ; n'' = 5
etc.
[...]
Tu peux t'apercevoir assez aisément que la liste des nombres de gauche est obtenue en ajoutant 20 au précédent, le premier étant 11. Cela signifie que pour obtenir le second tu ajoutes 1 fois 20 à 11, pour obtenir le troisième tu ajoutes 2 fois 20 à 11, etc. Tu peux également remarquer que le premier est tout simplement 11 auquel tu ajoutes 0 fois 20 … Plus techniquement tu as une suite arithmétique de premier terme 11 et de raison 20 ⇒ uₙ₊₁ = uₙ + 20, u₀=11 ; soit uₙ = 20n+11. Il faut que tu te familiarise avec ces notions pour les voir immédiatement, c'est assez aisé.
Tu poursuis en proposant de construire un nombre p = (𝝈( 3 uₙ + 2 ) - 2) % ( uₙ + 2 ).
Ensuite ce n'est pas hyper clair mais je comprends que tu proposes que p = 12n+7 ⇒ 12n+7 premier.
Donc du coup la première des choses à faire est de tester ça, déjà pour voir. Ta conjecture tient le coup pour n≤500.000
Les as-tu tous ? presque, il te manque le 7 (j'ai cherché les uₙ jusqu'à n=500000), mais passons ce détail.
Regardons 𝝈( 3 uₙ + 2 ) de plus près. Si on développe on obtient 𝝈( 3 (20n+11) + 2 ) = 𝝈( 60n + 35 ) = 𝝈( 5( 12n+7 ) )
À partir de là tu as deux cas possibles : soit 12n+7 est premier et tu auras 𝝈( 3 uₙ + 2 ) - 2 = 𝝈(5)𝝈(12n+7) - 2 = 6 (12n+8) - 2 = 72n+46 et tu continues le raisonnement … 72n+46=3*(20n+13)+12n+7 donc 72n+46 % 20n+13 = 12n+7 ⇒ qui est premier
soit 12n+7 n'est pas pas premier … mais est premier avec 5 auquel cas on a toujours 𝝈( 3 uₙ + 2 ) - 2 = 𝝈(5)𝝈(12n+7) mais reste à prouver que dans ce cas on obtient jamais 12n+7
soit 12n+7 n'est pas premier et est un multiple de 5, et on se relance dans un raisonnement similaire.
Donc oui, a priori, ta conjecture semble avérée et prouvable (avec un peu d'effort).
Une conjecture demeure une conjecture tant qu'elle n'est pas prouvée ou contredite. Si je comprend bien, n" = n/10 et n"" = n" / 2 ? Donc, n"" = n / 20 Et la fonction sigma(k) est la somme des diviseurs de k en incluant 1 et k lui-même ? Je dois vérifier: (sigma(3*n+2)-2) % (n+2) == 12*n"" + 7 (sigma(3*n+2)-2) % (n+2) == 12*(n/20) + 7 (sigma(3*n+2)-2) % (n+2) == 6*(n/10) + 7 <= simplification pas possible Dites-moi si je me suis trompé. Si je veux essayer de conttredire plutôt que prouver, je devrai tester toutes les valeurs valides de n. Soit 11 + k*20 pour 0 <= k Deux choses prendront du temps à être évaluer: + Évaluer sigma pour chaque nombre concerné. + Vérifier que le reste est un nombre premier. Je ne sais pas trop comment optimiser le calcul des sigma. Cependant, si j'ai assez de mémoire, je peux calculer tous les nombres premiers avec le crible d'Ératosthène. Si on ne fait que ça, c'est passablement rapide comparé aux autres méthodes. Je n'aurai qu'à indexer dans la table obtenue pour savoir si le nombre est premier.
edit: Le reste doit absolument être de la forme 12*(n/20)+7 (division entière) Voici du code en C pour trouver les diviseurs d'un nombre: - #include <stdio.h> #include <math.h> int sigma(int number) { int sum = 1 + number; int root =sqrt(number + 0.5); for(int divisor = 2; divisor <= root; divisor++) { if(number % divisor ==0) sum += divisor + number/divisor; } if(number == root*root) sum -= root; return sum; } int main(void) { int n; puts("Entrez un nombre "); scanf("%d", &n); printf("%d\n", sigma(n)); }
-
re-edit:
J'ai écrit le code de test au complet. Je pourrait donner le code au besoin.
La conjecture est vérifiée jusqu'à n = 500 millions.
Il restera à le prouver ...
- Edité par PierrotLeFou 26 mai 2022 à 1:34:03
Le Tout est souvent plus grand que la somme de ses parties.
Je reviens vers vous, je me suis penché sur ton raisonnement White Crow et j'essaye de le comprendre. Je te tiens au courant si j'ai des questions. Merci à toi en tout cas.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.go.yj.fr
Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.go.yj.fr
Le Tout est souvent plus grand que la somme de ses parties.
Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.go.yj.fr