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

Répondre
Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6653
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

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

Message par gege » 26 mars 2020 16:33

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.
Dernière édition par gege le 28 mars 2020 12:01, édité 2 fois.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2064
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret » 26 mars 2020 18:17

gege a écrit :
26 mars 2020 16: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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 4849
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Les nombres d'Ackerman

Message par ledudu » 26 mars 2020 18:39

Galopin !
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6653
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege » 26 mars 2020 18:44

Bonjour,
Tricheur ! :-)

Et sinon, ils sont TOUS divisibles par 52 au-delà de certains m et n...
G.E.

Avatar de l’utilisateur
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 326
Inscription : 27 janv. 2013 01:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl » 27 mars 2020 00:41

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 de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6653
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege » 27 mars 2020 02:03

Bonjour,
En effet, c'est difficile.
G.E.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2064
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret » 27 mars 2020 12:17

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) Consulté 167 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€99,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. :)
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 326
Inscription : 27 janv. 2013 01:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl » 27 mars 2020 21:33

Encore une performance remarquable de C.Ret sur ce MPO ; bien qu'il ne soit pas indexé comme tel :)
C.Ret a écrit :
27 mars 2020 12: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

Avatar de l’utilisateur
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 326
Inscription : 27 janv. 2013 01:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl » 27 mars 2020 22:42

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 de l’utilisateur
Danny
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 59
Inscription : 28 déc. 2013 17:34

Re: Les nombres d'Ackerman

Message par Danny » 28 mars 2020 00:47

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
Casio 3900p, 8500G, 9900GC
HP 21, 28S, 42S, 48SX, 48GX, 50g, Prime

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6653
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege » 28 mars 2020 00:48

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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2064
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Les nombres d'Ackerman

Message par C.Ret » 28 mars 2020 01:20

dprtl a écrit :
27 mars 2020 21: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
Dernière édition par C.Ret le 28 mars 2020 03:43, édité 2 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Danny
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 59
Inscription : 28 déc. 2013 17:34

Re: Les nombres d'Ackerman

Message par Danny » 28 mars 2020 01:31

gege a écrit :
28 mars 2020 00: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) :)
Casio 3900p, 8500G, 9900GC
HP 21, 28S, 42S, 48SX, 48GX, 50g, Prime

Avatar de l’utilisateur
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 326
Inscription : 27 janv. 2013 01:26
Localisation : Strasbourg
Contact :

Re: Les nombres d'Ackerman

Message par dprtl » 28 mars 2020 01:38

gege a écrit :
28 mars 2020 00: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 :
28 mars 2020 00: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 de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6653
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege » 28 mars 2020 01:54

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

Revenir vers « Tous les Pockets »