Super duper recursive function
Super duper recursive function
Okay, so safari crashed on me, so my wellwritten post on this super cool function I made was just destroyed, so I won't go into as much depth as I would if MY POSTS DIDN'T ALWAYS DISAPPEAR!!!! Sorry, just had to rant a little. Anyways, my function is basically defined as the (f(x),n) where you go to the f(n)th level recursion with f(x), which would probably mean something to you if stupid safari hadn't... *Exfret goes grumbling on about stuff*... Anyways, I'll just give you an example for when f(x)=x+1 and n=2.
First level: f(n)=2+1=3
Second level: f2(x)=f(x) applied to itself f(n) times=f(f(f(x)))=(((x)+1)+1)+1=x+3
f2(n)=n+3=2+3=5
Third level: ff(n)(x)=f3(x)=f2(x) applied to itself f2(n) times=f2(f2(f2(f2(f2(x)))))=(((((x)+3)+3)+3)+3)+3=x+3*5=x+15
ff(n)(n)=n+15=2+15=17
So you could return the function f(x)=x+15, or the number 17. This may not seem like a very quickly growing function, but if g(x)=x^(2^x), then (x+1,3)~g(g(g(870))). The arguments that returned 17 were f(x)=x+1 and n=2, but those that got this huge number were f(x)=x+1 and n=3. Oh, what a tiny change can do.
Here's the sequence varying n but keeping f(x) to x+1, starting at x=0:
1, 4, 17, a gazillion, then I don't even want to think about what comes after that...
Edit: It's actually 1,5,17 as ARP pointed out.
First level: f(n)=2+1=3
Second level: f2(x)=f(x) applied to itself f(n) times=f(f(f(x)))=(((x)+1)+1)+1=x+3
f2(n)=n+3=2+3=5
Third level: ff(n)(x)=f3(x)=f2(x) applied to itself f2(n) times=f2(f2(f2(f2(f2(x)))))=(((((x)+3)+3)+3)+3)+3=x+3*5=x+15
ff(n)(n)=n+15=2+15=17
So you could return the function f(x)=x+15, or the number 17. This may not seem like a very quickly growing function, but if g(x)=x^(2^x), then (x+1,3)~g(g(g(870))). The arguments that returned 17 were f(x)=x+1 and n=2, but those that got this huge number were f(x)=x+1 and n=3. Oh, what a tiny change can do.
Here's the sequence varying n but keeping f(x) to x+1, starting at x=0:
1, 4, 17, a gazillion, then I don't even want to think about what comes after that...
Edit: It's actually 1,5,17 as ARP pointed out.
Last edited by exfret on Thu Sep 25, 2014 7:16 pm, edited 1 time in total.
Nobody ever notices my signature. ):
Re: Super duper recursive function
Sounds like a bit of a twist on the ackermann function?
Either way, sounds like a nice exercise in Haskell.
However, I can't quite understand it. I tried to code it to get a sense of it but I can't quite understand what we're doing here. So what does this function do then, exactly?
Either way, sounds like a nice exercise in Haskell.
However, I can't quite understand it. I tried to code it to get a sense of it but I can't quite understand what we're doing here. So what does this function do then, exactly?
Convincing people that 0.9999... = 1 since 2012

 Posts: 523
 Joined: Mon Jun 03, 2013 4:54 pm
