Hamiltonian prime cycles in a square

​



Jean-Claude Grobon, 2023

This page and the hereunder illustration explain how to label with distinct numbers the squares of the 8 x 8 traditionnal chessboard:
Put now a Queen on the above 11-square and try to find an hamiltonian cycle that visits each prime square exactly once – cycle ending on the 11-square again. Here is a first such circuit: 
11-13-17-37-47-67-23-43-53-73-83-61-71-41-31-(11)

Questions
How many such hamiltonian prime cycles are present in the 8 x 8 chessboard?
Is it possible for a Rook to do such a circuit on the 8 x 8 chessboard?

A nice sequence S would be the one counting all such cycles for chessboards of increasing sizes. Though S is a nightmarish sequence to calculate by hand, I guess it starts with a(1) = 1, a(2) = 1, a(3) = 0 and a(4) = 3 as illustrated below:
Unfortunately, we were unable to calculate a(5) – if we are right, there are 8 prime hamiltonian cycles starting with 11-13... in the 5 x 5 chessboard:
We end this page with a bluish 15 x 15 square: can you find a prime hamiltonian cycle where the lines don't cross?
(a warm thank you to Gilles E.-F. who helped me distinguish between the words eulerian and hamiltonian)
____________________
September 6 update

« Nicolas Graner is a genious in computing such hamiltonian cycles », said to me Gilles.
Indeed! Here is what Nicolas wrote to me this morning, a couple of hours after reading this page (the Queen seq so far and the Rook seq are in blue and red):

> Voici les nombres de cycles trouvés et un exemple pour chaque cas. Je peux te fournir tous les autres si ça t'intéresse. Chaque cycle est compté deux fois (deux sens de parcours), donc tu peux préférer tout diviser par deux.
(Google translation: Here are the numbers of cycles found, and an example for each case. I can provide you with all the others if you are interested. Each cycle is counted twice (two directions of travel), so you can prefer any divide by two.)

a(1, queen) = 1
    (the only solution is a loop on the initial square): 11
a(2, queen) = 1
    (the only solution is a loop on the initial square): 11
a(3, queen) = 0
a(4, queen) = 8
    11 13 23 43 41 31
    11 13 43 23 41 31
    11 31 13 23 43 41
    11 31 13 43 23 41
    11 31 41 23 43 13
    11 31 41 43 23 13
    11 41 23 43 13 31
    11 41 43 23 13 31
a(5, queen) = 36
    11 13 23 41 43 53 31
    11 13 23 43 53 31 41
    11 13 23 53 43 41 31
    11 13 31 53 23 43 41
    11 13 31 53 43 23 41
    11 13 43 23 53 31 41
    11 13 43 41 23 53 31
    11 13 43 53 23 41 31
    11 13 53 23 43 41 31
    11 13 53 43 23 41 31
    11 31 13 23 53 43 41
    11 31 13 43 53 23 41
    11 31 13 53 23 43 41
    11 31 13 53 43 23 41
    11 31 41 23 43 53 13
    11 31 41 23 53 43 13
    11 31 41 43 23 53 13
    11 31 41 43 53 23 13
    11 31 53 13 23 43 41
    11 31 53 13 43 23 41
    11 31 53 23 13 43 41
    11 31 53 23 41 43 13
    11 31 53 43 13 23 41
    11 31 53 43 41 23 13
    11 41 23 13 43 53 31
    11 41 23 43 13 53 31
    11 41 23 43 53 13 31
    11 41 23 43 53 31 13
    11 41 23 53 43 13 31
    11 41 31 53 23 43 13
    11 41 31 53 43 23 13
    11 41 43 13 23 53 31
    11 41 43 23 13 53 31
    11 41 43 23 53 13 31
    11 41 43 23 53 31 13
    11 41 43 53 23 13 31
a(6, queen) = 130
    (one example): 11 13 23 41 31 53 43 61
a(7, queen) = 197972
    (one example): 11 13 17 37 31 41 23 53 71 73 43 47 67 61
a(8, queen) = 1381722
    (one example): 11 13 17 37 31 41 23 43 47 67 61 83 53 73 71
