MPO n°92 - Les (faux) nombres d'Ackerman

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

MPO n°92 - Les (faux) nombres d'Ackerman

Message par gege »

Bonjour,
Les nombres d'Ackerman A(m,n) sont calculés ainsi :
- A(1,1)=1
- si m<1 ou n<1, A(m,n)=0
- sinon A(m,n)= m*A(m-1,n) + n*A(m,n-1)

Question : quel est le plus petit nombre d'Ackerman divisible par 52 ?

(faux) indice : A(m,m) est divisible par m! .
A vos machines !!!
G.E.
Modifié en dernier par gege le 28 mars 2020 11:01, modifié 2 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret »

gege a écrit : 26 mars 2020 15:33 Les nombres d'Ackerman A(m,n) sont calculés ainsi :
- A(1,1)=1
- si m<1 ou n<1, A(m,n)=0
- sinon A(m,n)= m*A(m-1,n) + n*A(m,n-1)

Question : quel est le plus petit nombre d'Ackerman divisible par 52 ?
Le plus petit nombre d'Ackerman définit comme ci-dessus divisible par 52 est zéro.
C'est pratique zéro est petit (c'est le plus petit entier positif ou nul) et en plus il est divisible pour n'importe quel nombre dont 52.

J'en ai trouvé une infinité parmi les nombres d'Ackerman A(m,n) ;
* il y a tout d'abord A(0,0) = 0
* mais aussi tous les A(0,x) = 0 et tous les A(x,0) = 0 (avec x entier naturel)
* enfin tous les A(x,y) avec x et y entiers relatifs pris simultanément inférieurs à l'unité (x<1 ET y<1)

Maintenant, je vais effectivement aller chercher une calculette pour trouver le plus petit nombre d'Ackerman non nul divisible par 52 définit comme ci-dessus.

:wink:
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5631
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Les nombres d'Ackerman

Message par ledudu »

Galopin !
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege »

Bonjour,
Tricheur ! :-)

Et sinon, ils sont TOUS divisibles par 52 au-delà de certains m et n...
G.E.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl »

Si je ne me plante pas, ce problème est plutôt ardu pour une calculette de base : mon plus petit nombre d'Ackerman divisible par 52 comporte 12 chiffres... à vérifier :)
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege »

Bonjour,
En effet, c'est difficile.
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret »

Merci de préciser, je m'en été rendu compte.

Surtout que la première calculette qui m'était tombé sous la main était un SHARP PC1211.
C'est difficile, mais pas impossible :)
arton2510.jpg
arton2510.jpg (44.63 Kio) Vu 10672 fois
Evidemment, pour être sûr du résultat avant de l'annoncer, j'ai vérifier avec une TI-92 II.
C'est bien plus facile.

Pour ceux qui n'aurait pas encore trouvé, je donne ci-dessous ma solution:

Code : Tout sélectionner

10:CLEAR :B=9€9,M=1,T=20,A(T+1)=1
20:M=M+1,N=0
30:N=N+1,A=MA(T+N)+NA(T+M),A(T+M)=A,A(T+N)=A:IF A>€10 GOTO 60
40:Q=A/52:IF A=52*INT Q IF A<B LET I=M,J=N,B=A
50:IF N<M GOTO 30
60:IF N>1 GOTO 20
70:BEEP 3: PRINT I;J;"=";B
Ce qui me semble être le plus petit nombre d'Ackerman A(m,n) non nul multiple de 52 s'affiche accompagné de ses coordonnées lorsque les trois 'bips' ont retentis c'est à dire environ 1min40s après avoir lancé le programme

L'algorithme s'inspire du fou qui la nuit cherche ses clefs uniquement sous les réverbères allumés. :)
Modifié en dernier par C.Ret le 21 mai 2020 09:27, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl »

Encore une performance remarquable de C.Ret sur ce MPO ; bien qu'il ne soit pas indexé comme tel :)
(Edit : entre temps,il a été indexé MPO numéro 92)
C.Ret a écrit : 27 mars 2020 11:17 Ce qui me semble être le plus petit nombre d'Ackerman A(m,n) non nul multiple de 52
J'arrive presque instantanément au résultat ci-dessous sur ma DM42 :

Image

Mais est-ce vraiment le plus petit ? Pas évident à prouver... Mon programme naïf utilise la récursivité et la fonction LSTO sur DM42 (ou Free42). Chargez les deux programmes ci-dessous en RAM, puis lancez D52ACK sans argument :
ack2.raw
d52ack.raw
Modifié en dernier par dprtl le 04 avr. 2020 10:29, modifié 1 fois.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl »

En imprimant virtuellement mes deux sous-programmes avec Free42, je me suis rendu compte qu'il y a une coquille dans ACK2 :

Image

Les trois derniers pas (35, 36 et 37) sont des résidus d'une version précédente. On peut les effacer sans aucun impact sur le fonctionnement du programme.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Les nombres d'Ackerman

Message par Danny »

Balaise cette fonction 8O
J'ai voulu la faire en mode récursif sur la Prime :

Code : Tout sélectionner

EXPORT Ackermann(m, n)
BEGIN
 CASE
  IF (m = O) THEN
   RETURN n + 1;
  END;
  IF (n = 0) THEN
   RETURN Ackermann(m - 1, 1);
  END;
  DEFAULT
   RETURN Ackermann(m - 1, Ackermann(m, n - 1));
 END;
END;
Et du coup je me suis rendu compte qu'en mode CAS, il y a une limite à 100 appels récursifs maxi, qu'il n'y a pas en mode "non CAS" :|
Donc je l'ai faite tourner en mode non-CAS, mais on atteint vite les limites de la machine : pour Ackermann(4,1) par exemple, j'ai pas eu la patience d'attendre de voir si elle pouvait aller jusqu'au bout du calcul :D
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege »

Bonjour,
@C.Ret : je vais tester sur un Basic.

@dprtl : La réponse est corrrecte mais tu as de la chance !
Si la solution n'était pas pour une valeur de n (ou m si tu préfères) égale à 1, c'aurait pu ne pas être la valeur minimale...
Bref, Bravo !

Si vous regardez bien les nombres d'Ackerman pour m+n=15, que remarquez-vous ?
Qu'en déduisez-vous pour m+n >= 15 ?

Ça me semblait tellement bizarre que je voulais vous le montrer.
Et pour d''autres nombres que 52 ?

@Danny :Bien vu, tu calcules les vrais nombres d'Ackerman, ceux que j'ai proposés... ben c'est pas les vrais ! Pas grave... ?
On doit pouvoir accélérer le bazar, non ?

Héhé...
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret »

dprtl a écrit : 27 mars 2020 20:33[…]Mais est-ce vraiment le plus petit ? Pas évident à prouver... [...]
En préparant les données pour illustrer le plus clairment possible ma réponse, je me rends compte de trois choses:
  • J'ai eut une chance terrible de trouver le bon résultat sur une machine limité à 10 chiffres
  • Que les bonnes pratiques de programmation et mon approche rigoureuse sont les deux seuls points qui ont aidés à cette chance insolante
  • Je peux donc encore simplifier mon programme qui n'était pas un MPO, juste structuré pour répondre au mieux à la question :(

Code : Tout sélectionner

1:CLEAR :M=2,T=20,U=1                     % Initialise M,N  indices parcourant les Ackermen A(m,n)
                                          %  T  début tableau des antécédents (initialisés à zéro)
					  %  U  initialise T(1) = 1           ( car A(1,1)=1 ) 
2:N=N+1			              % *** Boucle Principale ***
 ,A=MA(T+N)+NA(T+M)                       %  Calcul  A(m,n)=m.A(m-1,n)+n.A(m,n-1)			
 ,A(T+M)=A,A(T+N)=A                       %  MàJ antécédents ligne et colonne (respectivement m et n) 
 :IF A>€10 GOTO 5                         %  si trop grand, passe au m suivant
