# Golf the fast growing hierarchy

The fast growing hierarchy is a way of categorizing how fast functions are growing, defined the following way (for finite indices):

• $$\ f_0(n)=n+1 \$$
• $$\ f_k(n)=f_{k-1}^n(n)\$$ with $$\f^n\$$ meaning repeated application of the function f

## Examples

f0(5) = 6
f1(3) = f0(f0(f0(3))) = 3+1+1+1= 6
f2(4) = f1(f1(f1(f1(4)))) = 2*(2*(2*(2*4))) = 2⁴*4 = 64
f2(5) = f1(f1(f1(f1(f1(5))))) = ... = 2⁵*5 = 160
f2(50) = f1⁵⁰(50) = ... = 2⁵⁰*50 = 56294995342131200
f3(2) = f2(f2(2)) = f2(f2(2^2*2))) = f2(8) = 2^8*8 = 2048
f3(3) = f2(f2(f2(3))) = f2(f2(2³*3)) = f2(2²⁴*24)=2⁴⁰²⁶⁵³¹⁸⁴*402653184 = ...
f4(1) = f3(1) = f2(1) = f1(1) = f0(1) = 2
f4(2) = f3(f3(2)) = f3(2048) = f2²⁰⁴⁸(2048) = ...
...


shortcuts:

f1(n) = f0(...f0(n))) = n+n*1 = 2*n
f2(n) = f1(... f1(n)...)  = 2^n * n


Your goal is to write a program of function that given two positive integers $$\k\$$ and $$\n\$$ outputs $$\f_k(n)\$$

## Rules

• Given unlimited time and using unbounded integer types the algorithm you program is using should compute the correct result of f_k(n) for arbitrarily large n and k (even if the program will not finish in the lifetime of the universe)
• Your program only has to work for values that fit in a signed 32-bit integer
• Supporting the case $$\k=0\$$ is optional
• This is , the shortest solution in bytes wins
• Is Supporting the case 𝑘=0 is optional correct? Shouldn't it read n=0 instead? k=0 is the recursion base, so you can't exclude it meaningfully. Commented Sep 4, 2023 at 19:49
• @SUTerliakov We can, since we know f1(n)=2n. Also, the domain is previously specified to be positive integers $k,n$.
– att
Commented Sep 4, 2023 at 21:08
• Ough, I missed the positive specifier in your question, it saves 6 bytes, thanks! Linked Wikipedia article allows n == 0 (with standard identity function $f^0(x) = x$ for n == 0), so I didn't expect to find such relaxation in this question. Commented Sep 4, 2023 at 21:12
• @UndoneStudios depends on the compilation error, anything about numbers/recursion depths being to large is okay. The important thing is that the algorithm theoretically works for larger k Commented Sep 5, 2023 at 8:45
• What about syntax errors due to deeply nested parenthesis? Commented Sep 5, 2023 at 12:27

# K (ngn/k), 16 bytes

{{y x/y}x}/[;1+]


Try it online!

