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:
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:
(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