2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks!! It was very clear and helpful:). $\endgroup$ – user1118686 Jul 25 '15 at 23:52
  • $\begingroup$ @user1118686: You are welcome! $\endgroup$ – mathlove Jul 25 '15 at 23:54
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.