14
\$\begingroup\$

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
\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – STerliakov
    Sep 4, 2023 at 19:49
  • 3
    \$\begingroup\$ @SUTerliakov We can, since we know f1(n)=2n. Also, the domain is previously specified to be positive integers \$k,n\$. \$\endgroup\$
    – att
    Sep 4, 2023 at 21:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – STerliakov
    Sep 4, 2023 at 21:12
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – bsoelch
    Sep 5, 2023 at 8:45
  • 1
    \$\begingroup\$ What about syntax errors due to deeply nested parenthesis? \$\endgroup\$ Sep 5, 2023 at 12:27

18 Answers 18

5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jonah
    Sep 4, 2023 at 4:50
  • \$\begingroup\$ I've added my recursive reduce solution. There must be a shorter approach though. \$\endgroup\$
    – Jonah
    Sep 4, 2023 at 6:03
5
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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]
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 38 bytes

F²⊞υNW⊖Lυ«≔⊟υθ≔⊟υη¿η«Fθ⊞υ⊖η⊞υθ»⊞υ⊕θ»Iυ

Try it online! Link is to verbose version of code. Explanation:

F²⊞υN

Push k and n to the predefined empty list.

W⊖Lυ«

Repeat until the list only contains one value.

≔⊟υθ≔⊟υη

Extract k and n for the deepest recursion depth.

¿η«

If k is non-zero, then...

Fθ⊞υ⊖η

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

»Iυ

Output the final value.

52 bytes for a version optimised for k<3:

F²⊞υNW⊖Lυ«≔⊟υθ≔⊟υη≡η⁰⊞υ⊕θ¹⊞υ⊗θ²⊞υ×X²θθ«Fθ⊞υ⊖η⊞υθ»»Iυ

Try it online! Link is to verbose version of code.

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

Input [k][n].

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Cool idea, but unfortunately following the definition more directly is shorter. \$\endgroup\$
    – Bubbler
    Sep 4, 2023 at 6:20
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jonah
    Sep 4, 2023 at 6:34
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Really clever on the J one. \$\endgroup\$
    – Jonah
    Sep 4, 2023 at 7:01
4
\$\begingroup\$

R, 50 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ The lambda version can be 68 bytes by replacing if not k else with if k==0else \$\endgroup\$
    – noodle man
    Sep 3, 2023 at 14:12
  • \$\begingroup\$ @noodleman Or even k<1. \$\endgroup\$
    – Neil
    Sep 3, 2023 at 14:16
  • \$\begingroup\$ 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? \$\endgroup\$
    – Jo King
    Sep 4, 2023 at 5:11
  • \$\begingroup\$ @JoKing ~-n is n-1, not n+1. ~-1 == 0, ~-2 == 1. \$\endgroup\$
    – STerliakov
    Sep 4, 2023 at 20:00
  • 1
    \$\begingroup\$ You can post that on your own, I'm opting to support n=0 because my current answer supports it \$\endgroup\$ Sep 5, 2023 at 4:52
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ 39 bytes \$\endgroup\$
    – att
    Sep 3, 2023 at 21:25
  • \$\begingroup\$ @att Nice! (My initial attempt was close to that, but I messed it up and changed my mind.) \$\endgroup\$
    – Arnauld
    Sep 3, 2023 at 21:32
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Ruby, 39 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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-- :)

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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