Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Combien sur 21 ?

Posté par
littleguy
22-07-15 à 13:35

Bonjour à tous,

Voici une grille 5x5 où chaque case ne contient qu'un chiffre.

Au bout de chaque ligne et en bas de chaque colonne on a écrit en rouge les nombres formés par les six chiffres de la ligne ou de la colonne,  en bleu la somme des chiffres de la ligne ou de la colonne.
En bas à droite et en vert figure la somme de tous les chiffres de la grille. (Pardon pour les daltoniens, j'espère que le texte suffira à la compréhension.)

Combien sur 21 ?

On a donc ainsi vingt-et-un nombres.
Parmi eux il n'y a que six nombres premiers distincts : 17, 19, 23, 31, 48029, 72271.

Sachant que la ligne I et la colonne A ne doivent pas contenir le chiffre 0 et que chaque case ne doit contenir qu'un chiffre on voudrait remplir cette grille de telle sorte que sur les vingt-et-un nombres il y ait un maximum de nombres premiers distincts.

Quelle grille proposez-vous ?

Vous pourrez présenter votre grille sous forme simplifiée et indiquer votre score, par exemple pour celle donnée ci-dessus :
22177
48029
87628
90779
17316
Score : 6 sur 21

Merci pour votre éventuelle participation.

Posté par
jarod128
re : Combien sur 21 ? 22-07-15 à 20:46

perduBonjour et merci pour l'énigme.
On montre facilement que 21 est impossible. Je n'ai pas trouvé avec 20 alors je poste une solution avec 19 nombres premiers distincts:

42467
94789
31139
65497
71399

Score: 19 sur 21

PS: j'ai utilisé python avec une partie en recherche aléatoire.
J'espère qu'on ne peut pas faire 20!

Posté par
masab
re : Combien sur 21 ? 23-07-15 à 20:15

gagnéBonjour littleguy,


Je propose la grille écrite sous forme simplifiée :

11113
13007
13001
79939
77999
Score : 21 sur 21

Liste des 21 nombres premiers distincts obtenus :
[5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 101, 10039, 10099, 11113, 11177, 13001, 13007, 13397, 37199, 77999, 79939]

Merci pour cette énigme originale et assez difficile !

Posté par
Nofutur2
re : Combien sur 21 ? 23-07-15 à 20:30

gagnéMerci pour cette énigme "gourmande" en heures de traitement..
Je trouve :
11113
12107
10301
93979
77999
avec un score de 21/21....

Posté par
jarod128
re : Combien sur 21 ? 24-07-15 à 12:28

perduBonjour,
je sais déjà que je vais avoir un poisson puisque j'ai trouvé mieux.
En améliorant mon algorithme, j'ai un bon paquet de grilles avec 20 nombres premiers distincts et un 21ème nombre premier mais déjà utilisé.
J'en poste une:
44111
98011
89381
19001
11173
Score: 20 sur 21
Remarque: Autre erreur dans ma première intervention: je n'ai pas démontré qu'un score de 21 était impossible.

Posté par
sarriette84
re : Combien sur 21 ? 24-07-15 à 14:03

perduBon ca sent le poisson mais je me lance quand même:
11113
11119
11719
13151
71797

ce qui fait 15/21

D'après moi (et une démonstration plus que douteuse) il est mathématiquement impossible de dépasser 19/21. En tâtonnant je ne trouve pas mieux que 15, on verra bien.
Merci pour cette énigme pas vraiment évidente.

Posté par
torio
re : Combien sur 21 ? 24-07-15 à 22:39

perdu
11113
10037
10039
39799
19973  

Score 20 sur 21

les 20 nombres premiers :

7, 11, 13, 17, 19, 23, 29, 31, 37, 97, 10037, 10039, 10079, 10099, 11113, 11131, 13397, 19973, 37993, 39799


A+
Torio

Posté par
manitoba
re : Combien sur 21 ? 25-07-15 à 21:44

perduBonjour littleguy,

Je propose le score ridicule de : 16 sur 21 avec la grille
39979
10301
10321
10163
77999
utilisant les nombres premiers
5,7,11,13,23,37,41,101,
10163,10301,10321,39979,77999,90007,91139 et 93319.
Merci pour l'énigme.

Posté par
janpawel
score 19 sur 21 26-07-15 à 10:46

perdupas trouvé mieux

11113
10103
17137
12149
39937

Score 19 sur 21

Posté par
rschoon
re : Combien sur 21 ? 26-07-15 à 13:56

perduBonjour à tous.

Je propose l'une des très nombreuses solutions valant 20 :
11113
10037
11119
76079
19373
Score : 20

Il n'y a pas de solution à 21 : on établit la liste de tous les quintets de nombres premiers différents et inférieurs à 45 (maximum de la somme des 5 chiffres d'un nombre) et dont la somme est un nombre premier. Si l'on essaie de former des couples de ces quintets n'ayant pas d'éléments communs et dont la somme est le même nombre premier, on constate qu'il n'y a que 9 solutions. Toutes ces solutions contiennent le nombre 3. Or il n'existe pas de nombre premier à 5 chiffres dont la somme des chiffres vaut 3.

