Challenge Estival : l'Heure Première

[zpalm]

Un petit challenge estival, et une excuse pour amener votre pocket sur la plage.



Avec les vacances notre rapport au temps change, devient plus élastique, moins rigide. C'est l'occasion de revoir l'ordre immuable de l'horloge.
Saurez-vous redisposer les nombres de 1 à 12 autour du cadran de telle sorte que pour deux nombres voisins leur somme soit un nombre premier, ainsi que la valeur absolue de leur différence?

Quelques précisions:
- Les doublons dus à la symétrie du cadran seront éliminés. Par exemple: 1,2,3,4,5,6,7,8,9,10,11,12 et 1,12,11,10,9,8,7,6,5,4,3,2 sont identiques.
- 1 n'est pas considéré comme un nombre premier.

A vos pockets !

PS: j'ai hésité à en faire un MPO, mais ça me semblait un peu complexe pour l'esprit des MPO, et hors de portée des machines historiques comme les HP RPN.

[caloubugs]

Mouaip, c'est du niveau défi Turing ou Euler, malheureux...

Ca va nous faire chauffer les neurones...

[zpalm]

Bon, il semble bien que les neurones soient en vacances
On va donc simplifier drastiquement le problème : pour cela ajoutons une 13ème heure… là c’est facile.
C’est bon, vous avez la réponse? Vous pouvez généraliser ?
Ok, les neurones ne sont pas tous noyés dans le pastis, il ne reste plus qu’à trouver la réponse à la question initiale.

[charognard]

10 DIM A$(12),B$(12)
20 FOR A=1 TO 12
30 C= INT(A/2)<>A/2
40 FOR B=1-C TO 12-C STEP 2
50 S=ABS(A-B),R=A+B
60 IF S<>1 AND S<>9 AND R<>9 AND R<>15 AND R<>21 THEN A$(A)=A$(A)+HEX$ B
70 NEXT B
80 NEXT A
90 B=-1
100 FOR A=1 TO 12
110 IF LEN A$(A)=2 LET B=B+1:B$(B)=LEFT$(A$(A),1)+HEX$ A+RIGHT$(A$(A),1)
120 NEXT A
130 F=0
140 FOR C=0 TO B
150 FOR D=0 TO B
160 FOR E=1 TO 2
170 IF RIGHT$(B$(C),E)=LEFT$(B$(D),E) LET B$(C)=B$(C) + RIGHT$(B$(D),LEN B$(D)-E):B$(D)="#--",F=1
180 NEXT E
190 NEXT D
200 NEXT C
210 IF F=1 THEN 130
220 FOR C=0 TO B
230 IF B$(C)<>"#--" PRINT B$(C); "  ";
240 NEXT C
250 FOR A=1 TO 12
260 IF LEN A$(A)>2 PRINT HEX$ A;"(";A$(A);")";
270 NEXT A
280 END


RESULTATS :
--------------
5294 16B83A7

1 (46C)
4 (179)
5 (28C)
7 (4AC)
8 (35B)
C (157)

 

APRES ANALYSE :
-------------------
C5294;16B83A7

 

SOIT LES SOLUTIONS:
-------------------------
12;5;2;9;4;1;6;11;8;3;10;7
4;9;2;5;12;1;6;11;8;3;10;7
4;9;2;5;12;7;10;3;8;11;6;1
12;5;2;9;4;7;10;3;8;11;6;1

[zpalm]

Bravo !! (Il y a juste deux fois trop de solutions...)

Par contre je ne comprends pas la ligne 120, il ne manque pas un FOR A avant ?

[charognard]

Si oubli de la ligne 100

Pour les soluces
sens trigo et horaire.

De mon tel portable en vacances

[zpalm]

Pour les soluces
sens trigo et horaire.

C'est pas grave, je me suis peut être mal exprimé mais j'avais demandé de supprimer les doublons dus à la symétrie du cadran.

[Marge]

Sympa, ce défi. Dommage que mes neurones ne soient plus en vacances, j'aime bien (commenter, à défaut de participer à) ce genre de message.

[zpalm]

Je viens de m'apercevoir que ce petit challenge était resté ouvert avec la seule réponse de Charo.

L'auteur de ce challenge est le mathématicien Bernardo Recamán. Il a été publié initialement dans le New York Times: Bernardo Recamán’s Primes in a Circle Puzzle.

Tout d'abord la réponse à la question facile:

Bon, il semble bien que les neurones soient en vacances
On va donc simplifier drastiquement le problème : pour cela ajoutons une 13ème heure… là c’est facile.
C’est bon, vous avez la réponse? Vous pouvez généraliser ?