Re: Super duper recursive function
Looks to me that:
The examples given seem to introduce an additional level of recursion though. I'll analyze it in a sec.
Edit 1: First guess.
This doesn't seem to match up quite right, though.
FINALLY.
Final Draft, Pseudocode:
Some notes:
It's not 1, 4, 17, it's 1, 5, 17.
257 is a gazillion.
Exfret(f(x)=x+1, n=2, k) seems to grow only exponentially. Looks similar for n>2.
Code: Select all
H(f, n) takes a function f and a (nonnegative integral) number n, and returns a function. f takes a number x and returns a number.
H(f, n) = f(f(f(...f(x)...))
\ f(n) f's /
So H(f(x)=x+1*,5) = f(f(f(f(f(f(x)))))), or x+6.
*λx.(x+1) for computing nerds.
Edit 1: First guess.
Code: Select all
Ok, so the examples are using various subscripted versions of the function H. In this case, H is defined as
H_a(f, n) = f(f(f(...f(x)...))
\ H_(a1)(f, n) f's/
Where H_1(f, n) is defined to be f(n).
So H_3(f(x)=x+1, 3) = H_2(f(x)=x+1, 3) f's
H_2(f(x)=x+1, 3) = H_1(f(x)=x+1, 3) f's
H_1(f(x)=x+1, 3) = f(3) = 4
H_2(f(x)=x+1, 3) = f(f(f(f(3)))) = 7
H_3(f(x)=x+1, 3) = f(f(f(f(f(f(f(3)))))))
So H_3(f(x)=x+1, 3) = 10.
FINALLY.
Code: Select all
Calling with f(x), n, and k
{
M_k(x) = M_(k1)(n) copies of M_(k1)(x)
M_1(x) = f(x)
return M_k(n)
}
f(x) = x+1, n=2, varying k, we get
M_1(x) = f(x)
At n=2, M_1(2) = f(2) = 2+1 = 3
M_2(x) = M_1(n) copies of M_1(x)
= 3 copies of M_1(x)
= 3 copies of f(x)
= f(f(f(x)))
Or in other words M_2(x) = x+1+1+1 = x+3
At n=2, M_2(2) = 2+3 = 5
M_3(x) = M_2(n) copies of M_2(x)
= 5 copies of M_2(x)=x+3
= M_2(M_2(M_2(M_2(M_2(x)))))
In other words M_3(x) = x+3+3+3+3+3 = x+15
At n = 2, M_3(2) = 2+15 = 17
One further...
M_4(x) = M_3(n) copies of M_3(x)
= 17 copies of M_3(x)=x+15
= x+255
ergo M_4(2) = 257
M_5(x) = 257 copies of x+255
= x+65535
etc.
Final Draft, Pseudocode:
Code: Select all
Exfret(k, f(x), n) =
{
New Function M(k, x) = M(k1, x) copies of M(k1, n) \* In other words M(k1, M(k1, M(k1, ... M(k1, n)))...) *\
\* Implementation of the above comment requires an auxiliary variable or loop, probably *\
M(1, x) = f(x)
Return M(k, n)
}
Some notes:
It's not 1, 4, 17, it's 1, 5, 17.
257 is a gazillion.
Exfret(f(x)=x+1, n=2, k) seems to grow only exponentially. Looks similar for n>2.
$1 = 100¢ = (10¢)^2 = ($0.10)^2 = $0.01 = 1¢ [1]
Always check your units or you will have no money!
Always check your units or you will have no money!
Re: Super duper recursive function
Oh, sorry about not explaining further. I expected that you'd all be confused, but I just wanted to see if it sparked some interest and I didn't want to rewrite my post again (like I said). Now that a further explanation would be for good use, I'll explain it more. ARP, you were on the right track. I'll just explain it from the start:
Given a function f(x) and a number n, (f(x),n) is defined as the "f(n)th level recursion." Now to explain what "f(n)th level recursion" means. Here's a list of some of the first levels of recursion:
First level: f(n) (so if f(n)=1, then you would just stop here and return f(x) (or f(n), I haven't really decided whether my function should return a function or a number).
Second level: f2(n).
f2(x) is defined as f(x) applied to itself f(n) times. For example, if f(x)=2*x and n=1, then f(n)=2, so f2(x)=f(f(x))=2*2*x=4*x, meaning f2(n)=4*1=4. Since f(n)=2 in this case, we would actually stop here and be done because we would have recursed through the f(n)th/second level already.
Third level: ff(n),3(n).
I just put the 3 by there to differentiate it from further levels. (3 for 3rd level of recursion). ff(n),3(x)=ff(n)1,3(x) applied to itself ff(n)1,3(n) times. So, if we took f(x)=3*x and n=1, then we would start with finding f(n)=3. f2(x)=f(f(f(x)))=2(2(2(x)))=8*x. f2(n)=8*1=8, so f3(x)=f2(f2(f2(f2(f2(f2(f2(f2(f2(x))))))))=8(8(8(8(8(8(8(8(x))))))))=8^8*x. Also, f3(n)=8^8*1=8^8. Because f(n)=3, f3(x)=ff(n)(x), so we would be done. Also since f(n)=3, we would be done with the third recursion and therefore need not go further in this example.
Fourth level: ff(n),4(n).
ff(n),4(x)=ff(n)1,4(x) put through the third level recursion. This means that if g1,3(x)=ff(n)1,4(x), then gf(f(n)1,4)(n),3(x)=ff(n),4(x).
Fifth level: And so on.
Basically, you just take each new function and send it back through the last level of recursion f(n) times until you get to the f(n)th level recursion.
Because I probably didn't explain this very well, I've attached a picture that hopefully helps.
Edit in response to ARP's edit (which came after I started to post this): You got the first parts right, the 1, 5, 17 (good catch on that 5). After that, though, you go into the fourth level recursion that I didn't write anything about it my very undetailed post. This recursion causes you to need to square what is returned multiple times, which is why you get about g(g(g(870))) where g=x^(2^x) for f(x)=x+1 and n=3. Also, for the gazillion, you had n=2 and not n=3 anyways. Finally, k equals f(n), if that help clears some stuff about my function up. (In the fourth level recursion, M_k(x) becomes k after each third level recursion, and you do that f(n) times, if that makes any sense. This means that after each third level iteration, the returned function goes through another thirdlevel iteration until it has gone through f(n) iterations..) Hopefully, this helps to unconfuse you.
Given a function f(x) and a number n, (f(x),n) is defined as the "f(n)th level recursion." Now to explain what "f(n)th level recursion" means. Here's a list of some of the first levels of recursion:
First level: f(n) (so if f(n)=1, then you would just stop here and return f(x) (or f(n), I haven't really decided whether my function should return a function or a number).
Second level: f2(n).
f2(x) is defined as f(x) applied to itself f(n) times. For example, if f(x)=2*x and n=1, then f(n)=2, so f2(x)=f(f(x))=2*2*x=4*x, meaning f2(n)=4*1=4. Since f(n)=2 in this case, we would actually stop here and be done because we would have recursed through the f(n)th/second level already.
Third level: ff(n),3(n).
I just put the 3 by there to differentiate it from further levels. (3 for 3rd level of recursion). ff(n),3(x)=ff(n)1,3(x) applied to itself ff(n)1,3(n) times. So, if we took f(x)=3*x and n=1, then we would start with finding f(n)=3. f2(x)=f(f(f(x)))=2(2(2(x)))=8*x. f2(n)=8*1=8, so f3(x)=f2(f2(f2(f2(f2(f2(f2(f2(f2(x))))))))=8(8(8(8(8(8(8(8(x))))))))=8^8*x. Also, f3(n)=8^8*1=8^8. Because f(n)=3, f3(x)=ff(n)(x), so we would be done. Also since f(n)=3, we would be done with the third recursion and therefore need not go further in this example.
Fourth level: ff(n),4(n).
ff(n),4(x)=ff(n)1,4(x) put through the third level recursion. This means that if g1,3(x)=ff(n)1,4(x), then gf(f(n)1,4)(n),3(x)=ff(n),4(x).
Fifth level: And so on.
Basically, you just take each new function and send it back through the last level of recursion f(n) times until you get to the f(n)th level recursion.
Because I probably didn't explain this very well, I've attached a picture that hopefully helps.
Edit in response to ARP's edit (which came after I started to post this): You got the first parts right, the 1, 5, 17 (good catch on that 5). After that, though, you go into the fourth level recursion that I didn't write anything about it my very undetailed post. This recursion causes you to need to square what is returned multiple times, which is why you get about g(g(g(870))) where g=x^(2^x) for f(x)=x+1 and n=3. Also, for the gazillion, you had n=2 and not n=3 anyways. Finally, k equals f(n), if that help clears some stuff about my function up. (In the fourth level recursion, M_k(x) becomes k after each third level recursion, and you do that f(n) times, if that makes any sense. This means that after each third level iteration, the returned function goes through another thirdlevel iteration until it has gone through f(n) iterations..) Hopefully, this helps to unconfuse you.
 Attachments

 IMG_19070.jpg (233.35 KiB) Viewed 10189 times
Nobody ever notices my signature. ):
Re: Super duper recursive function
So basically:
h(f, x, n)
Equals f(x) if f(n) = 1, f(f(x)) if f(n) = 2 and so on and so forth?
Here, I whipped this up in haskell.
It doesn't seem to work though, it isn't giving me the results you said it would.
Not sure if you can speak haskell, but here's basically what it does, this is probably where I'm misunderstanding:
It takes a function and two numbers. So f, x, n.
Then it runs f(x) if f(n) = 1, f(f(x)) if f(n) = 2, basically f(n) f's
What am I getting wrong here?
h(f, x, n)
Equals f(x) if f(n) = 1, f(f(x)) if f(n) = 2 and so on and so forth?
Here, I whipped this up in haskell.
Code: Select all
higgs::(Integer > Integer) > Integer > Integer > Integer
higgs f x n = iterate f x !! (f n)
Not sure if you can speak haskell, but here's basically what it does, this is probably where I'm misunderstanding:
It takes a function and two numbers. So f, x, n.
Then it runs f(x) if f(n) = 1, f(f(x)) if f(n) = 2, basically f(n) f's
What am I getting wrong here?
Convincing people that 0.9999... = 1 since 2012

 Posts: 523
 Joined: Mon Jun 03, 2013 4:54 pm
Re: Super duper recursive function
That looks like my initial guess, which turned out to be wrong. Try implementing my Exfret(f, k, n). Your Higgs(f, x, n) returns a function which is applied to x it seems.robly18 wrote:So basically:
h(f, x, n)
Equals f(x) if f(n) = 1, f(f(x)) if f(n) = 2 and so on and so forth?
Here, I whipped this up in haskell.
It doesn't seem to work though, it isn't giving me the results you said it would.Code: Select all
higgs::(Integer > Integer) > Integer > Integer > Integer higgs f x n = iterate f x !! (f n)
Not sure if you can speak haskell, but here's basically what it does, this is probably where I'm misunderstanding:
It takes a function and two numbers. So f, x, n.
Then it runs f(x) if f(n) = 1, f(f(x)) if f(n) = 2, basically f(n) f's
What am I getting wrong here?
Edit: That paper; how many levels of recursion is that  where is it in the fast growing hierarchy?
$1 = 100¢ = (10¢)^2 = ($0.10)^2 = $0.01 = 1¢ [1]
Always check your units or you will have no money!
Always check your units or you will have no money!