Merci pour l'énigme

Posté par
Livia_C
re : Combien sur 21 ? 27-07-15 à 20:38

perduBonjour,    
    11113
    10037
    10211
    39799
    77999,
Score 21 sur 21.
Merci pour l'énigme

Posté par
emeu
re : Combien sur 21 ? 31-07-15 à 20:49

perduHello les mathiliens,

Je viens faire un tour sur le site après 10 ans d'absence,
et je tombe sur cette énigme vraiment chouette. Je ne me rappelle plus
de mon pseudo de l'époque donc j'ai créé un nouveau compte pour pouvoir contribuer.

Voici ma proposition :
21211
75821    
31511    
27901    
93719    
score: 20 sur 21

J'ai parlé de l'énigme à un collègue qui a réussi à énumérer tous les carrés de score 21
En voici un :

  41411
  10501
  10301
  89897
  93997
score: 21 sur 21

Il a réussi à calculer qu'il y a exactement 8352 carrés de score 21.

Merci pour l'énigme !
Et ca fait vraiment plaisir de voir que les énigmes et le forum sont toujours actifs 10 ans plus tard .

Mes amitiés à l'île,
emeu

Posté par
dpi
re : Combien sur 21 ? 01-08-15 à 15:30

perduBonjour,

C'est certainement le plus gros casse-tête
et grand merci pour les journées pluvieuses...

Ayant trouvé successivement 17,18,19 et 20
j'ai vainement tenté 21...

Bravo aux trouveurs.

Combien sur 21 ?

Posté par
JoseManuel
re : Combien sur 21 ? 02-08-15 à 19:07

perduBien que je ne soit pas sur ma meilleure grille est :

4 5 1 6 1
9 0 9 0 1
4 8 9 9 1
3 3 3 1 1
3 3 7 7 3

Score 18

Les 21 nombres sont premiers mais il y a seulement 18 distincts.

Posté par
noszeros
re : Combien sur 21 ? 02-08-15 à 22:45

perduBonjour,

Je propose la grille:
9.    6.    3.    2.    9.  
1.    1.    9.    5.    3.  
6.    3.    7.    6.    1.  
2.    6.    2.    0.    9.  
7.    1.    3.    3.    9.  

Score: 13 sur 21

Posté par
LittleFox
re : Combien sur 21 ? 07-08-15 à 14:17

perduJe propose la grille :

42979
79979
11423
20807
91711


On obtient avec elle 19 nombres premiers distincts : 11,13,17,19,23,29,31,37,41,11423,20807,29101,42979,47129,77201,79979,91711,99371 et 99487.

