Bonjour 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!

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 !

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

Bonjour,
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.

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

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

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

pas trouvé mieux

11113
10103
17137
12149
39937

Score 19 sur 21

Bonjour à 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

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

Hello 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

Bonjour,

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.

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

Bonjour,

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

Je 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 ^^).

bonjour : )

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}

dommage : )
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 }

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

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 .

bonjour : )

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

Bonjour à 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

merci emeu : )

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

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

Oui, 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 ]

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





emeu

oui 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)

oups mon dernier message à annuler, sans aucun sens

Trop fort !!

Impressionnant!

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 !

C'est pas encore ça

J'ai un problème avec la partie

Bonjour,

En attendant la nouvelle..

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

Merci 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

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*3293³*2340/120⁵ 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*10¹⁰ 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 .