A curried function that takes k and then n. Call it as f[k][n]. (f[k;n] doesn't work.)

The trick here is to iterate directly on the function f. The formula $$\f_k(n) = f_{k-1}^{n}(n)\$$ can be seen as a transformation on a function $$\f_{k-1}\$$ to $$\f_k\$$. Given a function x ($$\f_{k-1}\$$) and input value y ($$\n\$$), $$\f_k(n)\$$ can be written as y x/y, and {y x/y}x is the partially applied function $$\f_k\$$ that we want. We can iterate this transformation k times to $$\f_0\$$ (1+) to get $$\f_k\$$. However, k{y x/y}/(1+) invokes a wrong overload of / because {y x/y} itself is syntactically dyadic. So I put it in {...x} to make it monadic.

• I'd be curious to see your take on a J answer. I have one idea using recursive reductions which I haven't implemented yet, but the problem is tricky in J if you want to approach it using higher order fns, because then you need to implement a recursive conjunction, and my attempt there ended in a stack error. Would love to see any other better ideas. Commented Sep 4, 2023 at 4:50
• I've added my recursive reduce solution. There must be a shorter approach though. Commented Sep 4, 2023 at 6:03

# x86 32-bit machine code, 18 bytes

4A 78 0C 51 89 C1 E8 F5 FF FF FF E2 F9 59 48 40 42 C3


Try it online!

Following the regparm calling convention, this takes n in EAX and k in EDX, and returns a number in EAX. For easier recursion, this function also preserves the values of EDX and ECX (ending with them unchanged).

In assembly:

f:  dec edx         # Subtract 1 from k in EDX.
js z            # Jump if the result is negative (k was 0).
push ecx        # Save the value of ECX onto the stack.
mov ecx, eax    # Set ECX to n. This will be the iteration count.
r:  call f          # Recursive call, to apply fₖ₋₁ to EAX.
loop r          # Subtract 1 from ECX and jump back to repeat if it's nonzero.
pop ecx         # Restore the value of ECX from the stack.
dec eax         # Subtract 1 from EAX, cancelling out the next instruction.
z:  inc eax         # Add 1 to n in EAX.
inc edx         # Add 1 to EDX, restoring the value of k.
ret             # Return.


# K (ngn/k), 19 bytes

{y$[x;o@x-1;]/y+~x}  Try it online! {y$[x;o@x-1;]/y+~x}    / function with arguments x:k, y:n
$[x;o@x-1;] / if x>0, f_(k-1), else identity function y / / Apply the selected function n times to: y+~x / n + [0=k]  # Charcoal, 38 bytes Ｆ²⊞υＮＷ⊖Ｌυ«≔⊟υθ≔⊟υη¿η«Ｆθ⊞υ⊖η⊞υθ»⊞υ⊕θ»Ｉυ  Try it online! Link is to verbose version of code. Explanation: Ｆ²⊞υＮ  Push k and n to the predefined empty list. Ｗ⊖Ｌυ«  Repeat until the list only contains one value. ≔⊟υθ≔⊟υη  Extract k and n for the deepest recursion depth. ¿η«  If k is non-zero, then... Ｆθ⊞υ⊖η  ... push n copies of k-1, representing the recursive calls... ⊞υθ  ... and push k back as the argument. »⊞υ⊕θ  Otherwise just push n incremented as the result of f0(n). »Ｉυ  Output the final value. 52 bytes for a version optimised for k<3: Ｆ²⊞υＮＷ⊖Ｌυ«≔⊟υθ≔⊟υη≡η⁰⊞υ⊕θ¹⊞υ⊗θ²⊞υ×Ｘ²θθ«Ｆθ⊞υ⊖η⊞υθ»»Ｉυ  Try it online! Link is to verbose version of code. # Wolfram Language (Mathematica), 30 bytes Nest[fNest[f,#,#]&,#+1&,#]&  Try it online! Input [k][n]. # J, 24 bytes >:@](<:@[$:^:]])@.(0<[)


Attempt This Online!

-4 thanks to Bubbler for this straightforward approach

# J, 28 27 bytes

>:@](]$:/@,~]#_1+[)@.(0<[)  Attempt This Online! -1 using thanks to Bubbler's 0<] instead of 0=] idea This approach conceives uses a reduction which expands its left argument in place recursively: 2 f 3 1 1 1 f 3 1 1 0 0 0 f 3 1 1 0 0 f 4 1 1 0 f 5 1 1 f 6 1 0 0 0 f 6 ... etc ...  And this is what the above code does: • @.(0=[) If the left arg is 0... • (1+]) Return 1. Otherwise... • ]#_1+[ Repeat "left arg minus 1" as many times as the right arg... • ]...,~ Prepend the right arg... • $:/@ And continue reducing the result using this fn.
• Cool idea, but unfortunately following the definition more directly is shorter. Commented Sep 4, 2023 at 6:20
• Right, good point... I think I got thrown off in my thinking because I was originally trying to find a solution that actually return a fn, but that's not why my current answer is doing anyway, and I think a misreading of the OP's task anyway. Commented Sep 4, 2023 at 6:34

# J, 15 bytes

'>:'".@,'^:]'&,


Attempt This Online!

Takes k on the left as a number, and n on the right as a string.

Without ".@, the function constructs the expression >:^:]^:] ... ^:]n as a string, where ^:] is repeated k times.

f^:]n applies f n times to the initial value n. $$\f_0\$$ is increment, which is >:. $$\f_1(n) = f_0^n(n)\$$ is >:^:]n. In general, $$\f_k(n) = f_{k-1}^n(n)\$$ can be expressed as (f_{k-1})^:]n, and expanded recursively down to k=0, we get the expression above.

# Jelly, 9 bytes

ẋ@⁾¹¡”‘;v


Try it online!

The same strategy applied to Jelly. ‘ (increment) plus ¹¡ (repeat argument times) repeated k times, evaluated and applied to n.

• Really clever on the J one. Commented Sep 4, 2023 at 7:01

# R, 50 bytes

f=function(k,n){if(k)for(i in 1:n)n=f(k-1,n);n+!k}


Try it online!

# Python 3, 96 79 70 69 63 61 59 58 bytes

g=lambda k,n:-~n*(k<1)or eval(f"({'n:=g(k-1,n),'*n})")[-1]


It takes time to compute k=2, n=50, but it should be completed after some time...

While this answer is longer, I'm keeping it because it inspired the other two winning answers in Python:

70 67 65 bytes if Python could handle huge nested parentheses (this answer is allowed, but other golfs based on this are already present, with the other answers being this one by xnor, and this other one by SUTerliakov):
f=lambda k,n:n+1if k>1else eval(f"{n*('f(%d,'%(k-1))}{n}{')'*n}")

