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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2119
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 05:29

gege a écrit :
28 mars 2020 01:54
[…] Regardes tous les m+n=15...

Pourquoi A(13,1) est multiple de 52 ?

Ben tout simplement parce que :
13! = 1.2.3.4.5.6.7.8.9.10.11.12.13
et que
52 = 2.13
On retrouve donc tous les facteurs premiers de 52 dans A(13,1).

Pourquoi A(14,1) est multiple de 52 ?
Tout simplement parce que d'après sa définition, il peut être exprimé comme un multiple de A(13,1) c'est à dire un multiple de 13!

En effet, par définition :

A(14,1) = 14.A(13,1) + 1*A(14,0)

Or on sait que A(14,0) = 0 car tout A(m,n) avec (m<1) OU (n<1) est nul.

On a donc bien
A(14,1) = 14.A(13,1) = 14.13!
donc A(14,1) est bel et bien un multiple de 52
C'est aussi, par ailleur la factorielle de 14.
Donc, tous les A(m,1) avec m>12 seront tous des multiples de 52.
Et par symétrie, A(1,n) avec n>12 seront tous des multiples de 52.

Mais bon, concernant A(13,2) on constate que A(13,2)=161902540800 = 3113510400 * 52 donc A(13,2) est aussi un multiple de 52 :)

N'y aurait-il pas un moyen d'exprimer A(13,2) comme un multiple de la factorielle 13! ? Est-il possible de trouver k tel que A(13,2)=k.13!

On sait par définition que A(13,2) = 13*A(12,2) + 2*A(13,1)
On sait que A(13,1) = 13! mais pour calculer A(12,2), le plus simple est de commencer par le haut du tableau des A(m,n)

par définition A(1,1)=1 c'est à dire que A(1,1)=1!

Calculons A(2,2) tout en laissant apparaitre les termes factoriels:
Par définition :A(2,2)=2.A(1,2) + 2.A(2,1)
Or on sait que A(2,1) =A(1,2) = 2!
On a donc :
A(2,2) = 2.2! + 2.2! = 4.2!

Calculons A(3,2) :
par définition A(3,2) = 3.A(2,2) + 2.A(3,1) avec A(2,2)= 4.2! et A(3,1) = 3!
On a donc A(3,2) = 3.4.2! + 2.3!
Or 3.4.2! = 4.3! = 4! on peut donc factoriser par la factorielle 3!
Il vient :
A(3,2) = 4.3! + 2.3! = 6.3!

Nous avons donc calculer successivement A(2,2)=4.2! et A(3,2)=6.3! Nous pouvons continuer ainsi de proche en proche et obtenir:
A(4,2)=8.4! , A(5,2)=10.5! , A(6,2)=12.6! , … , A(12,2)=24.12! , A(13,2)=26.13! , A(14,2)=28.14! ,etc

On a bien A(13,2)=13.A(12,2)+2.A(13,1)=13.24.12! + 2.13! = 24.13.12! + 2.13! = 24.13! + 2.13! = 26.13!

Et donc le grand mystère des A(m,n) avec m+n=15 s'éclaircit d'un seul coup, tous ces nombre d'Ackerman sont multiples de 52 car il peuvent s'exprimer directement sous la forme A(m,n)=k.13!

En effet, de proche en proche le tableau suivant peut être construit :

Code : Tout sélectionner