a(9, queen) = ???
    (one example): 11 13 17 19 29 23 41 31 37 47 43 53 59 79 97 67 89 83 73 71 61

a(1, rook) = 1
    (the only solution is a loop on the initial square): 11
a(2, rook) = 1
    (the only solution is a loop on the initial square): 11
a(3, rook) = 0
a(4, rook) = 2
    11 13 23 43 41 31
    11 31 41 43 23 13
a(5, rook) = 4
    11 13 23 53 43 41 31
    11 13 53 23 43 41 31
    11 31 41 43 23 53 13
    11 31 41 43 53 23 13
a(6, rook) = 8
    (one example): 11 13 23 53 43 41 31 61
a(7, rook) = 4568
    (one example): 11 13 17 37 31 41 61 67 47 43 23 53 73 71
a(8, rook) = 17808
    (one example): 11 13 17 37 31 41 61 67 47 43 23 53 83 73 71
a(9, rook) = 5849952
    (one example): 11 13 17 19 29 23 43 53 59 79 89 83 73 71 31 37 47 97 67 61 41
__________

Nicolas (and a couple of friends of mine) are skeptical about using this chess notation for chessboards of size > 9. Here is Nicolas' remark (in French, but this is easy to understand):

> (...) pour aller au-delà de 9, il faudrait utiliser d'autres bases de numération. Mais alors ce ne serait plus homogène avec les résultats de 1 à 9. Ce qui me fait penser qu'il serait beaucoup plus logique d'interpréter la numérotation de l'échiquer NxN comme des nombres en base N+1.

Je note que la définition de la notation numérique ne parle que de chiffres, il n'est jamais question de les interpréter comme des nombres en base dix. C'est toi qui es obligé de forcer cette interprétation pour pouvoir parler de nombres premiers, mais rien n'interdit de changer la base.

Exemples (les nombres premiers sont suivis d'un *) :

N = 1
échiquier en base 2 :
11*
traduction en décimal :
3*

N = 2
échiquier en base 3 :
12* 22
11 21*
traduction en décimal :
5* 8
4 7*

N = 3
échiquier en base 4 :
13* 23* 33
12 22 32
11* 21 31*
traduction en décimal :
7* 11* 15
6 10 14
5* 9 13*

(Remarque que pour un matheux le plus naturel serait de numéroter les lignes de 0 à N-1 et de l'interpréter en base N, mais ça ne serait plus compatible avec la notation numérique échiquéenne.)

Un petit inconvénient est que la case inférieure gauche 11 n'est plus forcément un nombre premier, mais ce n'est pas bien grave. Puisqu'on s'intéresse à des cycles, peu importe la case de départ. On peut par exemple partir du plus petit nombre premier de la grille, i.e. le plus bas de la première colonne (il y a forcément au moins un nombre premier dans la première colonne, cf. http://fr.wikipedia.org/wiki/Postulat_de_Bertrand).

Avec cette nouvelle convention, voici des valeurs de la fonction a, renommée b pour éviter toute confusion.

b(1, rook) = 1
    cycle en base 2 : 11
    conversion en décimal : 3
b(2, rook) = 0
b(3, rook) = 0
b(4, rook) = 0
b(5, rook) = 24
    cycle en base 6 : 11 15 25 45 35 31 21 51
    conversion en décimal : 7 11 17 29 23 19 13 31
b(6, rook) = 0
b(7, rook) = 312
    cycle en base 8 : 13 15 35 45 65 75 73 23 21 27 37 57 51 53
    conversion en décimal : 11 13 29 37 53 61 59 19 17 23 31 47 41 43
b(8, rook) = 0

b(1, queen) = 1
    cycle en base 2 : 11
    conversion en décimal : 3
b(2, queen) = 1
    cycle en base 3 : 12 21
    conversion en décimal : 5 7
b(3, queen) = 0
b(4, queen) = 48
    cycle en base 5 : 12 21 23 32 43 34
    conversion en décimal : 7 11 13 17 23 19
b(5, queen) = 44
    cycle en base 6 : 11 15 25 45 35 31 21 51
    conversion en décimal : 7 11 17 29 23 19 13 31
b(6, queen) = 10410
    cycle en base 7 : 14 16 25 23 32 43 52 56 65 61 41
    conversion en décimal : 11 13 19 17 23 31 37 41 47 43 29
b(7, queen) = 89730
    cycle en base 8 : 13 15 35 37 27 21 23 45 65 75 53 57 51 73
    conversion en décimal : 11 13 29 31 23 17 19 37 53 61 43 47 41 59

> Peut-être à suivre dans les prochains jours, si je trouve le temps (...)
____________________
Waow, many thanks, Nicolas!
This made me think: why not using the good old square spiral? We could start the spiral with a zero or a one. Then consider the successive squares 1 x 1 , 2 x 2, 3 x 3, etc. and count the prime hamiltonian cycles. I've submitted the idea to Nicolas...

















Commentaires

Enregistrer un commentaire

Posts les plus consultés de ce blog

A square for three (chess)

Image
(English translation after the French text) Voici cinq problèmes d’échecs disjoints : a ) combien faut-il de coups au minimum pour que trois pions soient capturés sur la même case ? b ) trois tours c ) trois cavaliers d ) trois fous e ) trois dames Here are five disjointed chess problems: a) how many moves are required at least for three pawns to be captured on the same square? b) three rooks c) three knights d) three bishops e) three queens Solutions a ) (corrigé grâce à Orion , ici ) 3,5 coups pour 3 pions capturés en b5 (4 moves for White and 3 moves for Black   — 3 pawns  captured on b5)  b ) 5  coups pour 3 tours capturées en a3 (ci-dessous – merci aussi à Orion !-) (5 moves for White and 5 moves for Black  — 3 rooks  captured on a3  hereunder )  c ) 5  coups pour 3 cavaliers capturés en d5  ( ci-dessous) (5 moves for White and 5 moves for Black   — 3 knights  captured on d5  hereunder )  (merci Orion !-) d ) ...
Lire la suite