Je pense qu'on ne peut pas avoir une grille avec 21 nombres premiers distincts. Puisque la somme de tous les chiffres devrait être  un nombre premier > 9, elle est impaire. Cette somme est aussi la somme des sommes des lignes et des colonnes. Il y a 10 lignes + colonnes donc au moins la somme d'une ligne ou d'une colonne doit valoir 2. Or il n'existe pas de nombre premier > 10000 dont la somme des chiffres vaut 2.

J'ai trouvé beaucoup de grilles avec un score de 19 (on commence par la ligne et la colonne du fond, puis les premières, puis on rempli le reste) mais encore aucune avec un score de 20 et mon algorithme tourne depuis quelques heures. Je tente donc une solution avec un score de 19. Chapeau à ceux qui ont un score de 20, ce n'était pas un problème facile (ou bien j'ai loupé quelque chose ce qui est très possible ^^).

Posté par
mdr_non
re : Combien sur 21 ? 10-08-15 à 08:42

perdubonjour : )

super énigme merci,
je pense qu'il y en a plus mais je m'arrête à :

19759
49999
69991
89989
91711
score : 16/21

les nombres premiers sont : {19, 29, 31, 37, 41, 43, 167, 19759, 49999, 59981, 69991, 79997, 89989, 91711, 99191, 99991}

Posté par
mdr_non
re : Combien sur 21 ? 10-08-15 à 16:13

perdudommage : )
j'en ai trouvé plusieurs avec 18/21

14783
30011
50417
86869
93739
score : 18/21

les nombres premiers sont :
{ 14783 30011 50417 86869 93739 |
23 5 17 37 31 |
113 |
# 40063 70487 81163 31799 |
# 13 # 19 29 }

Posté par
littleguy
re : Combien sur 21 ? 17-08-15 à 13:20

Bravo à masab et nofutur2 !

Quelques regrets pour emeu dont la proposition personnelle est 20/21 puis qui donne la réponse d'un collègue qui convient, elle.
D'ailleurs je suis en admiration devant les 8352 carrés annoncés de score 21 ! (je n'en avais que 4, élaborés "à la main" avec peine...)

Posté par
LittleFox
re : Combien sur 21 ? 18-08-15 à 14:20

perdu
Tout d'abord, grosse boulette dans ma démonstration de pourquoi on peut pas avoir 21 .

Ensuite, Emeu, je suis intéressé de savoir comment on peut les énumérer dans un temps raisonnable. Toute indication est la bienvenue .

Encore merci à Littleguy pour cette énigme bien corsée .

Posté par
mdr_non
re : Combien sur 21 ? 18-08-15 à 16:08

perdubonjour : )

Citation :
Ensuite, Emeu, je suis intéressé de savoir comment on peut les énumérer dans un temps raisonnable. Toute indication est la bienvenue .

+1, intéressé aussi : )




la méthode naïve que j'ai utilisée en C++ + OpenMP :

écrire dans un fichier la liste de tous les nombres premiers de 10000 à 99999 (triés par ordre croissant)
(on peut trouver une telle liste sur internet déjà sous format texte)

> créer un conteneur avec tous ces nombres premiers (ça nous fait un conteneur de 8363 entiers)
on peut prendre (un vector par exemple que l'on nomme v_rc_primes)
> créer un autre conteneur avec tous les nombres premiers de 2 à 450 (ça nous fait un conteneur de 87 entiers)
un autre vector que l'on nomme v_s_primes

et effectuer l'algorithme suivant :
> remplir les 5 lignes de notre tableau avec 5 entiers de v_rc_primes
> extraire les 21 nombres de ce tableau et les sauver dans un conteneur de type set
"le conteneur de type set nous permettra d'avoir des nombres distincts (de cette façon
à l'étape du stockage même on réussit à extraire l'ensemble des nombres distincts parmi les 21)"
    parmi les nombres à extraire (5 d'entre eux sont tout simplement les 5 extraits du conteneur de v_rc_primes, et ils sont premiers
    on a donc déjà 5 nombres premiers au compteur)
    ensuite on a à extraire uniquement : la somme de tous les chiffres du tableau,
    les nombres formés par les colonnes et la somme de leurs chiffres,
    et la somme des chiffres des lignes.