n    1      2      3      4      5      6      7       8       9      10      11      12      13      14
m        
1     1!     2!     3!     4!     5!     6!     7!      8!      9!     10!     11!     12!     13!     14!
2     2!  4. 2!  6. 3!  8. 4! 10. 5! 12. 6! 14. 7!  16. 8!  18. 9!  20.10!  22.11!  24.12!  26.13!  28.14!
3     3!  6. 3!  9. 4! 12. 5! 15. 6! 18. 7! 21. 8!  24. 9!  27.10!  30.11!  33.12!  36.13!  39.14!  42.15!
4     4!  8. 4! 12. 5! 16. 6! 20. 7! 24. 8! 28. 9!  32.10!  36.11!  40.12!  44.13!  48.14!  52.15!  56.16!
5     5! 10. 5! 15. 6! 20. 7! 25. 8! 30. 9! 35.10!  40.11!  45.12!  50.13!  55.14!  60.15!  65.16!  70.17!
6     6! 12. 6! 18. 7! 24. 8! 30. 9! 36.10! 42.11!  48.12!  54.13!  60.14!  66.15!  72.16!  78.17!  84.18!
7     7! 14. 7! 21. 8! 28. 9! 35.10! 42.11! 49.12!  56.13!  63.14!  70.15!  77.16!  84.17!  91.18!  98.19!
8     8! 16. 8! 24. 9! 32.10! 40.11! 48.12! 56.13!  64.14!  72.15!  80.16!  88.17!  96.18! 104.19! 112.20!
9     9! 18. 9! 27.10! 36.11! 45.12! 54.13! 63.14!  72.15!  81.16!  90.17!  99.18! 108.19! 117.20! 126.21!
10   10! 20.10! 30.11! 40.12! 50.13! 60.14! 70.15!  80.16!  90.17! 100.18! 110.19! 120.20! 130.21! 140.22!
11   11! 22.11! 33.12! 44.13! 55.14! 66.15! 77.16!  88.17!  99.18! 110.19! 121.20! 132.21! 143.22! 154.23!
12   12! 24.12! 36.13! 48.14! 60.15! 72.16! 84.17!  96.18! 108.19! 120.20! 132.21! 144.22! 156.23! 168.24!
13   13! 26.13! 39.14! 52.15! 65.16! 78.17! 91.18! 104.19! 117.20! 130.21! 143.22! 156.23! 169.24! 182.25!
14   14! 28.14! 42.15! 56.16! 70.17! 84.18! 98.19! 112.20! 126.21! 140.22! 154.23! 168.24! 182.25! 196.26!
Et donc pour tout m>1 et n>1, A(m,n) = (m.n).(m+n-2)! et A(1,n) = n! et A(m,1) = m!
Vérifions:
A(15,6) = 10948059036794880000
15*6 = 90
19! = 121645100408832000
15.6.19! = 10948059036794880000 = A(15,6) = A(6,15)

Et voilà comment nous n'avons plus besoin de procédures de calcul récurrente et lente, ou de tableau à vecteurs pour calculer les A(m,n) que l'on sait maintenant calculer directement en fonction de m et n.

Code : Tout sélectionner

« * LAST + 2 - FACT * » »

1 "A" AREAD M:INPUT N:A=M*N:FOR I=1 TO M+N-2:A=A*I:NEXT I:PRINT STR$ M+","+ STR$ N,A:END

LBL"ACK  RCL Y  RCL Y  +  2  -  FACT  *  *  RTN 

LBL A  STO 0  X:Y  STO*0  + 2  -  x!  RCL*0 RTN

:ACK(m,n)
:Func
:If m<1 or n<1 Then
: Return 0
:Else
: Return m*n*(m+n-2)!
:EndIf
:EndFunc  
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
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6742
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Les nombres d'Ackerman

Message par gege » 28 mars 2020 12:00

Bonjour,
Wooooooowww
Bravo !!!
Tu as "fini" ce MPO...
Excellent
G.E.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2119
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 12:02

dprtl a écrit :
28 mars 2020 01:38
[…]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.
Je confirme, ma TI-92 II indique ACK(6,17) = 52112761010514362880000 Elle marche bien ta DM42 (surtout elle semble être correctement programmée)

D'après mon précèdent post:
A(6,17) = 102*21!
En effet 102*21! = 102*51090942171709440000 qui fait bien 5211276101514362880000

Pour prouver que A(6,17) MOD 52 == 0, il faut faire apparaître 52 c'est à dire 2².13 quelque part dans l'expression de A(6,17)

