Nombres premiers : Jeu recto-verso
Nombres premiers : Jeu recto-verso
C'est un jeu qui concerne les nombres premiers. Je l'ai baptisé recto-verso.
Imaginez un tableau d'une ligne et à n colonnes. Dans chacune des cases est déposé un pion. Sur chacun des pions vous pouvez inscrire un chiffre au recto et un autre au verso de manière telle que si vous retournez un ou deux ou trois ou n pions, le nombre composé de ces n pions soit toujours un nombre premier.
Je prendrai un nombre à 2 chiffres pour illustrer. Donc n=2.
En écrivant :
1 au verso et 3 sur le premier pion
1 au verso et 7 sur le second pion
j'obtiens les 4 possibilités suivantes :
1 et 1 ( 11 est premier)
1 et 7 ( 17 est premier)
3 et 1 ( 31 est premier)
3 et 7 ( 37 est premier)
On peut donc avec un nombre de n chiffres (soit 2*n recto + verso) reproduire 2^n nombres premiers.
Si n=30
avec une base de 60 chiffres
on peut générer 2^30 = 1.073.741.824 nombres premiers.
Mes questions sont :
1. Quel est le plus grand nombre à n chiffres que l'on peut obtenir?
2. Le nombre n peut-il être infini ou a-t-il une limite?
Imaginez un tableau d'une ligne et à n colonnes. Dans chacune des cases est déposé un pion. Sur chacun des pions vous pouvez inscrire un chiffre au recto et un autre au verso de manière telle que si vous retournez un ou deux ou trois ou n pions, le nombre composé de ces n pions soit toujours un nombre premier.
Je prendrai un nombre à 2 chiffres pour illustrer. Donc n=2.
En écrivant :
1 au verso et 3 sur le premier pion
1 au verso et 7 sur le second pion
j'obtiens les 4 possibilités suivantes :
1 et 1 ( 11 est premier)
1 et 7 ( 17 est premier)
3 et 1 ( 31 est premier)
3 et 7 ( 37 est premier)
On peut donc avec un nombre de n chiffres (soit 2*n recto + verso) reproduire 2^n nombres premiers.
Si n=30
avec une base de 60 chiffres
on peut générer 2^30 = 1.073.741.824 nombres premiers.
Mes questions sont :
1. Quel est le plus grand nombre à n chiffres que l'on peut obtenir?
2. Le nombre n peut-il être infini ou a-t-il une limite?
Pour n=3, il y a 12 possibilités :
011 337 [11, 17, 31, 37, 311, 317, 331, 337]
053 379 [53, 59, 73, 79, 353, 359, 373, 379]
053 389 [53, 59, 83, 89, 353, 359, 383, 389]
073 389 [73, 79, 83, 89, 373, 379, 383, 389]
013 647 [13, 17, 43, 47, 613, 617, 643, 647]
013 659 [13, 19, 53, 59, 613, 619, 653, 659]
023 859 [23, 29, 53, 59, 823, 829, 853, 859]
101 439 [101, 109, 131, 139, 401, 409, 431, 439]
101 499 [101, 109, 191, 199, 401, 409, 491, 499]
131 499 [131, 139, 191, 199, 431, 439, 491, 499]
103 599 [103, 109, 193, 199, 503, 509, 593, 599]
541 977 [541, 547, 571, 577, 941, 947, 971, 977]
Par contre pour n=4, 5, 6 ou 7, ce n'est pas possible.
011 337 [11, 17, 31, 37, 311, 317, 331, 337]
053 379 [53, 59, 73, 79, 353, 359, 373, 379]
053 389 [53, 59, 83, 89, 353, 359, 383, 389]
073 389 [73, 79, 83, 89, 373, 379, 383, 389]
013 647 [13, 17, 43, 47, 613, 617, 643, 647]
013 659 [13, 19, 53, 59, 613, 619, 653, 659]
023 859 [23, 29, 53, 59, 823, 829, 853, 859]
101 439 [101, 109, 131, 139, 401, 409, 431, 439]
101 499 [101, 109, 191, 199, 401, 409, 491, 499]
131 499 [131, 139, 191, 199, 431, 439, 491, 499]
103 599 [103, 109, 193, 199, 503, 509, 593, 599]
541 977 [541, 547, 571, 577, 941, 947, 971, 977]
Par contre pour n=4, 5, 6 ou 7, ce n'est pas possible.
Est-ce que tu as utilisé un programme pour dire que ce n'est pas possible au-delà de n=3?linfir a écrit :Pour n=3, il y a 12 possibilités :
011 337 [11, 17, 31, 37, 311, 317, 331, 337]
053 379 [53, 59, 73, 79, 353, 359, 373, 379]
053 389 [53, 59, 83, 89, 353, 359, 383, 389]
073 389 [73, 79, 83, 89, 373, 379, 383, 389]
013 647 [13, 17, 43, 47, 613, 617, 643, 647]
013 659 [13, 19, 53, 59, 613, 619, 653, 659]
023 859 [23, 29, 53, 59, 823, 829, 853, 859]
101 439 [101, 109, 131, 139, 401, 409, 431, 439]
101 499 [101, 109, 191, 199, 401, 409, 491, 499]
131 499 [131, 139, 191, 199, 431, 439, 491, 499]
103 599 [103, 109, 193, 199, 503, 509, 593, 599]
541 977 [541, 547, 571, 577, 941, 947, 971, 977]
Par contre pour n=4, 5, 6 ou 7, ce n'est pas possible.
Entre le nombre 1000 et le nombre 9999, il y a 1061 nombres premiers et je serais étonné de ne pas voir un ensemble de 16 nombres premiers remplissant les conditions citées ci-dessus.
Je m'attendais à un n limite vu la raréfaction des nombres premiers quand le nombre à n chiffres devient grand mais pas à n=4.
Je m'attendais à un n limite vu la raréfaction des nombres premiers quand le nombre à n chiffres devient grand mais pas à n=4.
Pour faire un test exhaustif de n=4 il faut au plus 5832000 tests en utilisant un algo brutomnibus a écrit :Si je comprends bien, il faut évaluer toutes les possibilités possibles avec les chiffres pour retenir seulement celles qui ne génèrent que des nombres premiers ? mais c'est super long !
A moins que je ne comprenne pas... HELP PLEASE ! :helpsmilie:
Pour les 3 premiers pions il y a 45 couples à tester par pions :
Combinaisons de 2 parmi 10 (0,1,2,3,....8,9)
Ça fait 45*45*45 = 91125
le dernier pion 4 possibilités 1,3,7.9
Ça fait 91125*4= 364500
Et pour chacune des combinaisons : 16 cas à vérifier (en théorie) car si le premier cas n'est pas premier on arrête et on teste le suivant
Au plus 364500*16= 5832000
Avec un programme brut le traitement prendrait moins d'une minute (la fonction "isprime" existe dans tous les langages)
Ps : je ne suis pas programmeur.
Il est plus efficace de précalculer la liste des nombres premiers.
Prenons $n=4$ par exemple.
On établit la liste de tous les nombres premiers inférieurs à 10000.
Pour chaque paire de chiffres $(i,j)$, on trouve rapidement tous les nombres de trois chiffres $abc$ tels que $iabc$ et $jabc$ sont dans la liste, et on recommence.
Le problème, c'est qu'il faut beaucoup de mémoire pour $n>8$.
Prenons $n=4$ par exemple.
On établit la liste de tous les nombres premiers inférieurs à 10000.
Pour chaque paire de chiffres $(i,j)$, on trouve rapidement tous les nombres de trois chiffres $abc$ tels que $iabc$ et $jabc$ sont dans la liste, et on recommence.
Le problème, c'est qu'il faut beaucoup de mémoire pour $n>8$.
Il n'est pas encore prouvé qu'il n'y a pas de solution pour n=4.omnibus a écrit :Si j'ai bien compris la règle ne s'applique plus à partir de n=4 , mais n'est-ce pas un peu rapide ? :(On peut donc avec un nombre de n chiffres (soit 2*n recto + verso) reproduire 2^n nombres premiers.
Ceci dit, rien n'empêche qu'il y ait une solution pour un nombre n assez grand.
Si tel est le cas avec n = 62 par exemple, une telle formule serait une bizarrerie car avec 124 nombres on pourrait engendrer 2 puissance 62 nombres premiers, soit plus de 4 milliards de milliards (4.611.686.018.427.387.904).
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Ton copain ne s'appelerait pas Pierre de F.....cerise a écrit :Mon copain a montré (au brouillon) que ce n'est pas possible pour $n\geq 9$ je crois, mais il n'a pas rédigé proprement sa démonstration...
Bon allez, je
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Euh, comme il ne l'a pas rédigée, ce n'est pas facile... Il a gribouillé un peu sur un morceau de papier (non, pas dans une marge ;-)), et il s'est dit que ça devait marcher, mais il n'est pas allé plus loin...
Il fallait être Newton pour apercevoir que la Lune tombe quand tout le monde voit bien qu'elle ne tombe pas.
Paul Valéry
Paul Valéry
En fait, je montre que ça ne marche pas à partir de n=11. Pour cela, je note a_i et b_i les chiffres écrits respectivement au resto et au verso de la i-ième pièce et je définis $S_i = \{(-1)^i a_i, (-1)^i b_i\} \subset \mathbb Z/11\mathbb Z$. Puisque les chiffres écrits sont clairement compris entre 0 et 9, les S_i sont tous de cardinal 2.
Maintenant j'ai besoin du lemme suivant : Soit S une partie non vide de $\mathbb Z / p \mathbb Z$ (en pratique on aura p=11, mais ça marche pour n'importe quel nombre premier p) de cardinal n<p, et T une partie de $\mathbb Z / p \mathbb Z$ de cardinal 2. Alors S+T (l'ensemble des sommes d'un élément de S et d'un élément de T) compte au moins n+1 éléments.
Prouvons le lemme. Soient a et b les deux éléments de T. Comme S+T est inclus dans S+{a}, il est au moins de cardinal n. Supposons qu'il soit exactement de cardinal n. Cela entraine que pour tout $s \in S$, il existe $s' \in S$ tel que s+a = s'+b. Autrement dit, S est stable par addition de b-a. Comme p est premier, et que $b \not \equiv a \pmod p$, S est nécessairement égal à tout $\mathbb Z / p \mathbb Z$, ce que j'ai exclu dans l'énoncé.
Bien, utilisons maintenant le lemme avec nos ensembles S_i. Par récurrence directe, on montre que le cardinal de la somme $S_1 + S_2 + \ldots + S_{10}$ est tout $\mathbb Z / 11 \mathbb Z$. Par ailleurs, on sait que le nombre $c_1c_2\ldots c_n$ est multiple de 11 si et seulement si la somme alternée de ses chiffres l'est. Il s'ensuit que quelle que soit la position du pion donnant le chiffre de gauche, il est possible de placer les autres de façon à obtenir un multiple de 11. Et bien sûr, puisque l'on a deux choix pour le chiffre de gauche, on peut s'arranger pour que celui-ci ne soit pas 0. Ainsi on peut toujours écrire un nombre qui est à la fois un multiple de 11 et qui commence par autre chose qu'un 0 ; ce nombre n'est évidemment pas premier.
--
Pierre de Fermat.
Maintenant j'ai besoin du lemme suivant : Soit S une partie non vide de $\mathbb Z / p \mathbb Z$ (en pratique on aura p=11, mais ça marche pour n'importe quel nombre premier p) de cardinal n<p, et T une partie de $\mathbb Z / p \mathbb Z$ de cardinal 2. Alors S+T (l'ensemble des sommes d'un élément de S et d'un élément de T) compte au moins n+1 éléments.
Prouvons le lemme. Soient a et b les deux éléments de T. Comme S+T est inclus dans S+{a}, il est au moins de cardinal n. Supposons qu'il soit exactement de cardinal n. Cela entraine que pour tout $s \in S$, il existe $s' \in S$ tel que s+a = s'+b. Autrement dit, S est stable par addition de b-a. Comme p est premier, et que $b \not \equiv a \pmod p$, S est nécessairement égal à tout $\mathbb Z / p \mathbb Z$, ce que j'ai exclu dans l'énoncé.
Bien, utilisons maintenant le lemme avec nos ensembles S_i. Par récurrence directe, on montre que le cardinal de la somme $S_1 + S_2 + \ldots + S_{10}$ est tout $\mathbb Z / 11 \mathbb Z$. Par ailleurs, on sait que le nombre $c_1c_2\ldots c_n$ est multiple de 11 si et seulement si la somme alternée de ses chiffres l'est. Il s'ensuit que quelle que soit la position du pion donnant le chiffre de gauche, il est possible de placer les autres de façon à obtenir un multiple de 11. Et bien sûr, puisque l'on a deux choix pour le chiffre de gauche, on peut s'arranger pour que celui-ci ne soit pas 0. Ainsi on peut toujours écrire un nombre qui est à la fois un multiple de 11 et qui commence par autre chose qu'un 0 ; ce nombre n'est évidemment pas premier.
--
Pierre de Fermat.
-
- Sujets similaires
- Réponses
- Vues
- Dernier message