> si la taille de ce set n'est pas supérieure à (on va dire 15) on continue l'algorithme avec un autre ensemble de 5 entiers
"au début j'avais choisi quelque chose autour de 15 car on pouvait facilement construire un tableau avec 15 nombres premiers distincts..."
> à l'intérieur du set, compter le nombre de nombres premiers (en excluant les 5 déjà comptés précédemment) en utilisant une fonction qui va
prendre un nombre dans ce set et voir si ce nombre est présent dans les conteneurs v_s_primes ou v_rc_primes.

pour la recherche on pourra utiliser par exemple des algorithmes de type binary_search concernant v_rc_primes
(comme notre conteneur est déjà trié...)
et une recherche linéaire devrait être plus efficace sur v_s_primes comme il est tout petit

l'algorithme se déroulera pour toutes combinaisons de 5 entiers parmi les 8363 entiers de v_rc_primes
soit 3.4 1017 itérations,

aujourd'hui les processeurs 4 coeurs sont très communs, on peut en profiter en insérant au code quelques petites lignes pour paralléliser les boucles
cela nous permettra de partager le travail, 4.3 1016 itérations pour chacun des 8 threads

et à la fin on récupère le nombre de fois qu'on a obtenu le nombre maximum de nombres premiers (on sait que c'est 21 maintenant)

Posté par
emeu
re : Combien sur 21 ? 18-08-15 à 21:28

perduBonjour à tous,

Voici quelques infos sur la méthode utilisée par mon collègue pour énumérer toutes les grilles (j'espère ne pas me tromper car ça fait un moment).

On commence par énumérer les sommes possibles. Pour cela, on commence par faire la liste des premiers entre 10000 et 99999 dont la somme des chiffres est un nombre premier. Il y en a 3293.
Puis on regarde l'ensemble des sommes de chiffres de ces nombres, on en trouve seulement 12 possibles
{ 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 }

Comme on veut trouver des nombres premiers distincts, on cherche les paires de sous-ensembles de 5 éléments de cette liste qui donnent une somme totale qui est un nombre premier (on peut par exemple énumérer toutes les partitions de ces 12 en trois sous-ensembles de tailles 5,5,2, le nombre de cas à tester est 12!/5!/5!/2! = 16632).

Il ne reste alors que 139 possibilités pour les 11 sommes (si je me souviens bien, il y a aussi quelques cas qui peuvent être éliminés à la main).

Puis pour chacune de ces 139 possibilités, on bourrine .
il y a quelques optimisations possibles : par exemple dans le nombre de la colonne de droite ou la ligne du bas, il ne peut y avoir que les chiffres {1,3,7,9} qui apparaissent (à cause de la divisibilité par 2 ou par 5), ce qui ne laisse que 197 nombres premiers pour cette ligne et cette colonne. On commence donc par placer ceux-là, puis on complète le reste (le nombre de possibilités est normalement assez faible). Le fait que le problème est invariant par transposition permet également de diviser le nombre de cas à tester par 2.
Je ne sais pas si il y a des optimisations absolument nécessaires pour cette partie, je pourrai demander à mon collègue lorsque je le reverrai.

Au final, le nombre de cas à tester devient raisonnable, et un programme permet de finir le calcul.

Merci beaucoup pour l'énigme !

emeu

Posté par
mdr_non
re : Combien sur 21 ? 18-08-15 à 22:58

perdumerci emeu : )

écrit comme ça c'est vrai que c'est plus simple et plus rapide

Posté par
littleguy
re : Combien sur 21 ? 19-08-15 à 13:31

Ça me rassure un peu... La phrase :

