Nombres premiers : Jeu recto-verso

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

Nombres premiers : Jeu recto-verso

Messagepar Algibri » Mercredi 06 Juin 2007, 21:15

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
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Publicité

Suite

Messagepar Algibri » Jeudi 07 Juin 2007, 17:50

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?
Algibri
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar omnibus » Vendredi 08 Juin 2007, 17:20

Juste une question : comment choisit-on les chiffres qui sont sur les rectos et versos ? :?:
Ne jamais juger sans connaître...
omnibus
Déca-utilisateur
 
Messages: 12
Inscription: Mardi 03 Avril 2007, 13:18

Messagepar Le_golbarg » Vendredi 08 Juin 2007, 17:45

C'est a toi des les trouver. Chuis en train de programmer le truc, c'est un peut long...
Le_golbarg
Déca-utilisateur
 
Messages: 28
Inscription: Vendredi 27 Avril 2007, 15:09

Messagepar Algibri » Vendredi 08 Juin 2007, 21:22

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
Algibri
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar linfir » Vendredi 08 Juin 2007, 23:42

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.
linfir
Déca-utilisateur
 
Messages: 36
Inscription: Jeudi 08 Décembre 2005, 22:25

Messagepar Algibri » Samedi 09 Juin 2007, 00:47

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
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar Algibri » Dimanche 10 Juin 2007, 00:56

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.
Algibri
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar omnibus » Mardi 12 Juin 2007, 14:11

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:
Ne jamais juger sans connaître...
omnibus
Déca-utilisateur
 
Messages: 12
Inscription: Mardi 03 Avril 2007, 13:18

Messagepar Algibri » Mardi 12 Juin 2007, 15:30

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.
Algibri
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar linfir » Mardi 12 Juin 2007, 15:57

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$.
linfir
Déca-utilisateur
 
Messages: 36
Inscription: Jeudi 08 Décembre 2005, 22:25

Messagepar omnibus » Vendredi 15 Juin 2007, 09:15

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 ? :(
Ne jamais juger sans connaître...
omnibus
Déca-utilisateur
 
Messages: 12
Inscription: Mardi 03 Avril 2007, 13:18

Messagepar Algibri » Vendredi 15 Juin 2007, 17:17

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).
Algibri
Hecto-utilisateur
 
Messages: 82
Inscription: Dimanche 04 Février 2007, 01:32

Messagepar Le_golbarg » Vendredi 15 Juin 2007, 21:33

Comme toute les possibilité ont été testé pour $n=4$, on a prouvé que ce n'etait pas possible.
Le_golbarg
Déca-utilisateur
 
Messages: 28
Inscription: Vendredi 27 Avril 2007, 15:09

Messagepar cerise » Dimanche 17 Juin 2007, 09:05

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
cerise
Méga-utilisateur
 
Messages: 448
Inscription: Mercredi 08 Juin 2005, 17:03
Statut actuel: Actif et salarié

Messagepar guiguiche » Dimanche 17 Juin 2007, 11:00

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.
guiguiche
Modérateur
 
Messages: 8062
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Messagepar omnibus » Lundi 18 Juin 2007, 10:17

Pourrait-on voir cette démonstration ( du copain de cerise, ou, si j'ai bien compris, de Fermat) ? Merci d'avance ... :?:
Ne jamais juger sans connaître...
omnibus
Déca-utilisateur
 
Messages: 12
Inscription: Mardi 03 Avril 2007, 13:18

Messagepar cerise » Lundi 18 Juin 2007, 15:18

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
cerise
Méga-utilisateur
 
Messages: 448
Inscription: Mercredi 08 Juin 2005, 17:03
Statut actuel: Actif et salarié

Messagepar omnibus » Vendredi 22 Juin 2007, 08:44

Et pour la démonstration de Fermat ? Merci d'avance...
Ne jamais juger sans connaître...
omnibus
Déca-utilisateur
 
Messages: 12
Inscription: Mardi 03 Avril 2007, 13:18

Messagepar xavier » Vendredi 22 Juin 2007, 15:56

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.
xavier
Déca-utilisateur
 
Messages: 20
Inscription: Dimanche 12 Mars 2006, 10:46
Localisation: Rennes

Suivante

Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 2 invités