On a : 102 = 2 * 51 et 21! = 21*20*19*18*17*16*15*14*13*12! où 20 = 2*10

D'où on peut écrire A(6,17) = 2*51 * 21*2*10*19*18*17*16*15*14*13*12! = 2*2*13 * 51*21*10*19!
et donc A(6,17) = 52 * 10710*19!

d'où A(6,17) MOD 52 = 0
et A(6,17) DIV 52 = 10710.19! = 1302819025378590720000
gege a écrit :
28 mars 2020 01:54
[…]:Ackermann(3,n)=8*2^n-3
Hop Ackermann(4,1)=65533 en 0,04 s !
Oui oui, je hoppe hoppe tous les Ackerman, sauf ceux famille avec les Kellerman de METZ, en moins de 40ms.
Mais je ne trouve aucun A(3,n) ou A(4,n) égal à 65533 ? Tu es sûr de ta formule ?

Je propose A(3,n) = 3.n.(1+n)! = 3n.(n+1).n! = 3(n²+n).n! et A(4,n)=4.n.(n+2)! = 4n.(n+2).(n+1).n! = 4n.(n²+3n+2).n!

A(3,0) = 0 A(3,1)=3*2*1=6 A(3,2)=3*6*2=36 A(3,3)=3*12*6=216 A(3,4)=3*20*24=1440 A(3,5)=3*30*120=10800 etc...

En résumé :

Si m>0 et n>0 alors A(m,n)=A(n,m)=m*n*(m+n-2)! sinon A(m,n)=A(n,m)=0

Code : Tout sélectionner

mn  0      1       2       3      4      5      6      7       8       9      10      11      12      13      14
0   0      0       0       0       0       0       0       0       0       0       0       0       0       0       0
1   0   1. 0!   2. 1!   3. 2!   4. 3!   5. 4!   6. 5!   7. 6!   8. 7!   9. 8!  10. 9!  11.10!  12.11!  13.12!  14.13!
2   0   2. 1!   4. 2!   6. 3!   8. 4!  10. 5!  12. 6!  14. 7!  16. 8!  18. 9!  20.10!  22.11!  24.12!  26.13!  28.14!
3   0   3. 2!   6. 3!   9. 4!  12. 5!  15. 6!  18. 7!  21. 8!  24. 9!  27.10!  30.11!  33.12!  36.13!  39.14!  42.15!
4   0   4. 3!   8. 4!  12. 5!  16. 6!  20. 7!  24. 8!  28. 9!  32.10!  36.11!  40.12!  44.13!  48.14!  52.15!  56.16!
5   0   5. 4!  10. 5!  15. 6!  20. 7!  25. 8!  30. 9!  35.10!  40.11!  45.12!  50.13!  55.14!  60.15!  65.16!  70.17!
6   0   6. 5!  12. 6!  18. 7!  24. 8!  30. 9!  36.10!  42.11!  48.12!  54.13!  60.14!  66.15!  72.16!  78.17!  84.18!
7   0   7. 6!  14. 7!  21. 8!  28. 9!  35.10!  42.11!  49.12!  56.13!  63.14!  70.15!  77.16!  84.17!  91.18!  98.19!
8   0   8. 7!  16. 8!  24. 9!  32.10!  40.11!  48.12!  56.13!  64.14!  72.15!  80.16!  88.17!  96.18! 104.19! 112.20!
9   0   9. 8!  18. 9!  27.10!  36.11!  45.12!  54.13!  63.14!  72.15!  81.16!  90.17!  99.18! 108.19! 117.20! 126.21!
10  0  10. 9!  20.10!  30.11!  40.12!  50.13!  60.14!  70.15!  80.16!  90.17! 100.18! 110.19! 120.20! 130.21! 140.22!
11  0  11.10!  22.11!  33.12!  44.13!  55.14!  66.15!  77.16!  88.17!  99.18! 110.19! 121.20! 132.21! 143.22! 154.23!
12  0  12.11!  24.12!  36.13!  48.14!  60.15!  72.16!  84.17!  96.18! 108.19! 120.20! 132.21! 144.22! 156.23! 168.24!
13  0  13.12!  26.13!  39.14!  52.15!  65.16!  78.17!  91.18! 104.19! 117.20! 130.21! 143.22! 156.23! 169.24! 182.25!
14  0  14.13!  28.14!  42.15!  56.16!  70.17!  84.18!  98.19! 112.20! 126.21! 140.22! 154.23! 168.24! 182.25! 196.26!
On a bien : pour m>0 et n>0 la relation de récurrence :
m.A(m-1,n) + n.A(m,n-1)
= m. (m-1).n.(m+n-3)! + n.m.(n-1).(m+n-3)!
= [ m.(m-1).n + n.m.(n-1) ].(m+n-3)!
= m.[ (m-1).n + n.(n-1) ].(m+n-3)!
= m.n.[ (m-1) + (n-1) ].(m+n-3)!
= m.n. (m+n-2) . (m+n-3)!
= m.n. (m+n-2) !
= A(m,n)
Dernière édition par C.Ret le 28 mars 2020 13:20, édité 1 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 à 300 bauds
Fonctionne à 300 bauds
Messages : 109
Inscription : 28 déc. 2013 17:34

