De functie van Ackermann wordt als volgt gedefinieerd:
f(0,y) = y+1 f(x+1,0) = f(x,1) f(x+1,y+1) = f(x, f(x+1,y)) A(x) = f(x,x)Hierbij zijn x en y niet-negatieve gehele getallen. Bereken A(n) voor n=0,1,2,3,4,... Bereken de laatste 4 cijfers van A(10). Hoeveel cijfers heeft A(10) ongeveer?
Snel blijkt f(0,y) = y+1 en f(1,y) = y+2 en f(2,y) = 2y+3. Vervolgens f(3,y) = 2^(y+3)-3. (Want: f(3,y) ontstaat door telkens f(2,.) toe te passen op f(3,y-1), d.w.z. door herhaald met 2 te vermenigvuldigen.) Vervolgens is f(4,y) = 2^2^2^...^2 - 3, waarbij de exponent een stapel van y+3 tweeen is. Kortom: A(0) = f(0,0) = 1 en A(1) = f(1,1) = 3 en A(2) = f(2,2) = 7 en A(3) = f(3,3) = 61 en A(4) = 2^2^2^2^2^2^2-3 = 2^2^2^2^16-3 = 2^2^2^65536-3 is een beetje groot. A(5) is werkelijk onvoorstelbaar groot.
Hoe zit het met de laatste cijfers? Wel, als a == b (mod 5^j) dan a^5 == b^5 (mod 5^(j+1)). Dus 2^4 == 1 (mod 5), 2^20 == 1 (mod 25), 2^100 == 1 (mod 125). Dus geldt zeker 2^10^k == 1 (mod 5^k) als k > 1. Hieruit volgt dat als a == b (mod 10^j) dan ook 2^a == 2^b (mod 10^j) als b >= a >= j >= 2. Kortom, als we alleen de laatste j cijfers van a kennen dan kennen we ook de laatste j cijfers van 2^a. Met Mathematica vind je:
In[1]:= FixedPoint[Function[t, PowerMod[2, t, 10^4]],1]-3 Out[1]= 8733 In[2]:= FixedPoint[Function[t, PowerMod[2, t, 10^40]],1]-3 Out[2]= 8696872600159853338098615075353432948733zodat de laatste 4 cijfers van A(10) 8733 (en de laatste 40 cijfers 8696872600159853338098615075353432948733) zijn.