Citation :
Il a réussi à calculer qu'il y a exactement 8352 carrés de score 21
m'avait laissé pantois ; je l'avais interprétée  comme ceci :  il y a 8352 solutions !!??

Posté par
emeu
re : Combien sur 21 ? 19-08-15 à 19:17

perduOui, c'est bien ça que je voulais dire : il y a 8352 solutions

Mon collègue m'a envoyé la liste mais elle fait 4176 lignes (modulo transposition), donc je ne peux pas vraiment la poster ici (est-ce qu'il y a un endroit où je peux l'uploader en respectant les règles du forum ?).
Voici quelques grilles (1 par ligne) si vous voulez vérifier que c'est correct.

emeu

[ 11131, 10103, 10037, 79889, 79399 ],
[ 11131, 11027, 77999, 11003, 79399 ],
[ 11131, 10091, 11003, 96989, 79399 ],
[ 11131, 11003, 10037, 96989, 79399 ],
[ 11131, 19001, 79979, 11003, 79939 ],
[ 11131, 79979, 19001, 11003, 79939 ],
[ 11131, 79979, 11003, 13007, 79939 ],
[ 11131, 79979, 13007, 11003, 79939 ],
[ 11311, 10211, 79997, 10631, 73999 ],
[ 11311, 10301, 12503, 77999, 73999 ],
[ 11311, 10211, 79979, 10613, 73999 ],
[ 11311, 77999, 12107, 10103, 73999 ],
[ 12211, 77999, 11801, 10103, 73999 ],
[ 11131, 11027, 73999, 11003, 77999 ],
[ 11131, 11003, 10037, 94789, 77999 ],
[ 11131, 11003, 10037, 98389, 77999 ],
[ 11131, 19001, 39979, 11003, 79979 ],
[ 11131, 19001, 79939, 11003, 79979 ],
[ 11131, 11003, 13007, 79399, 79979 ],
[ 11311, 79939, 12107, 10103, 77999 ],
[ 11311, 10211, 39979, 10613, 79979 ],
[ 11311, 10211, 79939, 10613, 79979 ],
[ 11261, 10141, 79997, 10211, 73999 ],
[ 11621, 10211, 79997, 10321, 73999 ],
[ 11621, 10301, 10303, 79889, 73999 ],
[ 11621, 10301, 79889, 10303, 73999 ],
[ 11621, 79979, 10211, 10303, 79939 ],
[ 12611, 10501, 11003, 77999, 73999 ],
[ 15131, 13001, 79979, 13003, 79939 ],
[ 11621, 10301, 10303, 97849, 79979 ],
[ 15131, 13001, 39979, 13003, 79979 ],
[ 15131, 13001, 79939, 13003, 79979 ]

Posté par
emeu
re : Combien sur 21 ? 19-08-15 à 19:28

perduSauf erreur, voilà la liste de toutes les grilles de score 21 (4176 + leur transposée).





emeu

Posté par
mdr_non
re : Combien sur 21 ? 19-08-15 à 19:32

perduoui on peut peut-être former 4176 grilles

mais que fait-on des permutations comme par exemple :
[93997,21101,30161,88997,11971],
[93997,30161,21101,88997,11971],

extrait de (part 2)

Posté par
mdr_non
re : Combien sur 21 ? 19-08-15 à 19:38

perduoups mon dernier message à annuler, sans aucun sens

Posté par
littleguy
re : Combien sur 21 ? 19-08-15 à 22:22

Trop fort !!

Posté par
LittleFox
re : Combien sur 21 ? 25-08-15 à 16:15

perduImpressionnant!

Une petite précision, 139 est le nombre de partitions 5-5-2 des 12 sommes telles que la somme totale est identique. On passe à 51 si la somme totale est un nombre premier.