Re: Les nombres d'Ackerman

Message par Danny » 28 mars 2020 12:43

C.Ret a écrit :
28 mars 2020 12:02
Mais je ne trouve aucun A(3,n) ou A(4,n) égal à 65533 ? Tu es sûr de ta formule ?
Ça c'est avec la vraie définition, d'Ackermann avec 2 n : https://en.wikipedia.org/wiki/Ackermann_function :)

J'ai mis au propre les algos sur Prime pour la fonction d'Ackerman-Gege :) , en mode CAS finalement car il y a moins d'appels que pour Ackermann :

1. La fonction en version de base récursive :

Code : Tout sélectionner

#cas
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;
#end
2. La fonction en version non récursive optimisée avec factorielle :

Code : Tout sélectionner

#cas
Ackerman2(m, n):=
BEGIN
 CASE
  IF (m = 1) THEN
   RETURN n!;
  END;
  IF (n = 1) THEN
   RETURN m!;
  END;
  DEFAULT
   RETURN (m * n * (m + n - 2)!);
 END;
END;
#end
3. Le programme pour trouver le + petit nombre divisible :
(params : le diviseur et la valeur maxi pour m et n)

Code : Tout sélectionner

#cas
Ackerman_Divisible(diviseur, maxi):=
BEGIN
local m, n, ack, divis_mini, m_mini, n_mini;
divis_mini := 0;
m_mini := 0;
n_mini := 0;

 PRINT;
 FOR m FROM 1 TO maxi DO
  FOR n FROM m TO maxi DO
   ack := Ackerman(m, n); // ou Ackerman2 bien sûr :)
   PRINT("Ackerman(" + m + "," + n + ") = " + ack);
   IF (ack MOD diviseur == 0) THEN
    IF NOT(divis_mini) OR (ack < divis_mini) THEN
     divis_mini := ack;
     m_mini := m;
     n_mini := n;
    END;
   END;
  END;
 END;
 PRINT("Plus petit nb divisible par " + diviseur + " : Ackerman(" + m_mini + "," + n_mini + ") = " + divis_mini);
END;
#end
J'ai essayé seulement sur l'émulateur pour le moment :)

Image

Merci pour ce sujet sympa :P
Casio 3900p, 8500G, 9900GC
HP 45, 21, 42S, 28S, 32SII, 48SX, 48GX, 50g, Prime

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

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

Message par C.Ret » 28 mars 2020 16:21

Merci Danny pour ces précisions, je me demandais aussi d'où pouvait provenir le 2^n ?