C'était quand même pas trop dur, pas besoin de pocket pour ça: avec 13 heures autour du cadran on a plus d'heures impaires que d'heures paires donc quelque soit la répartition on aura toujours deux heures impaires côte à côte, leur somme est paire et ne peut donc pas être un nombre premier.
On peut donc conclure que si l'on a un nombre impair d'heures autour du cadran il n'y a pas de solution.

Revenons au problème initial avec un nombre pair d'heures autour du cadran.

Saurez-vous redisposer les nombres de 1 à 12 autour du cadran de telle sorte que pour deux nombres voisins leur somme soit un nombre premier, ainsi que la valeur absolue de leur différence?

Quelques précisions:
- Les doublons dus à la symétrie du cadran seront éliminés. Par exemple: 1,2,3,4,5,6,7,8,9,10,11,12 et 1,12,11,10,9,8,7,6,5,4,3,2 sont identiques.
- 1 n'est pas considéré comme un nombre premier.

Voici un petit programme récursif sur HP Prime qui a comme paramètre d'entrée le nombre d'heures sur le cadran ce qui permet de vérifier qu'il y a deux solutions pour 12 heures, une seule pour 14 heures, 4 pour 16 heures et 88 pour 18 heures...



Le programme construit d'abord une matrice NxN identifiant les paires de nombres correspondant aux critères: leur somme est un nombre premier, ainsi que la valeur absolue de leur différence.

Ensuite, partant du haut de l'horloge (heure N) il va parcourir cette matrice pour trouver tous les chemins de N éléments en éliminant les doublons.

Code : Tout sélectionner

#pragma mode( separator(.,;) integer(h32) )
LOCAL Mn, Nn, Res;
Suivant();

EXPORT HeurePremière(N)
BEGIN
  PRINT("HeurePremière("+N+"):");
  Nn:=N; Res:={};
  Mn:=MAKEMAT(isprime(I+J)*isprime(ABS(I-J)),N,N);
  Suivant(Mn,Nn,{});
  PRINT(Size(Res)+" solution"+IFTE(Size(Res)==1,"","s"));
  RETURN Res;
END;

Suivant(m,c,l)
BEGIN
  LOCAL j,a,b:=Res;
  l:=CONCAT(l,c);
  IF SIZE(l)==Nn AND Mn(Nn,c) THEN
    a:=CONCAT({l(1)},REVERSE(l({2,Nn})));
    IF NOT CAS(POS(b,a)) THEN Res(0):=l; PRINT(l); END;
    RETURN;
  END;
  m:=mRow(0,m,c);
  FOR j FROM 1 TO Nn DO
    IF m(j,c) THEN Suivant(m,j,l); END;
  END;
END;

[Marge]

Ah bah oui, mais c'est fastoche avec une Prime
Parce que la même chose sur une HP-25e ("e" comme "estivale"), je veux bien voir

[C.Ret]

Chiche...

Mais d'abord en RPL (HP-28S), puis RPN mais avec beaucoup de mémoire (type HP-41) et peut-être sur émulateur HP-25 ou HP-15...

Et avec un algorithme original différent de ceux utilisés ci-dessus, algorithme basé sur le développement d'un arbre...

En effet, pour que la somme et la différence de deux heures qui se suivent sur l'horloge primaire puissent être toutes les deux premières, il faut alterner les parités.

De plus, les combinaisons ne sont pas infinies, loin de là. Il y a même de fortes limitations dans le choix de l'heure b une fois que l'on a choisi l'heure précèdante a
.

[C.Ret]

Bon, comme je n'avais pas mon HP-28S sous la main, j'ai composé une première solution pour SHARP PC-1360

Code : Tout sélectionner

10:CLEAR : INPUT "Lenght =";L,"Initial=";B:T=B/2,P=-(T=INT T): WAIT 0: USING : DIM H(L),E(L)
20:N=N+1,H(N)=B,E(B)=N,B=P,P= NOT P
30:IF N=L LET T=H(1):GOSUB 100: IF T FOR T=1 TO N: PRINT H(T);: NEXT T: BEEP 1: PRINT
40:B=2+B: IF B>L LET B=H(N),E(B)=0,H(N)=0,N=N-1,P= NOT P: GOTO 60
50:IF E(B)=0 LET T=B: GOSUB 100: IF T GOTO 20
60:IF N GOTO 40	
70:BEEP 2: END

100:T=T+H(N): GOSUB 120: IF T=0 RETURN
110:T= ABS (T-2*H(N))
120:IF T=1 OR T=9 OR T=15 OR T=21 OR T=25 OR T=27 OR T=33 LET T=0
130:RETURN

