Golf the fast growing hierarchy

Question

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 code-golf, the shortest solution in bytes wins

Answer 1

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.

Answer 2

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.

Answer 3

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]

Answer 4

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.

Answer 5

Wolfram Language (Mathematica), 30 bytes

Nest[fNest[f,#,#]&,#+1&,#]&

Try it online!

Input [k][n].

Answer 6

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.

Answer 7

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.

Answer 8

R, 50 bytes

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

Try it online!

Answer 9

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}")

Answer 10

Haskell, 31 bytes

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.

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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!

Answer 15

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

Answer 16

Ruby, 39 bytes

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

Try it online!

Answer 17

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

Answer 18

C (gcc), 51 46 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-- :)