How should I deal with this crazy function?

🎙️ ReplaceableName · 42 points · Posted at 17:55:51 on May 16, 2016 · (Permalink)*

There was something I was trying to describe using a function but I got a very weird function which I don't really know how to deal with.

Here is what I can tell about it:

It takes two positive intreger values 'n' and 'x' (could be 0).

I call it f(n,x) and I think that those properties I found are enough to tell everything about the function.

f(n,0)=n+1

f(0,x)=0 (only for x=/=0, because f(0,0)=1)

And here is the complicated one:

f(n,x)=f(f(...f(f(n,x-1),x-1)...,x-1),x-1)

and there are n functions inside

It's probably not very clear so here are examples:

f(2,x)=f(f(2,x-1),x-1)  

f(3,x)=f(f(f(3,x-1),x-1),x-1)

f(4,x)=f(f(f(f(4,x-1),x-1),x-1),x-1)

From this you can derive that:

f(n,1)=2n

f(n,2)=n*2^n

And for x=>3 I think there is no algebreic way to describe it.

So is there a better way to treat this function?

If you happen to know minecraft command blocks this is what it describes:

https://redd.it/4jmf33^[1]

[1]

Mathy stuff

edderiofer · 31 points · Posted at 18:05:05 on May 16, 2016 · (Permalink)

f(n,x)=f(f(...f(f(n,x-1),x-1)...,x-1),x-1) and there are n functions inside

Oh no. Get this thing away from me! It's even worse than the Ackermann Function!

Also, I think you meant:

f(4,x)=f(f(f(f(4,x-1),x-1),x-1),x-1)?

Oh, and this definition:

f(0,x)=n

Seems to be invalid. Do you mean that f(0,x) = 0?

🎙️ ReplaceableName · 7 points · Posted at 18:06:42 on May 16, 2016 · (Permalink)

right thanks

SpeakKindly · 27 points · Posted at 18:43:48 on May 16, 2016 · (Permalink)

We can bound f(n,2) between 2^n and 2^2^n (obviously, because we have a closed form). I'm going to switch to Knuth's up-arrow notation, writing these as 2↑n and 2↑2↑n.

This lets us bound f(n,3) between two expressions of the form 2↑2↑...↑n, one with n ↑'s and one with 2n ↑'s. By giving away rather a lot, we can write 2↑↑n < f(n,3) < 2↑↑2↑↑n; this is rather tedious, so I leave it as an exercise to the reader.

This lets us bound f(n,4) between two expressions of the form 2↑↑2↑↑...↑↑n, one with n ↑↑'s and one with 2n ↑↑'s. The same argument lets us write 2↑↑↑n < f(n,4) < 2↑↑↑2↑↑↑n.

Iterating, we get the inequality 2↑^x-1n < f(n,x) < 2↑^x-12↑^x-1n. (I haven't checked, but possibly this might require n to be at least 2 or something).

This is rather terrible as an inequality but gives you the right "rate of growth". If you look closely at the steps, you find that the lower bound is much closer to the truth than the upper bound, so f(n,x) is "essentially the same" as the Ackermann function, which has a similar recurrence and satisfies A(x,n) = 2↑^x-2(n+3) - 3.

Superdorps · 12 points · Posted at 21:36:34 on May 16, 2016 · (Permalink)

You will crash servers by using up all the memory just with f(3,3); it's about 2^{2^134217755.} :-)

🎙️ ReplaceableName · 2 points · Posted at 11:39:28 on May 17, 2016 · (Permalink)

Yeah it's exactly this

402653184*2^402653184

I actually tried while trying to figure out the function :)

My game got to about 45,000 entities and then I just left the game and deleated all the entities with MCEdit.

Xgamer4 · 11 points · Posted at 21:39:40 on May 16, 2016 · (Permalink)

Just for kicks, I wrote a quick python script implementing this:

import sys
iter = 0
def f(n,x):
    global iter
    iter = iter + 1

    if n < 0 or x < 0:
        return -1;

    if x == 0:
        return n+1;

    if n == 0:
        return 0;
    newN = n
    for i in range(n):
        newN = f(newN, x-1)
    #print str(newN) + "\n"
    return newN

print f(int(sys.argv[1]),int(sys.argv[2]))
print iter

In theory it was a cool idea. In practice, basically anything causes it to gobble up all the RAM the python interpreter can get its grubby hands on before it terminates it with a MemoryError.

schoolmonkey · 6 points · Posted at 03:06:02 on May 17, 2016 · (Permalink)

Just to test out my python skills (learning it for fun), I decided to do the same.

from functools import reduce
def f(n,x):
    if x == 0:
        return n+1
    if n == 0:
        return 0
    return reduce(f, [x-1]*n, n)

It's almost exactly the same in effect, just uses the built-in reduce to simplify it.

For those curious (like I was), the program can quickly compute (no more than a couple seconds) up to f(24,2)=402,653,184 and f(2,3)=2048 with fixed x before throwing a MemoryError, and can compute up to f(1,496)=2 with fixed n before throwing a RecursionError.

It could probably be improved by adding the closed form solutions given in OP for n=1 and 2, but that is kind of irrelevant.

PupilofMath · 3 points · Posted at 12:02:22 on May 17, 2016 · (Permalink)

My Haskell program if anyone wants it:

import Data.List
f n x
    | x == 0      = n+1
    | n == 0      = 0
    | otherwise = iterate f' n !! n
        where f'  = flip f $ x-1

Superdorps · 2 points · Posted at 07:52:56 on May 17, 2016 · (Permalink)*

You could probably get it to do most things in the f(n,3) range if you included cases for n==1 and n==2, but f(n,4) is still likely to run out of either memory or stack space.

EDIT: Well, representing f(3,3) just as it is might cause out-of-memory errors, considering that it has something on the order of 10^40000000 digits. So never mind :-)

N8CCRG · 6 points · Posted at 20:43:03 on May 16, 2016 · (Permalink)

f(1,x) = f(1,x-1) = f(1,x-2) = ... = f(1,0) = 2?

🎙️ ReplaceableName · 1 points · Posted at 04:19:34 on May 17, 2016 · (Permalink)

Yes!

hexagonhexagon · 6 points · Posted at 02:00:27 on May 17, 2016 · (Permalink)

This looks like part of the fast-growing hierarchy, where the f(n,x) you describe is f_x(n) in the hierarchy. I don't see anything that has closed forms for x>3, but it might be worthwhile to look at.

deeschannayell · 11 points · Posted at 20:28:54 on May 16, 2016 · (Permalink)

Upvote for coming to /r/math about Minecraft!