Le tripalin se présente

Image
Un tripalin est constitué de trois images. Chaque image illustre un substantif. Accolés, ces trois substantifs forment une chaîne palindromique. Laquelle nous vous invitons à trouver.  Exemple ci-dessous. Le premier mot est COL-BLEU Le second DUEL Le troisième BLOC . Ces mots forment la chaîne COLBLEUDUELBLOC qui est bien palindromique. Je posterai chaque jeudi une nouvelle salve de tripalins . Rien que des noms illustrés – pas d’adjectifs, pas de verbes conjugués, pas d’adverbes (parfois un prénom ou un nom propre – mais seulement quand il faut). À la demande générale (de mon neveu), chaque tripalin sera surmonté de son numéro d ’ ordre ( octothorpe noir) et de trois nombres bleus. Ces nombres reprennent les trois longueurs (en lettres) des trois mots présents dans le tripalin. On a par exemple ci-dessous [ #0 ↓ 7+4+4 ] car COL-BLEU comporte  7  lettres, DUEL   4  et BLOC   4 . Le numéro d ’ ordre est zéro. #0 ↓ 7+4+4 Voilà – tous retours critiques, con...
Lire la suite

Some strings au cinéma Galeries

  Lettre ouverte au cinéma Galeries   Bonsoir à tous,   Je viens de voir pour la seconde fois chez vous le beau film de Léos Carax (la première fois c’était le 26 juin en présence du réalisateur, au BRIFF). Apparut à l’écran aujourd’hui, avant la projection proprement dite, un avis que je n’avais pas remarqué en juin, expliquant un projet baptisé Some strings (« Quelques ficelles »), visible au sous-sol. Cet avis semblait faire l’éloge d’un poète palestinien mort à Gaza, lors d’un bombardement. Je n’ai pas bien compris de quoi il s’agissait, mais les mots utilisés m’ont interpellé. Après le Carax  je suis descendu voir l’exposition Some strings . J’en ai lu tous les cartels et avis placardés dans votre cinéma – et j’aimerais vous poser, si vous le voulez bien, quelques questions (je suis journaliste, vous m’avez d’ailleurs gentiment donné un « Exo » pour le Carax ).   Cette phrase, par exemple, omniprésente au cinéma Galeries, mériterait de...
Lire la suite