Consider the three-variable function defined at the following way for all natural numbers $n,x,y$ :
$f(0,x,y) = x+y $
$f(n,x,0) = x$
$f(n,x,y) = f(n-1, $ $ $ $f(n,x,y-1) , $ $ $ $f(n,x,y-1)+y ) $.
For some values calculating the function is easy and for others I am having a very hard time... Can someone tell me what are the exact values of $f(2,1,3),f(3,3,3), f(2,3,1)$? If possible I would also like to know how could calculate it more efficiently.
On
This function looks like a modified version of the Ackermann function:
https://en.wikipedia.org/wiki/Ackermann_function
So it means that it will gives you huge numbers really fast.
On
I ran a short recursion program. For $f(2,3,1)$ I get the output (printing every time the function gets called):
2 3 1
2 3 0
2 3 0
1 3 4
1 3 3
1 3 2
1 3 1
1 3 0
1 3 0
0 3 4
1 3 1
1 3 0
1 3 0
0 3 4
0 7 9
1 3 2
1 3 1
1 3 0
1 3 0
0 3 4
1 3 1
1 3 0
1 3 0
0 3 4
0 7 9
0 16 19
1 3 3
1 3 2
1 3 1
1 3 0
1 3 0
0 3 4
1 3 1
1 3 0
1 3 0
0 3 4
0 7 9
1 3 2
1 3 1
1 3 0
1 3 0
0 3 4
1 3 1
1 3 0
1 3 0
0 3 4
0 7 9
0 16 19
0 35 39
74
With $74$ being the value of the function at this point. So you can already forget about calculating it by hand :). For the other parameters I do not get a result. For $f(2,1,3)$ I get the message "maximum recursion death exceeded", and for $f(3,3,3)$ the programm gets stuck in some kind of loop, but I'm not sure.
First of all, let us find an efficient formula.$$f(1,a,b)=f(0,f(1,a,b-1),f(1,a,b-1)+b)=2f(1,a,b-1)+b$$ Here, let $g_b=f(1,a,b)$. Then, $$g_b=2g_{b-1}+b\iff g_b+b+2=2(g_{b-1}+b-1+2).$$ So, let $h_b=g_b+b+2$, we have $h_b=2h_{b-1}$. So, $h_b=2^{b}h_0$, i.e. $g_b+b+2=2^{b}(g_0+2)$, i.e. $$\color{red}{f(1,a,b)}=2^{b}(f(1,a,0)+2)-b-2=\color{red}{2^b(a+2)-b-2}\tag1$$ In the following, let us use $(1)$ to find the values.
$$f(2,1,0)=1$$ $$f(2,1,1)=f(1,f(2,1,0),f(2,1,0)+1)=f(1,1,2)=2^2(1+2)-2-2=8$$ $$f(2,1,2)=f(1,f(2,1,1),f(2,1,1)+2)=f(1,8,10)=2^{10}(8+2)-10-2=10228$$ $$\color{red}{f(2,1,3)}=f(1,f(2,1,2),f(2,1,2)+3)=f(1,10228,10231)=2^{10231}(10228+2)-10231-2=\color{red}{10230\cdot 2^{10231}-10233}$$
$$f(2,3,0)=3$$ $$\color{red}{f(2,3,1)}=f(1,f(2,3,0),f(2,3,0)+1)=f(1,3,4)=2^4(3+2)-4-2=\color{red}{74}$$ $$f(2,3,2)=f(1,f(2,3,1),f(2,3,1)+2)=f(1,74,76)=2^{76}(74+2)-76-2=76\cdot 2^{76}-78$$ $$f(2,3,3)=f(1,f(2,3,2),f(2,3,2)+3)=f(1,76\cdot 2^{76}-78,76\cdot 2^{76}-78+3)=2^{76\cdot 2^{76}-78+3}(76\cdot 2^{76}-78+2)-(76\cdot 2^{76}-78+3)-2$$ $$f(3,3,0)=3$$ $$f(3,3,1)=f(2,f(3,3,0),f(3,3,0)+1)=f(2,3,4)=f(1,f(2,3,3),f(2,3,3)+4)=f(1,2^{76\cdot 2^{76}-78+3}(76\cdot 2^{76}-78+2)-(76\cdot 2^{76}-78+3)-2,2^{76\cdot 2^{76}-78+3}(76\cdot 2^{76}-78+2)-(76\cdot 2^{76}-78+3)-2+4)=\cdots$$
$f(3,3,2)=\cdots$
$f(3,3,3)=\cdots$
I stop here because the values are huge. I hope that you see how to get the value of $f(3,3,3)$.