3:Q=A/52                              % *** Test divisibilité par 52 
 :IF A=52*INT Q BEEP 1: PRINT M;N;"=";A   %  bip et affiche coordonnée (m,n) et multiple A
4:IF N<M GOTO 2                           %  ne calcul qu'avec n<=m car symétrie A(m,n)=A(n,m)
5:IF N>1 LET M=M+1,N=0:GOTO 2             %  calcul toutes les A(m,*) possibles
                                      % *** Fin programme: plus de valeur calculable ligne m
Ce programme est plus cours mais aussi plus rapide il ne recherche pas le multiple minimum, il s'arrête comme le code de dprlt dès qu'un multiple est trouvé car le sens de parcourt du tableau des A(m,n) guaranti un parcourt par valeur croissante et donc de trouver le plus petit multiple non nul en premier.

En réalité, il est facile de prouver que les termes A(m,n) croissent avec m ou n croissant.
Tout les termes sont positifs et les termes suivant s'obtiennent par multiplication (m>0 et n>0 ) et donc l'addition de deux termes strictement positifs.

Donc, les nombre d'Ackerman A(m,n) croissent avec m ou n croissant. Ils le font même très rapidement, ils prennent facilement au minimum un chiffre supplémentaire chaque fois que l'on se décale d'un m ou d'un n. C'est exactement comme une factorielle. D'ailleurs, A(m,1) = m! et A(1,n)=n!

Par ailleurs, on voit d'après la définition que les indices m et n ont des rôles parfaitement symétriques. Il en résulte que A(m,n) = A(n,m). Mon code abuse d'ailleurs de cette symétrie pour diviser par deux (ou presque) les valeurs à calculer. Mais aussi pour n'avoir à retenir qu'un nombre très limité de valeurs afin de calculer les prochains A(m,n).

Outre la symétrie, la définition de A(m,n) ne fait intervenir que deux antécédents A(m-1,n) et A(m,n-1). Dans la matrice des A(m,n) ces des antécédents correspondent respectivement à l'élément juste à gauche sur la même ligne m (mais à la colonne n-1) et celui juste au-dessus sur la même colonne n (mais à la ligne précédente m-1).

A cause de la symétrie, les valeurs des antécédents sont les mêmes pour les lignes et les colonnes et peuvent donc être mémorisées dans un même vecteur T(). Il faut juste veiller à bien les y déposer et au bon moment afin de les récupérer facilement lors du calcul du prochain A(m,n).

Tels que présenté ci-dessous, le code ne parcourt donc que le triangle inférieur de la matrice des A(m,n), c'est à dire les A(m,n) avec n≤m en commençant par l'élément le plus petit A(1,1)=1.
On parcourt donc la matrice dans le sens des éléments croissants, notamment à chaque fois que l'on passe à l'élément situé à droite, on aura une valeur plus grande.
Mais mon PC-1211 ne sais pas déterminer la divisibilité par 52 si le nombre A devient trop grand. D'où le test de la fin de la ligne 2: qui suspend la progression vers les éléments des colonnes à droite en passant au calcul des éléments A(m,n) de la ligne suivante.

Comme le fou qui ne cherche la nuit ses clefs tombées de sa poche au milieu du parc, je ne scrute le sol que sous les lampadaires allumés.

Dans le tableau suivant j'ai recopié toutes les valeurs que peut calculer mon PC-1211 sans arrondi. Les pointillés indiques les valeurs qui ne sont pas calculées mais déduites par la symétrie. Les *skip* indiquent les valeurs trop grandes qui ont fait avancer le calcul à la ligne suivante.

Code : Tout sélectionner