Cependant pour chacune des partitions, il reste 5!*5! permutations à tester. Ce qui fait quand même 734400 cas à tester et on a pas encore mis de nombre premier dans la grille...  Ça me semble beaucoup mais on peut certainement diminuer ce nombre en évitant de générer toutes les permutations. On peut ne prendre qu'un nombre de chacun des sets de taille 5 et essayer de remplir la grille (en partant du coin inférieur droit) ne continuant à développer les permutations que si c'est possible de faire le coin.

Je vais essayer de mettre tout ça en pratique et je vous reviens

Merci !

Posté par
LittleFox
re : Combien sur 21 ? 25-08-15 à 19:19

perdu
C'est pas encore ça

J'ai un problème avec la partie

Citation :
on bourrine [...] le nombre de possibilités est normalement assez faible
Moi, j'ai un nombre de possibilités énorme .

Je vais prendre une solution particulière prise au hasard dans les solutions données et extrapoler, je sais que ce n'est pas correct mais je ne sais pas comment donner une idée de grandeur du calcul autrement.

Soit cette solution à laquelle on va arriver :

41381
20641
10211
99991
79997

Les sommes des lignes sont {5,13,17,37,41} et celle des colonnes {11,19,23,29,31}, la somme totale est 113. C'est une partition sur 51 possibilités.

Nous allons choisir les rangées, les chiffres possibles sont {1,3,7,9} pour la ligne du bas et la colonne de droite, il n'y a pas de 0 dans la ligne du haut ni dans la colonne de gauche :

Rangée : Chiffres - Somme des chiffres - Nombre de possibilités -> Nombre choisi (somme des chiffres)
L5 : ????? - {5,13,17,37,41} - 54 -> 79997 (41)
C5 : ????7 - {11,19,23,29,31} - 11 -> 11117 (11)
L1 : ????1 - {5,13,17,37} - 206 -> 41381 (17)
C1 : 4???7 - {19,23,29,31} - 59 -> 42197 (23)
L2 : 2???1 - {5,13,37} - 25 -> 20641 (13)
C2 : 10??9 - {19,29,31} - 6 -> 10099 (19)
L3 : 10??1 - {5,37} - 2 -> 10211 (5)
C3 : 362?9 - {29,31} - 1 -> 36299 (29)
L4 : 999?1 - {37} - 1 -> 99991 (37)
C4 : 84199 - {31} - 1 -> 84199 (31)

En choisissant au hasard parmi les possibilités rencontrées, j'avais une chance sur 51x54x11x206x59x25x6x2x1x1x1 = 110.457.982.800 ça me semble beaucoup. Bon ce nombre varie beaucoup en fonction du chemin choisi mais en testant quelques chemins donnant une solution ou non, j'obtiens souvent des nombres au delà de 109. D'habitude si un algorithme parcours plus de 106 chemins, je considère qu'il sera probablement trop lent.

Et le fait est que mon algorithme tourne depuis un peu plus de 2h30 sans avoir trouvé de solution...

Y aurait-il un raccourci que j'ai manqué? Notamment lors du choix de L1 et C1?
Peut-être un langage par contrainte marche mieux qu'un langage impératif (en choisissant parmi le moins de possibilité à chaque étape par exemple)? En quel langage le problème a-t-il été résolu?
En combien de temps, quel genre de machine?

Still fighting

Posté par
dpi
re : Combien sur 21 ? 26-08-15 à 11:35

perduBonjour,

En attendant la nouvelle..

Et dire que seulement 2 grilles ont été trouvées dans
les temps par masab et  nofutur2

Posté par
emeu
re : Combien sur 21 ? 27-08-15 à 01:15

perduMerci LittleFox pour tes remarques !

Du coup, j'ai écrit un peu de code pour essayer de reproduire le calcul. En ne faisant quasiment aucune optimisation, j'obtiens l'estimation de temps de calcul suivante:

- pour chacune des 51 partitions possibles et chacune des (5!)^2 permutations, le test de toutes les complétions possibles me prend en moyenne 0.5 secondes. Le plus gros du temps de calcul est passé dans le calcul de tous les bords possibles de la grille.

