MPO n°92 - Les (faux) nombres d'Ackerman
Modérateur : Politburo
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
MPO n°92 - Les (faux) nombres d'Ackerman
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Les nombres d'Ackerman
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.
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Les nombres d'Ackerman
Bonjour,
Tricheur !
Et sinon, ils sont TOUS divisibles par 52 au-delà de certains m et n...
G.E.
Tricheur !
Et sinon, ils sont TOUS divisibles par 52 au-delà de certains m et n...
G.E.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Les nombres d'Ackerman
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
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Les nombres d'Ackerman
Bonjour,
En effet, c'est difficile.
G.E.
En effet, c'est difficile.
G.E.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Les nombres d'Ackerman
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
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:
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.
Surtout que la première calculette qui m'était tombé sous la main était un SHARP PC1211.
C'est difficile, mais pas impossible
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
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.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Les nombres d'Ackerman
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)
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
(Edit : entre temps,il a été indexé MPO numéro 92)
J'arrive presque instantanément au résultat ci-dessous sur ma DM42 :
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.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Les nombres d'Ackerman
En imprimant virtuellement mes deux sous-programmes avec Free42, je me suis rendu compte qu'il y a une coquille dans ACK2 :
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.
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.
Re: Les nombres d'Ackerman
Balaise cette fonction
J'ai voulu la faire en mode récursif sur la Prime :
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
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;
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
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Les nombres d'Ackerman
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.
@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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Les nombres d'Ackerman
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
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*
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.
Re: Les nombres d'Ackerman
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;
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Les nombres d'Ackerman
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
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Les nombres d'Ackerman
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...
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...