• The lambda version can be 68 bytes by replacing if not k else with if k==0else Commented Sep 3, 2023 at 14:12
• @noodleman Or even k<1.
– Neil
Commented Sep 3, 2023 at 14:16
• n+1 can be ~-n and same as above, not k with k<1. I would also assume you could do maybe do something like for i in range(n):n=g(k-1,n) instead?
– Jo King
Commented Sep 4, 2023 at 5:11
• @JoKing ~-n is n-1, not n+1. ~-1 == 0, ~-2 == 1. Commented Sep 4, 2023 at 20:00
• You can post that on your own, I'm opting to support n=0 because my current answer supports it Commented Sep 5, 2023 at 4:52

0%n=n+1
k%n=iterate((k-1)%)n!!n


Try it online!

Writing out the definition.

34 bytes

q((>>=)id.q)(+1)
q=((!!).).iterate


Try it online!

A pointfree mess.

• Fun 32, kinda stretching sequence IO: l=(1+):[\n->iterate f n!!n|f<-l] Commented Sep 4, 2023 at 2:12

# JavaScript (ES6), 39 bytes

A shorter version with a single recursive function suggested by @att.

f=(k,n,i=n)=>k*i?f(k-1,f(k,n,i-1)):n+!k


Try it online!

# JavaScript (ES6), 42 bytes

f=(k,n)=>k--?(g=i=>f(k,--i?g(i):n))(n):n+1


Try it online!

### Commented

f = (k, n) => // f is a recursive function taking (k, n)
k-- ?         // if k is not 0 (decrement it afterwards):
( g = i =>  //   g is another recursive function taking a counter i
f(        //   do a recursive call to f:
k,      //     pass the updated value of k
--i ?   //     decrement i, if it's not 0:
g(i)  //       use the result of a recursive call to g for n
:       //     else:
n     //       final call: use n
)         //   end of recursive call to f
)(n)        //   initial call to g with i = n
:             // else (k = 0):
n + 1       //   f0(n) = n + 1

• 39 bytes
– att
Commented Sep 3, 2023 at 21:25
• @att Nice! (My initial attempt was close to that, but I messed it up and changed my mind.) Commented Sep 3, 2023 at 21:32

# Python, 50 bytes

f=lambda k,n:k and eval(n*'f(k-1,'+'n'+')'*n)or-~n


Try it online!

Based on the second solution of UndoneStudios. In practice gives a MemoryError for larger values from trying to generate huge strings of Python code.

# Jelly, 10 bytes

x@’ßƒ⁸ʋ‘⁹?


A dyadic Link that accepts $$\n\$$ on the left and $$\k\$$ on the right and yields $$\f_k(n)\$$.

Try it online!

### How?

x@’ßƒ⁸ʋ‘⁹? - Link: integer, n; integer, k
? - if...
⁹  - ...condition: chain's right argument, k -> k > 0?
ʋ    - ...then: last four links as a dyad - g(n, k):
’        -            decrement {k} -> k-1
@         -            with swapped arguments:
x          -              {k-1} repeated {n} times -> [k-1,k-1,...,k-1]
⁸     -            chain's left argument, n
ƒ      -            reduce {[n, k-1,k-1,...,k-1]} by:
ß       -              {current value} this Link {next value}
‘   - ...else: increment {n} -> n+1


# PARI/GP, 41 bytes

f(k,n,i=n)=if(k*i,f(k-1,f(k,n,i-1)),n+!k)


Attempt This Online!

A port of @Arnauld's JavaScript answer.

# PARI/GP, 49 bytes

f(k,n,i)=if(i,f(k,f(k,n,i-1)),k,f(k-1,n,n-1),n+1)


Attempt This Online!

# Python, 53 bytes

g=lambda k,n:k and[n:=g(k-1,n)for _ in[0]*n][-1]or-~n


Attempt This Online!

Does not support $$\ n = 0 \$$; supports $$\ k = 0 \$$.

# Ruby, 39 bytes

f=->k,n{k>0?n.times{n=f[k-1,n]}:n+=1;n}


Try it online!

# Brain-Flak, 92 bytes

({}<>)(()){{}((){[()](<({}[()])<>(({})<>){({}[()]<(({}))>)}{}{}>)}{}){({}<>{})(<>)}{}([])}<>


Try it online!

Supports $$\k=0\$$ and $$\n=0\$$. Large outputs take an unreasonable amount of time to compute, since no shortcuts are taken for $$\f_1\$$ or $$\f_2\$$.

# C (gcc), 5146 43 bytes

f(k,n,i){for(i=n;k*i--;)n=f(k-1,n);k=n+!k;}


Try it online!

5 bytes shaved off thanks to the n+!k trick I saw others do, and 3 more thanks to c-- :)