# What is the value of this function?

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.

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)$.

• Thanks!! It was very clear and helpful:). – user1118686 Jul 25 '15 at 23:52
• @user1118686: You are welcome! – mathlove Jul 25 '15 at 23:54

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.

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.