A(m,n)                                   n
  \          1         2          3          4          5          6          7 
  1          1         .          .         ..        ...        ...       ....
  2          2         8         ..        ...       ....       ....      .....
  3          6        36        216       ....      .....      .....     ......
  4         24       192       1440      11520     ......     ......   ........
  5        120      1200      10800     100800    1008000   ........  .........
  6        720      8640      90720     967680   10886400  130636800 .......... 
m 7       5040     70560     846720   10160640  127008000 1676808600     *skip*
  8      40320    645120    8709120  116121600 1596672000     *skip*
  9     362880   6531840   97977600 1437004800     *skip*
 10    3628800  72576000 1197504000     *skip*
 11   39916800 878169600     *skip*
 12  479001600    *skip* 
 13[6227020800]
 14     *skip*
Il était donc moins-une que je ne trouve rien avec mon PC-1211 :)

Pour un MPO :

Code : Tout sélectionner

1:CLEAR :A=1/52,X=1
2:X=X+1,Y=0
3:Y=Y+1,Z=XA(Y)+YA(X),A(X)=Z,A(Y)=Z:IF Z=INT Z PRINT X+.1Y,52Z
4:IF Z<1.9€8 IF Y<X GOTO 3
5:IF Y>1 GOTO 2
                                                      105octets  Reg:A~G X Y Z
Modifié en dernier par C.Ret le 28 mars 2020 02:43, modifié 2 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Les nombres d'Ackerman

Message par Danny »

gege a écrit : 27 mars 2020 23:48 @Danny :Bien vu, tu calcules les vrais nombres d'Ackerman, ceux que j'ai proposés... ben c'est pas les vrais ! Pas grave... ?
On doit pouvoir accélérer le bazar, non ?
Ah oui en effet, avec ta définition ça galère moins en récursion :)
Ça donne ça sur la Prime :

Code : Tout sélectionner

EXPORT Ackerman(m, n)
BEGIN
 CASE
  IF (m < 1) OR (n < 1) THEN
   RETURN 0;
  END;
  IF (m = 1) AND (n = 1) THEN
   RETURN 1;
  END;
  DEFAULT
   RETURN m * Ackerman(m - 1, n) + n * Ackerman(m, n - 1);
 END;
END;
Reste à faire les tests pour trouver le + petit divisible par 52 (ou autre), mais ça sera pour plus tard (ZZzzz) :)
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl »

gege a écrit : 27 mars 2020 23:48 @dprtl : La réponse est corrrecte mais tu as de la chance !
Si la solution n'était pas pour une valeur de n (ou m si tu préfères) égale à 1, c'aurait pu ne pas être la valeur minimale...
On devrait pouvoir démontrer que, pour n fixé :

Si m1 < m2 alors A(m1,n) < A(m2,n)

Dans ce cas, si je vais suffisamment loin pour n (ce qui n'était pas le cas lors de mes premiers essais : je m'arrêtais à 10 !), alors je trouve forcément le plus petit nombre d'Ackerman-gege divisible par 52.

[EDIT] Il faudrait aussi prouver que si A(m1,n) est divisible par 52, alors A(m2,n) l'est aussi. Et là, ça me parait moins évident :)
gege a écrit : 27 mars 2020 23:48 Si vous regardez bien les nombres d'Ackerman pour m+n=15, que remarquez-vous ?
Qu'en déduisez-vous pour m+n >= 15 ?
Effectivement, au delà de 15 :

A(6,17) = 5.211.276.101.514.362.880.000 (d'après ma DM42)

et 52 [MOD]... ça fait bien zéro.... surprenant.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege »

Bonjour,
On peut tricher sur les nombres d'Ackermann-Danny (pourquoi tant de "n" ?) en s'apercevant que :
Ackermann(3,n)=8*2^n-3
Hop Ackermann(4,1)=65533 en 0,04 s !
Mais pour les suivants c'est l'horreuur !!!
Argh
G.E.

Edit : la classe C.Ret ! Regardes tous les m+n=15...
Répondre

Retourner vers « Tous les Pockets »