avec:
L   = Longueur de l'horloge
H() = Tableau des L heures premières déjà placées
E() = non nul pour les heures déjà placées

N   = Nombre d'heures premières placées
B   = Heure suivante / initiale
P   = parité de la dernière heure placée (-1:pair   0:impair)
T   = Argument et résultat du "test de primalité"  (GOSUB 100)

Petites explications :

"pair+pair" et "impair+impair" donne des résultats "pair".
Il est donc nécessaire d'organiser les heures de l'horloge première en alternant heures paires et impaires.

Ensuite, parmi les nombres impairs que l'on peut composer avec les heures d'une horloge à 12, 14 ou 16 positions horaires, seuls 9 15 21 25 27 et 33 ne sont pas des nombres premiers (ainsi que 1 comme demandé dans l'énoncé).

Le test de primalité se réduit donc aux tests de la ligne 120. C'est plus simple et se sera réalisable (je l'espère) sur une HP-25C.

Ensuite pour que l'heure b puisse suivre l'heure a, il faut vérifier que a+b et |a-b| sont tous deux premiers.
Si l'on pose T=a+b, le second test revient à tester | T-2b | d'où la ligne 110

Le programme est basé sur une boucle de recherche, on donne la taille de l'horloge et l'heure initiale.
Les heures déjà données sont mémorisées dans le tableau H(), à la position H(N) se trouve la dernière heure posée de l'horloge.

La ligne 20 se charge de poser l'heure B dans l'horloge en incrémentant N et en mémorisant celle-ci dans le tableau à la position H(N). Comme il faut alterner heures paires et impaires, la parité P est changée en NOT P et B est initialisée à 0 ou -1 afin de commencer la recherche de l'heure suivante en testant successivement 2 4 6 8 ... ou 1 3 5 7 ... selon la parité de H(N).

Si on arrive à N=L c'est que l'horloge est remplie, on teste alors que la première heure et la dernière sont compatibles. On utilise pour cela le sous-programme commençant à la ligne 100 qui testera la primalité H(1)+H(N) et |H(1)-H(N)|.
Si les heures sont compatibles, la ligne 30 affiche l'horloge (en fait le contenu du tableau H()) et le pocket émet un BEEP pour faciliter le chronométrage.

Si l'horloge n'est pas remplie, la recherche d'une heure suivante possible commence à la ligne 40. Si l'on arrive à B>L, c'est qu'aucune heure ne convient, on retire alors la dernière heure posée de l'horloge en décrémentant N d'une unité. On prend le soin de mémoriser B qui servira pour la recherche de l'heure suivante et l'on change la parité P.

A la ligne 50, si l'heure B n'existe pas encore dans l'horloge, on effectue le test de parité de B+H(N) et |B-H(N)|. Si le test est valide, l'heure B est posée dans l'horloge.
Le tableau E() permet de facilement tester l'existence de l'heure dans l'horloge. En effet, une valeur (non nulle) est mémorisée dans E(B) pour chaque heure B posée (cf. ligne 20) et E(B) est remis à zéro pour chaque heure B retirée de l'horloge (cf. ligne 40).
Le rôle de E() est assez binaire, je compte sur HP-41C utiliser les drapeaux SF nn et CF nn pour mimer le rôle de E() en RPN.


Ce code, ne vérifie pas le sens de rotation de l'horloge, il donne donc pour l'horloge de 12 positions horaires les 2 solutions dans les deux sens :

Code : Tout sélectionner

Display:                             Keystrokes:       Times:
--------                             -----------       ------
RUN MODE                             [ON]
RUN                                  [R][U][N][ENTER] 
Lenght =12                           [1][2][ENTER]
Inital =12_                          [1][2]
                                     [ENTER]           0'00"00
12.1.6.11.8.3.10.7.4.9.2.5.                            1'11"98
12.5.2.9.4.1.6.11.8.3.10.7.                            1'48"65 
12.5.2.9.4.7.10.3.8.11.6.1.                            1'57"45
12.7.10.3.8.11.6.1.4.9.2.5.                            4'22"60
>                                                      4'32"59

RUN                                  [R][U][N][ENTER] 
Lenght =14                           [1][2][ENTER]
Inital =1                            [1][ENTER]         0'00"00
1.4.7.10.13.6.11.8.3.14.9.2.5.12.                       1'25"12
1.12.5.2.9.14.3.8.11.6.13.10.7.4.                      12'50"35
>                                                      15'32"59

J'ai sous le coude une version qui va 4x plus vite...
... c'est cette version que j'adapte pour le RPL et qui servira de base pour une solution en RPN.

Mais je suis loin encore d’une version pour HP-25C