Avec la nouvelle définition des nombres d'Ackerman-Gégé je me vois contraint de refondre mon code pour SHARP PC-1211:

Code : Tout sélectionner

1:P=1:FOR M=1 TO 13:F=P:FOR N=1 TO M:Q=MNF/52,F=FM+FN-F:IF Q<1.9€8 IF Q=INT Q PRINT M+.1N,52Q
2:NEXT N:P=PM:NEXT M
81 octets Registres F M N P Q

Trouve le plus petit A(m,n) non nul multiple de 52 en 2min10:
┌────────────────────────┐
│        13.1 6227020800.│
└────────────────────────┘
C'est à mon sens un peu lent, la version ci-dessous permet d'avoir la réponse en moins d'une minute:

Code : Tout sélectionner

1:P=1:FOR M=2 TO 14:F=P:FOR N=1 TO M:Q=MNF/52,F=FM+FN-F:IF Q>2€8 GOTO 4
2:IF Q=INT Q PRINT 52Q;M;N 
3:NEXT N
4:P=PM:NEXT M
84 octets Registres F M N P Q
┌────────────────────────┐
│6227020800.13.1.        │  52sec.
└────────────────────────┘
Et le petit utilitaire pour calculer A(m,n) :
En mode DEF, saisir m [SHIFT][ A ] n [ENTER] affiche A(m,n)

Code : Tout sélectionner

[MODE] Pro :
10:"A" AREAD M:INPUT N:A=MN:FOR F=1 TO M+N-2:A=FA:NEXT F:PRINT M;N;": ";A    (47 octets Registres A F M N)

[MODE] Def : 9 [SHIFT][ A ] 4 [ENTER] ┌────────────────────────┐
                                      │9.4.: 1437004800.       │                  ~5sec.
                                      └────────────────────────┘
             1 [SHIFT][ A ] 1 [ENTER] ┌────────────────────────┐
                                      │1.1.: 1.                │
                                      └────────────────────────┘
            21 [SHIFT][ A ] 7 [ENTER] ┌────────────────────────┐
                                      │21.7.: 5.928384483€ 28  │                 ~11sec.
                                      └────────────────────────┘
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
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2119
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret » 02 avr. 2020 09:04

Merci pour cet excellent MPO à gégé qui a la bonne habitude de soumettre au forum de petits sujets fort sympathiques volontairement proches de grands thèmes mathématiques.

J'ai eut beaucoup de chance de trouver avec un Pocket Computer peu puissant mais heureusement bien conçu et facile à programmer.

Le confinement fait aussi que j'ai eut un peu plus de temps qu'à l'habitude. En particulier quand il a fallu calculer A(15,6) sur ma TI-92 II à l'aide de la fonction ack(m,n) définie par récurrence :

Code : Tout sélectionner

:ack(m,n)
:Func
:If m<1 or n<1 Then
: Return 0
:ElseIf m=1 and n=1 Then
: Return 1
:Else
: Return m*ack(m-1,n)+n*ack(m,n-1)
:EndIf
:EndFunc
Avec la définition ci-dessus, il lui a fallu plus d'une heure ???

Alors, je me suis mis en tête de dessiner l'arbre représentant les appels récursifs pour calculer ack(15,6), mais je ne suis pas arrivé au bout de mon PowerPoint !!
mpo92 ACK_4_3_ tree.gif
mpo92 ACK_4_3_ tree.gif (11.71 Kio) Consulté 313 fois
C'est seulement à ce moment que j'ai ajouté un petit compteur pour déterminer le nombre d'appels en question. Et je n'étais donc pas prêt de venir à bout de mon arbre : il faut pas moins de 85271 appels récursifs pour calculer A(15,6).

Je comprends mieux pourquoi ce type de fonction est utilisé pour tester les systèmes à évaluation latente et autres astuces de mnémonisation, il y a rapidement de quoi mettre à rude épreuve la plupart des algorithmes.
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. .

Répondre

Revenir vers « Tous les Pockets »