J'ai fait quelques optimisations (assez basiques mais qui m'ont l'air efficaces) :
Avant toute chose on précalcule pour tout (i,j,k), où i dans {1,...9}, j dans {1,3,7,9} l'ensemble des nombres premiers à 5 chiffres qui commencent par i, finissent par j et dont la somme des chiffres vaut k. En effet, on aura besoin souvent de ces ensembles et on ne veut pas les recalculer à chaque fois.
Les bords possibles sont calculés en agrandissant progressivement pour éviter un gros facteur combinatoire (i.e. on calcule les dernières colonnes possibles, puis les dernières lignes compatibles avec celles-ci, puis les premières lignes, puis les premières colonnes).

Tout ça mis bout à bout, j'obtiens une estimation de temps de 0.5s * 51 * (5!)^2 = 360000 secondes soit environ 4 jours. (on peut sûrement largement réduire ce temps en optimisant et en précalculant tous les sous-ensembles de premiers qui vont être utiles par la suite, par exemple tous ceux qui commencent ou finissent par un chiffre donné)

Je n'ai pas encore eu le temps de finir le code...
Le langage que j'utilise est Magma et je ne sais pas sur quel type de machine le problème a été résolu.

emeu

Posté par
LittleFox
re : Combien sur 21 ? 10-09-15 à 15:52

perdu
J'ai enfin des réponses (je les ais depuis plus d'une semaine mais pas eu le temps de les analyser) (oui je suis encore sur ce problème ).

J'ai utilisé une approche où j'ai essayé d'optimiser le calcul de chaque possibilité plutôt que le nombre de possibilités.

Après avoir générés les partitions, je génère trois tables où j'ai les nombres premiers de 5 chiffres dont la somme est s et qui fini par i pour chaque i et s possibles. La première table contient tous ces nombres premiers, la deuxième ceux qui ne contiennent pas de 0 (première ligne et première colonne) et la troisième ceux qui ne contiennent que les chiffres {1,3,7,9} (dernière ligne et dernière colonne).

Pour chaque partition (51), je choisi une somme s dans la première partition (5 possibles) et un nombre n pour ma dernière colonne dont la somme des chiffres est s (en moyenne 16.4 possibilités). Ensuite pour chaque permutation p possible de la seconde partition (120), je rempli ma table ligne par ligne en ne tenant compte que de la somme de la ligne (égale à p[ligne]) et du dernier chiffre (égal à n[ligne]) (en moyenne 197*32933*2340/1205 661532).

Une fois la table obtenue je la transpose et je vérifie que les nombres obtenu correspondent à la première partition et qu'ils sont dans la première table de nombres premiers.

Ça fait moins de 6.5*1010 tables à vérifier. Quand même beaucoup mais en pratique ça m'a pris un peu plus de 10h de calcul sur 3 processeurs (2.6Ghz en python) pour passer à travers tout... et me rendre compte que j'ai sélectionné la mauvaise table pour la première ligne et que je n'ai que 1209 sur 4176 solutions . Mais au moins elles sont correctes et je confirme un bon tiers des solutions d'emeu .

Il ne me reste plus qu'à relancer tout ça avec cette petite correction . Ça devrait me prendre 3293/2340*10 14 heures de calcul .

Mais depuis, je me dis que je retenterai bien la solution où on cherche la solution en intercalant lignes et colonnes ce qui fait beaucoup plus de tables (on connait le 5ème chiffre, le 5ème et le 1er, le 5ème, le 1er et le 4ème, ...) et qui est plus difficile à généraliser (car oui, j'ai essayé de généraliser la taille de la grille :p)

Pour information, il n'y a pas de solution pour les grilles de taille 1,2,3,4 et 6... Pour la taille 7, je cherche encore . Il y a 771 partitions au lieu de 51 et 216859 nombres premiers possibles au lieu de 3293, good luck .

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 160:59:07.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !