Evaluate the nth hyperoperation

Question

I do realise that this is a bit math-y, but - here goes.

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations) that starts with the unary operation of successor, then continues with the binary operations of addition, multiplication and exponentiation, after which the sequence proceeds with further binary operations extending beyond exponentiation, using right- associativity.

Your goal is to write a program that takes three integers x, y and n as input and outputs the result of the nth hyperoperation on x and y.

E.g.

1 1 1 outputs 2

2 4 4 outputs 65536

3 3 4 outputs 7625597484987

• The program must be written in the shortest bit of code.
• You may take input either from STDIN or from a file.
• Library functions not allowed.
• Input constraints: n will be ≥ 1.

http://en.wikipedia.org/wiki/Tetration has a good explanation in case you can't wrap your head around this.

Answer 1

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: Takes evaluated input (space-separated numbers evaluates to a numerical array) and apply function to it.

1=3⌷⍵:: If n equals 1...
2⌷+\⍵: Return sum of first 2 elements (x+y)...
⋄0=2⌷⍵:: Else if y equals 0...
(⍵[3]⌊3)⌷⍵[1],0,1: Create numerical array [x,0,1] and return index min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: Else return ∇(x,∇(x,y-1,n),n-1). (∇ is self-reference)

---

I have got a "hyper-raiser" operator, which takes a function and return next hyperoperation

{⍺⍺/⊃⍴/⌽⍵}

For example, +{⍺⍺/⊃⍴/⌽⍵} would be the multiplication function and +{⍺⍺/⊃⍴/⌽⍵}5 3 outputs 15.

But can't get it to recurse. Maybe someone else can do it.

Answer 2

Ruby, slow, 86 84 83 characters

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Ruby, fast, 96 94 93 characters

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

The first version is way too slow with the last test case, so I added a version that uses multiplication as the base case instead of addition. The first version takes ages to calculate 3 3 4; the second one is instanteneous (in the native IRB console; the web version is a bit slower).

Several beauties of Ruby show up here:

Almost every statement is an expression in ruby. Thus, you can stuff semicolons inside the ternary operator, provided you've got enough parentheses lying around. Coffeescript borrowed that one. It also borrowed Ruby's "no parens needed" call syntax.

Implicit returns: this is a cool feature, and follows from the previous. Indeed, starting the last line of a function with return is considered lame, even when not golfing.

Numbers are objects in ruby (even null is an object). In ruby, integers have the method times, which executes the block passed to it several times. This is just one of Ruby's many iterator methods. Here, the upto method lets us save two more characters over what times lets us.

unary * is the splat operator here. It turns an array into an argument list. Just like Javascript's Function#apply, but it's shorter and better.

unary & turns a procedure into a block. While :to_i is a symbol, it converts into a procedure pretty well. Namely, it turns into a procedure that calls to_i on its argument and returns the result. More information on Stack Overflow.

It would be possible to get it even faster by using n=3 as the base case, but I'm afraid it is not needed. It would only cost 11 characters, though, thanks to another beauty of ruby: the exponentiation operator **. Python has this operator, but it's not the first one (as @aka.nice noted - thanks -, Fortran already had this operator).

online ruby interpreter available here: http://repl.it/Ikj/1

Answer 3

APL (Dyalog Unicode), 31 23 22 bytes (SBCS)

Saved 6 bytes thanks to Bubbler

{×a←⍺-1:a∇⍣⍵×⍺-2⋄⍵+⍺⍺}

Try it online!

Can be used as n (x f) y.

{
 ×a←⍺-1:     ⍝ Check if n is greater than 1
  a←⍺-1      ⍝ Assign n - 1 to a variable a to reuse later
 ×           ⍝ Sign of a (0 if addition, 1 otherwise)

  a∇⍣⍵×⍺-2  ⍝ Apply the (n-1)th hyperoperation y times to x
       ×⍺-2  ⍝ Sign of n-2 (the identity for the nth hyperoperation
    ⍣        ⍝ Power operator, apply
   ∇         ⍝ the derived function (f x)
     ⍵       ⍝ y times
       ×⍺-2  ⍝ to the identity
  a          ⍝ With n-1 as the new n

⋄
⍵ + ⍺⍺     ⍝ n is 1 (addition)
}
```

Answer 4

Jelly, 15 bytes

ṛ+⁵ðx’ß@ƒ>2¥ðỊ?

Try it online!

Writing a 3-argument program in Jelly is hard, though at least we need to use one of them only once in this problem. So this program takes three arguments in the order of n y x and recurses as a dyadic function. Roughly a hybrid of this Ackermann solution with user's APL answer.

How it works

ṛ+⁵ðx’ß@ƒ>2¥ðỊ?    Main program as a dyadic link.
                   Left = n, Right = y, 3rd arg (⁵) = x
A..ðB.......ðC?    If C then A else B
             Ị     If n <= 1
ṛ+⁵                Then y + x
    x’ß@ƒ>2¥       Else...
    x’             y copies of n-1
      ß@ƒ>2        Reduce with the program itself flipped, with
                   the default value being n>2 (1 or 0)

Answer 5

Python, 83

(Based on flornquake's answer)

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Very slow for large results.

For 2, 4, 4 the output is 65536.

Answer 6

Python, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Input: 3, 3, 4
Output: 7625597484987

Shortened using a couple of @WolframH's ideas.

Answer 7

Smalltalk Squeak 4.x flavour many bytes!

I could implement one of the recursive form in Integer in 71 char

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

Then reading from a file or FileStream stdin will cost me an arm... Squeak was obviously not designed as a scripting language. So I will spend many bytes to create my own general purpose utilities unrelated to the problem:

Implement this 21 char method in Stream (to skip seaparators)

s self skipSeparators

Implement this 20 char method in Behavior (to read an instance from a Stream)

<s^self readFrom:s s

Then 28 chars in String (to create a file handle)

f^FileDirectory default/self

Then 59 chars in FileDirectory (to create a readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Then 33 chars in BlockClosure (to evaluate it n times)

*n^(1to:n)collect:[:i|self value]

Then 63 chars in Array (evaluate the argument with receiver and arguments taken from the Array)

`s^self first perform:s asSymbol withArguments:self allButFirst

then solve the problem by evaluating this 31 char snippet anywhere to read from file named x

|s|s:='x'f r.[0class<s]*3`#f:n:

Even without counting the utilities, that's 71+31=102 chars already...

Now, since I'm sure to lose the codeGolf, I have a funnier implementation in Integer:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

This method will define (compile) a binary messages made of n + if it does not exist (is not understood by the receiver of the message m), and will restart execution at the beginning of sender context. I inserted additionnal carriage return and spaces for readability.

Note that (m selector size-2min:1)hex last is a shorted form of (m selector size>2)asBit printString.

If it was not to demonstrate Smalltalk evil superpowers, the last statement could be replaced by shorter and simpler

^m sendTo:self

Now implement 28 chars utility in Character (to repeat it n times in a String)

*n^String new:n withAll:self

Then evaluate this 43 chars expression:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

We can accelerate with 10 more chars by implementing in Integer:

++y^self*y

and in this case we also have shorter code because we can replace ^',(m selector size-2min:1)hex lastwith ^1'

For such a high price, the code work with second integer=0 :)

Answer 8

Golfscript, slow, 39 characters

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(live link)

This is the standard recursive algorithm with a base case of n=1 (addition) (i.e. slow). The same I've used in my Ruby solution

Here's a version with my annotations (mostly stack-keeping). It doesn't include one optimisation I've added later:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~ is the eval operator. In case of strings, it treats the string as a GolfScript program. Luckily, a space-separated list of integers is a valid GolfScript program that pushes those integers on the stack. Compared to this, my previous version of the input routine (" "/{~}/, split by space and eval each) is pretty lame. In case of functions, it calls the function. When preceded by . (clone), it calls the function with itself as the first argument.

Golfscript doesn't seem to be exactly well suited for making recursive algorithms. If you want a recursive algorithm that isn't tail-call optimisable, you need to create and destroy stack frames to preserve your variables. In most languages, this is done automatically. In golfscript, you have to actually clone the variables (actually, stack entries), and destroy the stack entries you no longer need. Golfscript has no concept of stack frames. Have I said GolfScript is a stack-based language?

The first requirement is understandable. You have to specify the arguments somehow. It's only nice if they keep their original positions as well. The second requirement is unfortunate, especially since the return value is on the top of the stack, and golfscript lacks the ability to delete just any stack element. You can rotate the stack and discard the new top element, but that quickly builds up. \; is fine. \;\;\;\;\; isn't. You can do \; in a loop ({\;}9*; cost: 6 chars to discard up to 9 elements, or 7 chars to discard up to 99 elements), but we can do better:

Golfscript has first-class arrays. It also has the array literal syntax [1 2 3 4]. What's unexpected is that [ and ] are not actually a part of the syntax. They are merely two operators: [ marks the current position on the stack, and ] collects every element until it finds the start-of-array mark or runs out of stack, and discards the mark. You can even tear these two apart and see what happens. Well, quite an interesting thing:

Did I say golfscript has no concept of stack frames? I lied. This is a stack frame: [. You can discard it all at once: ];. But what if we want to keep the return value? You could close the stack frame on function entry (then we have a slightly mangled version of pass-by-array - not an interesting concept), or we can close the stack frame and take its last element instead of discarding it completely: ]-1= or we can uncons the last element instead, and then discard the frame: ])\;. They're the same length, but the latter is slightly cooler, so I'm using it.

So, instead of 6 or 7 characters to do a clean-up, we can do with 5. I still feel this could be golfed more, but hey, we've saved a character.

Answer 9

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Note: it requires obscene amounts of stack (and time) for non-tiny arguments.

Answer 10

R, 70 bytes

h=function(x,y,n)`if`(n<2,x+y,{z=n>2;while(y){z=h(x,z,n-1);y=y-1};+z})

Try it online!

As other answers have noted, recursing back to the n=1 hyperoperation of addition is rather slow by the time that n>3 and the hyperoperation is tetration or worse. TIO link includes recursive version starting at n=2 (multiplication) to check that the approach is sound and works for the last test-case...

---

R, 78 74 bytes

(for all n, including n=0)

h=function(x,y=x,n)`if`(n<2,x^n+y,{z=n>2;while(y){z=h(x,z,n-1);y=y-1};+z})

Try it online!

This was one of those frustrating problems where I couldn't resist going-ahead and trying to write the shortest general solution, even if n=0 wasn't required by the question.
The behaviour of n=0 (increment) and n=1 (addition) is different to all subsequent hyperoperations, since y=1 is not an identity function for these two cases. I've worked-around this by stopping recursion when n<2, and returning x^n+y, which manages to satisfy both the n=1 and n=0 cases.
For added niceness (at the cost of another +2 bytes), we can specify a default value for y of x, which means that it needn't be provided as an argument at all for n=0, since this is can be considered a unary operation on y.
So: +4 bytes wasted, but I'm happier now.

Answer 11

Haskell, 45 bytes

1?x=(x+)
n?x=(!!)$iterate((n-1)?x)$signum$n-2

Try it online!

Call it with (n?a)b.

Haskell, 51 bytes

(1?a)b=a+b
(2?_)0=0
(_?_)0=1
(n?a)b=(n-1)?a$n?a$b-1

Try it online!

Copied straight from the hyperoperation formula on Wikipedia. Call it with (n?a)b.

Answer 12

AXIOM Computer Algebra System, bytes 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

test:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

This would eliminate some recursion...Possible I swap in x and y in some return... are there other test values?

Answer 13

APL(NARS), chars 61, bytes 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

test:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987

Answer 14

Scala, 90 bytes

Port of @John Dvorak's Ruby answer in Scala.

---

Golfed version. Try it online!

(x,y,n)=>if(n>1){if(n>2){var c=x;for(i<-2 to y.intValue)c=f(x,c,n-1);c}else{x*y}}else{x+y}

Ungolfed version. Try it online!

object Main extends App {

  def f(x: BigInt, y: BigInt, n: BigInt): BigInt = {
    if (n > 1) {
      if (n > 2) {
        var c = x
        for (i <- 2 to y.intValue())
          c = f(x, c, n - 1)
        c
      } else {
        x * y
      }
    } else {
      x + y
    }
  }

  println(f(1, 1, 1))
  println(f(2, 4, 4))
  println(f(3, 3, 4))

}

Answer 15

C (gcc), 90 bytes

-2 bytes thanks to @ceilingcat!

_;h(a,b,n){int k=_++||!scanf("%d%d%d",&a,&b,&n),j=a;for(--n;n&&--b;)a=h(a,j,n);_*=k;a+=b;}

Try it online!

Ungolfed and explained:

_;
h(a,b,n)
{
    int k = _++ || !scanf("%d %d %d", &a, &b, &n),
    j=a;
    
    for (--n; n && --b;)
        a=h(a,j,n);
    
    _*=k;
    a+=b;
}

The code applies the n^th hyperoperations to a and b, respectively. These inputs need not be provided by the caller, since they're immediately reinitialized anyways. _++ || !scanf("%d %d %d", &a, &b, &n) makes a, b and c be read from stdin if and only if _ is non-zero (that is, if the current function call is not a recursive one - if it's called by another function rather than itself). The expression returns 0 if any new characters were read and nonzero if they weren't, making k an indicator for whether the current function call is a recursive one or not.

Then, the for loop applies the n-1^th hyperoperation to a b times, using j to store the initial value of a and a to store the intermediate values. Finally, _*=k makes _ zero again if and only if the current call is not a recursive one, so that the next call will reread the values of a, b and c, and b is added to a. Usually, b would equal 0 after the for loop, but if n equaled 1, the for loop wouldn't be executed at all and the function returns a + b. Note that the value of a is returned after a+=b since assignments and returns are usually stored in the same register.