Nombres premiers : Jeu recto-verso

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Algibri

Nombres premiers : Jeu recto-verso

Message non lu par Algibri »

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?
Algibri

Suite

Message non lu par Algibri »

Le cas n=3

Pion 1 : recto 1 verso 4
Pion 2 : recto 0 verso 9
Pion 3 : recto 1 verso 9

8 nombres premiers

101
109
191
199
401
409
491
499

Qui veut essayer de trouver soit un autre cas n=3 ou mieux n=4?
omnibus

Message non lu par omnibus »

Juste une question : comment choisit-on les chiffres qui sont sur les rectos et versos ? :?:
Le_golbarg

Message non lu par Le_golbarg »

C'est a toi des les trouver. Chuis en train de programmer le truc, c'est un peut long...
Algibri

Message non lu par Algibri »

Le_golbarg a écrit :C'est a toi des les trouver. Chuis en train de programmer le truc, c'est un peut long...
Ce sera un formidable exercice de programmation.
Impatient de voir les résultats.

Merci de les publier
linfir

Message non lu par linfir »

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.
Algibri

Message non lu par Algibri »

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.
Est-ce que tu as utilisé un programme pour dire que ce n'est pas possible au-delà de n=3?
Algibri

Message non lu par Algibri »

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.
omnibus

Message non lu par omnibus »

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 ? :shock: mais c'est super long !
A moins que je ne comprenne pas... HELP PLEASE ! :helpsmilie:
Algibri

Message non lu par Algibri »

omnibus 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 ? :shock: mais c'est super long !
A moins que je ne comprenne pas... HELP PLEASE ! :helpsmilie:
Pour faire un test exhaustif de n=4 il faut au plus 5832000 tests en utilisant un algo brut

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.
linfir

Message non lu par linfir »

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$.
omnibus

Message non lu par omnibus »

On peut donc avec un nombre de n chiffres (soit 2*n recto + verso) reproduire 2^n nombres premiers.
Si j'ai bien compris la règle ne s'applique plus à partir de n=4 :?: , mais n'est-ce pas un peu rapide ? :(
Algibri

Message non lu par Algibri »

omnibus a écrit :
On peut donc avec un nombre de n chiffres (soit 2*n recto + verso) reproduire 2^n nombres premiers.
Si j'ai bien compris la règle ne s'applique plus à partir de n=4 :?: , mais n'est-ce pas un peu rapide ? :(
Il n'est pas encore prouvé qu'il n'y a pas de solution pour n=4.
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).
Le_golbarg

Message non lu par Le_golbarg »

Comme toute les possibilité ont été testé pour $n=4$, on a prouvé que ce n'etait pas possible.
cerise
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 447
Inscription : mercredi 08 juin 2005, 18:03
Contact :

Message non lu par cerise »

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...
Il fallait être Newton pour apercevoir que la Lune tombe quand tout le monde voit bien qu'elle ne tombe pas.
Paul Valéry
guiguiche
Modérateur général
Modérateur général
Messages : 8191
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans
Contact :

Message non lu par guiguiche »

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...
Ton copain ne s'appelerait pas Pierre de F..... :lol:
Bon allez, je :arrow:
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.
omnibus

Message non lu par omnibus »

Pourrait-on voir cette démonstration ( du copain de cerise, ou, si j'ai bien compris, de Fermat) ? Merci d'avance ... :?:
cerise
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 447
Inscription : mercredi 08 juin 2005, 18:03
Contact :

Message non lu par cerise »

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
omnibus

Message non lu par omnibus »

Et pour la démonstration de Fermat ? Merci d'avance...
xavier

Message non lu par xavier »

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.
Répondre
  • Sujets similaires
    Réponses
    Vues
    Dernier message