title: The Ackermann function

text:
# Question
Title: The Ackermann function
The Ackermann function is notable for being the one of the simplest examples of a total, computable function that isn't primitive recursive.

We will use the definition of \\$A(m,n)\\$ taking in two nonnegative integers where

$$\begin{align} A(0,n) & = n+1 \\ A(m,0) & = A(m-1,1) \\ A(m,n) & = A(m-1,A(m,n-1)) \end{align}$$

You may implement

* a named or anonymous function taking two integers as input, returning an integer, or
* a program taking two space- or newline-separated integers on STDIN, printing a result to STDOUT.

You may not use an Ackermann function or hyperexponentiation function from a library, if one exists, but you may use any other function from any other library. Regular exponentiation is allowed.

Your function must be able to find the value of \\$A(m,n)\\$ for \\$m \le 3\\$ and \\$n \le 10\\$ in less than a minute. It must at least *theoretically* terminate on any other inputs: given infinite stack space, a native Bigint type, and an arbitrarily long period of time, it would return the answer. *Edit:* If your language has a default recursion depth that is too restrictive, you may reconfigure that at no character cost.

The submission with the shortest number of characters wins.

Here are some values, to check your answer:

$$\begin{array}{c|cccccccccc} A & n = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline m=0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 \\ 3 & 5 & 13 & 29 & 61 & 125 & 253 & 509 & 1021 & 2045 & 4093 & 8189 \\ 4 & 13 & 65533 & \text{big} \end{array}$$

# Answer
# Pyth, 19

```
DaGHR?atG?aGtHH1GhH

```

Defines `a`, which works as the Ackermann function. Note that this requires a higher recursion depth than the official pyth compiler allowed up until today to compute `a 3 10`, so I increased the recursion depth. This is not a change to the language, just to the compiler.

### Test:

```
$ time pyth -c "DaGHR?atG?aGtHH1GhH           ;a 3 10"
8189

real    0m0.092s
user    0m0.088s
sys     0m0.000s

```

### Explanation:

```
DaGH                     def a(G,H):
    R                    return
    ?          G                (if G:
     atG                              (a(G-1,
        ?    H                               (if H:
         aGtH                                      a(G,H-1)
              1                               else:1)
                hH               else:H+1)

```

Essentially, it first conditions on the truth value of `G` whether to recurse or return H+1. If it is recursing, the first argument is always G-1, and it conditions on the truth value of `H` whether to use `a(G,H-1)` as the second argument, or to use `1` as the second argument.
> 7 votes

# Answer
# Haskell, 35

```
0%n=1+n
m%n=iterate((m-1)%)1!!(n+1)

```

this defines the operator function `%`.

this works by noticing that `m%n` (where `a` is the ackerman function) for nonzero `m` is `(m-1)%` applied `n+1` times to `1`. for example, `3%2` is defined as `2%(3%1)` which is `2%(2%(3%0))`, and this is `2%(2%(2%1))`
> 26 votes

# Answer
# Binary lambda calculus, 54 bits = 6.75 bytes

Hexdump:

```
00000000: 1607 2d88 072f 68                        ..-../h

```

Binary:

```
000101100000011100101101100010000000011100101111011010

```

This is λ*m*. *m**g*. λ*n*. *g* (*n* *g* 1)) (λ*n*. λ*f*. λ*x*. *f* (*n* *f* *x*)), where all numbers are represented as Church numerals.
> 16 votes

# Answer
## GolfScript (30)

```
{1$1>{1\){1$(\A}*\;}{+)}if}:A;

```

Online demo

Without the `1>` (which special-cases `A(1, n)`) it takes 9 minutes to compute `A(3, 10)` on the computer I've tested it on. With that special case it's fast enough that the online demo takes less than 10 seconds.

Note that this *isn't* a naïve translation of the definition. The recursion depth is bounded by `m`.

### Dissection

```
{             # Function boilerplate
  1$          # Get a copy of m: stack holds m n m
  1>{         # (Optimisation): if m is greater than 1
    1         #   Take this as the value of A(m, -1)
    \){       #   Repeat n+1 times:
              #     Stack: m A(m, i-1)
      1$(\    #     Stack: m m-1 A(m, i-1)
      A       #     Stack: m A(m, i)
    }*
    \;        #   Lose that unwanted copy of m
  }{          # Else
    +)        #   A(m in {0, 1}, n) = m + n + 1
  }if
}:A;          # Function boilerplate

```
> 12 votes

# Answer
# J - 26 char

```
($:^:(<:@[`]`1:)^:(0<[)>:)

```

There is an alternate, more functional definition of Ackermann:

```
Ack 0 n = n+1
Ack m n = Iter (Ack (m-1)) n
Iter f 0 = f 1
Iter f n = f (Iter f (n-1))

```

It so happens that `Iter` is very easy to write in J, because J has a way of passing in the `m-1` to `Ack` and also to define the initial value of `Iter` to be 1. Explained by explosion:

```
(                      >:)  NB. increment n
                ^:(0<[)     NB. if m=0, do nothing to n+1; else:
   ^:                       NB. iterate...
($:                      )  NB.   self ($: is recursion)
     (<:@[     )            NB.   with left arg m-1
          `]                NB.   n+1 times
            `1:             NB.   starting on 1

```

This relies on what J calls the gerund form of `^:`—basically a way to have more control over all the bounds in a tacit (point-free) fashion.

At the REPL:

```
   3 ($:^:(<:@[`]`1:)^:(0<[)>:) 3
61
   ack =: ($:^:(<:@[`]`1:)^:(0<[)>:)
   (i.4) ack"0 table (i.11)
+-----+------------------------------------------+
|ack"0|0  1  2  3   4   5   6    7    8    9   10|
+-----+------------------------------------------+
|0    |1  2  3  4   5   6   7    8    9   10   11|
|1    |2  3  4  5   6   7   8    9   10   11   12|
|2    |3  5  7  9  11  13  15   17   19   21   23|
|3    |5 13 29 61 125 253 509 1021 2045 4093 8189|
+-----+------------------------------------------+
   6!:2 '3 ($:^:(<:@[`]`1:)^:(0<[)>:) 10'  NB. snugly fits in a minute
58.5831

```

We need to define `ack` by name to be able to put it in a table, because `$:` is a horrible, ugly beast and lashes out at anyone who attempts to understand it. It is self-reference, where self is defined as the largest verb phrase containing it. `table` is an adverb and so would love to become part of the verb phrase if you give it the chance, so you have to trap `$:` in a named definition to use it.

---

### Edit: 24 char?

Years later, I found a solution which is two characters shorter.

```
(0&<~(<:@#~$:/@,1:^:)>:)

```

It's a lot slower, though: `3 ack 8` takes over a minute on my machine. This is because (1) I use a fold `/` instead of iteration, so J probably has to remember more things than usual, and (2) while `0&<~` performs the same calculation as `(0<[)`, it actually gets executed `n+1` times *before taking the recursive step* when invoking `m ack n``0&<` happens to be idempotent, so it doesn't ruin the calculation, but `n` gets big fast and `ack` is highly recursive.

I am doubtful that a more powerful machine could push the new code under a minute, because this is a computer where the old code can find `3 ack 10` in less than 15 seconds.
> 7 votes

# Answer
## JavaScript, ES6, ~~41~~ 34 bytes

```
f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

```

Run this in a latest Firefox Console and it will create a function called `f` which you can call with different values of `m` and `n` like

```
f(3,2) // returns 29

```

OR

try the code below in a latest Firefox

```
f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

B.onclick=_=>alert(f(+M.value, +N.value))
```

```
#M,#N{max-width:15px;border: 1px solid;border-width:0 0 1px 0}
```

```
<div>f(<input id=M />,<input id=N />)</div><br><button id=B>Evaluate</button>
```
> 6 votes

# Answer
# Python 2.7.8 - ~~80, 54, 48, 46~~ 45

```
A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

```

(Credits to xnor!)

More readable, but with 1 more character:

```
A=lambda m,n:n+(m<1or A(m-1,n<1or A(m,n-1))-n)

```

Not that I had to set `sys.setrecursionlimit(10000)` in order to get a result for `A(3,10)`. Further golfing using logical indexing did not work due to the dramatically growing recursion depth.
> 6 votes

# Answer
# C - 41 bytes

Nothing to it--the small limits mean that all the required values can be calculated in less than 1 second by naively following the function definition.

```
A(m,n){return!m?n+1:A(m-1,n?A(m,n-1):1);}

int main()
{
    int m,n;
    for(m = 0; m <= 3; m++)
    for(n = 0; n <= 10; n++)
    printf("%d %d %d\n", m,n,A(m,n));
    return 0;
}

```
> 5 votes

# Answer
# Javascript ES6 (34)

```
a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1

```

### Implementation:

```
a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1
```

```
td[colspan="2"] input{width: 100%;}
```

```
<table><tbody><tr><td>m=</td><td><input id="m" type="number" value="0" /></td></tr><tr><td>n=</td><td><input id="n" type="number" value="0" /></td></tr><tr><td colspan="2"><input type="button" value="Calculate!" onclick="document.getElementById('out').value=a(document.getElementById('m').value, document.getElementById('n').value)" /></td></tr><tr><td colspan="2"><input id="out" disabled="disabled" type="text" /></td></tr></tbody></table>
```
> 5 votes

# Answer
# Coq, 40

```
nat_rec _ S(fun _ b n=>nat_iter(S n)b 1)

```

This is a function of type `nat -> nat -> nat`. Since Coq only allows the construction of total functions, it also serves as a formal proof that the Ackermann recurrence is well-founded.

Demo:

```
Welcome to Coq 8.4pl6 (November 2015)

Coq < Compute nat_rec _ S(fun _ b n=>nat_iter(S n)b 1) 3 10.
     = 8189
     : nat

```

Note: Coq 8.5, released after this challenge, renamed `nat_iter` to `Nat.iter`.
> 5 votes

# Answer
# JavaScript (ES6) - 34

```
A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1

```

And a test:

```
> A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1;s=new Date().getTime();console.log(A(3,10),(new Date().getTime() - s)/1000)
8189 16.441

```
> 4 votes

# Answer
# Jelly, 13 bytes

```
+‘ð;x’ß@ƒ1ðỊ?

```

Try it online!

Again uses proud haskeller's approach: `A(m+1,n)` is `A(m,?)` applied `n+1` times to 1.

The base case should've been simply `A(0,n) = n+1`, but unfortunately it (the code at the bottom) times out badly, so I had to use `A(m,n) = m+n+1 if m <= 1` instead.

### How it works

```
+‘ð;x’ß@ƒ1ðỊ?    Dyadic link. Left = m, Right = n
AAðBBBBBBBðC?    If C, do A; otherwise, do B
           Ị     If m <= 1...
+‘               Return m+n+1
   ;x’ß@ƒ1       Otherwise do this:
   ;x            Concatenate m to n copies of m (which gives n+1 copies of m)
     ’           Decrement each number (n+1 copies of m-1)
        ƒ1       Reduce with seed 1...
      ß@         This function, args swapped (since new m is on the right side)

```

---

# Jelly, 12 bytes, times out on A(3,9)

```
;x’ß@ƒ1ð‘}ḷ?

```

Try it online!
> 4 votes

# Answer
## Mathematica, 46 bytes

```
0~a~n_:=n+1
m_~a~n_:=a[m-1,If[n<1,1,a[m,n-1]]]

```

Takes pretty much exactly a minute for `a[3,10]`. Note that Mathematica's default recursion limit is too small for `a[3,8]` and beyond (at least on my machine), but that can be fixed by configuring

```
$RecursionLimit = Infinity

```
> 3 votes

# Answer
## Haskell, ~~48~~ 44 chars (36 for the list)

While not as short as the other Haskell solution, this one is notable because it expresses the Ackermann function as an infinite list, which I think is kinda neat. The result is an infinite list (of infinite lists) such that at position *\[m,n\]* it holds the value *A(m,n)*.

The infinite list itself:

```
iterate(tail.(`iterate`1).(!!))[1..]

```

As a function (to comply with the specification):

```
i=iterate;m%n=i(tail.(`i`1).(!!))[1..]!!m!!n

```

---

The formulation was derived by observing that the general/common case for the Ackermann function is to use the value to the left as an index in the row above. The base case for this recursion (i.e. the leftmost column of a row, i.e. *A(m,0)*) is to use the second left-most value in the row above. The base case for *that* recursion is the *A(0,n) = n+1* case, i.e. the first row is `[1..]`.

Thus, we get

```
let a0 = [1..]
let a1 = tail $ iterate (a0 !!) 1  -- 'tail' because iterate starts by applying
let a2 = tail $ iterate (a1 !!) 1  -- the function 0 times
-- etc

```

Then we simply add another level of iteration based on that pattern, and do some pointless juggling.
> 3 votes

# Answer
# Julia, ~~34~~ ~~31~~ 28 bytes

```
m\n=m>0?~-m\(n<1||m\~-n):n+1

```

This is a named anonymous function. It is a straightforward implementation of the recursive definition, abusing Julia's ability to redefine operators.

Try it online!
> 3 votes

# Answer
# Python 3, ~~58~~ 49 bytes

```
a=lambda m,n:m and a(m-1,n and a(m,n-1)or 1)or-~n

```

Try it online!

I didn't see a Python 3 answer (there was a Python 2), so I decided to fix that and put my own answer in here. (-(43+21) thanks to caird, -9 thanks to HN)
> 3 votes

# Answer
# Racket 67

```
(define(a m n)(if(= m 0)(+ n 1)(a(- m 1)(if(= n 0)1(a m(- n 1))))))

```
> 2 votes

# Answer
## Javascript with lambdas, 34

```
A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1

```

A tipical answer, can't make anything shorter.
> 2 votes

# Answer
# Tiny Lisp, 70 (out of competition)

This runs out of competition, as the language is newer than the question, and it also doesn't succeed to run the `(A 3 10)` as required in the question, due to a stack overflow.

`(d A(q((m n)(i m(i n(A(s m 1)(A m(s n 1)))(A(s m 1)1))(s n(s 0 1))))))`

This defines a function `A` which calculates the Ackermann function. Formatted:

```
(d A
   (q( (m n)
       (i m
          (i n
             (A (s m 1)
                (A m
                   (s n 1)
                 )
              )
             (A (s m 1)
                1
              )
           )
          (s n
             (s 0 1)
           )
        )
    ) )
 )

```

We are using all builtin macros (`d` (define) and `q` (quote) and `i` (if)) and one builtin function (`s` – subtract) here.

`i` executes its true part when the condition is a number \> 0 (and otherwise the false part), so we don't have to do an explicit comparison here.

`s` is the only arithmetic operation available, we use it for the `n-1`/`m-1`, as well as as `(s n (s 0 1))` for `n+1`.

Tiny lisp is using tail recursion optimization, but this only helps for the outer `A` call in the result, not for the `A(m, n-1)` call which is used for the parameters.

With my tiny lisp implementation in Ceylon on the JVM, it works up to `(A 3 5) = 253`, but it seems to break down when trying to calculate `(A 2 125)` directly (which should give the same result). If calculating that after `(A 3 4) = 125`, the JVM seems to got to optimize the functions enough to inline some intermediate function calls in my interpreter, allowing more recursion depth. Strange.

The reference implementation gets up to `(A 3 5) = 253` and also `(A 2 163) = 329`, but doesn't succeed `(A 2 164)`, and therefore even less `(A 3 6) = (A 2 253)`.
> 2 votes

# Answer
# brainfuck, 90 bytes

```
>>>>+>,>,<<[>[>[-[->>>+<<<]<[->+>>+<<<]>-[-<+>]>+>>>>>]<[->+>>]]<[>>+[-<<<+>>>]<<-]<<<]>>.

```

Try it online!

Assumes an implementation with arbitrary sized cell size, with IO as numbers. -6 bytes if you don't mind using negative cells.

Finishes in about 30 seconds for 3,8 in the linked interpreter, provided you tick the correct settings. Type inputted numbers prepended with `\`s, e.g. `3,9` is `\3\9`.
> 2 votes

# Answer
# Ral, ~~81~~ 61 bytes

```
,,/:11+-111:++:+:++:+:+?/0=:1/-/1/10*-0*1:+?+0=11:+?1++/1:+?.

```

Try it online!

**Commented**

```
Code                     Stack after        Description
,,                       0, m, n              Input m and n
                                            Loop:
/:11+-111:++:+:++:+:+?   r, n, m              Jump to SmallM if m < 2
/0=:1/-/1/10*-           r, m-1, 1, m, n-1    Perform [m, n] => [m-1, 1, m, n-1]
0*1:+?                   r, m-1, 1, m, n-1    Jump to Loop if n>0
+0=                      r, m-1, 1            Remove the last two elements
11:+?                    r, m-1, 1            Jump to Loop
                                            SmallM:
1++                      n+m+1, r             Perform [m, n] => [n+m+1]
/1:+?                    n+m+1                Jump to Loop if r>0
.                                             Print n+m+1

```

**Explanation**

Because there are no built in function calls (or recursion) in Ral, we need to simulate the stack frame. One way to do that is as follows:

1. Start with the stack \[m, n\]
2. Repeatedly apply the following rules, until a single element remains:
    * \[..., 0, n\] =\> \[..., n+1\]
    * \[..., m, 0\] =\> \[..., m-1, 1\]
    * \[..., m, n\] =\> \[..., m-1, m, n-1\]
3. Print the remaining element

However, since there is no way to know the current length of the stack in Ral, an additional flag is stored to test if the recursion should continue, resulting in the following rules:

* \[..., 0, 0, n\] =\> Print n+1 and exit
* \[..., 1, 0, n\] =\> \[..., n+1\]
* \[..., m, 0\] =\> \[..., m-1, 1\]
* \[..., m, n\] =\> \[..., m-1, 1, m, n-1\]
> 2 votes

# Answer
# K (ngn/k), 16 bytes

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

```

Try it online!

Same structure as my K answer for fast growing hierarchy, and happens to be the same length too. Can compute f(0..3)(0..10) in a couple seconds.

Again uses "`A(m+1,n)` is `A(m,?)` applied `n+1` times to 1."

```
{x/[;1]1+}/[;1+]    input: m, returns function that takes n
{        }/[;1+]    iterate m times on the function 1+ (increment):
       1+             create a function that increments n and then
 x/[;1]               run `x/[n+1;1]` == `(n+1)x/1`
                      == iterate function x n+1 times to 1

```
> 2 votes

# Answer
## APL, 31

```
{⍺=0:⍵+1⋄⍵=0:1∇⍨⍺-1⋄(⍺-1)∇⍺∇⍵-1}

```

Pretty straightforward. Uses the ⍨ character once to save one byte by reversing arguments. Takes m as the left argument and n as the right argument.

TryAPL.org
> 1 votes

# Answer
## R - ~~54~~ 52

I've used this as an excuse to try and get my head around R, so this is probably really badly done:)

```
a=function(m,n)"if"(m,a(m-1,"if"(n,a(m,n-1),1)),n+1)

```

Example run

```
> a(3,8)
[1] 2045

```

I get a stack overflow for anything beyond that

## T-SQL- 222

I thought I would try to get T-SQL to do it as well. Used a different method because recursion isn't that nice in SQL. Anything over 4,2 bombs it.

```
DECLARE @m INT=4,@n INT=1;WITH R AS(SELECT 2 C, 1 X UNION ALL   SELECT POWER(2,C),X+1FROM R)SELECT IIF(@m=0,@n+1,IIF(@m=1,@n+2,IIF(@m=2,2*@n+3,IIF(@m=3,POWER(2,@n+3)-3,IIF(@m=4,(SELECT TOP(1)C FROM R WHERE x= @n+3)-3,-1)))))

```
> 1 votes

# Answer
# Go, ~~260~~ ~~243~~ ~~240~~ 122 bytes

I didn't see that the question allowed anon funcs.

far from competitive but i'm learning this language and i wanted to test it out.

```
func (m,n int)int{r:=0
switch{case m==0&&n!=0:r=n+1
case m!=0&&n==0:r=a(m-1,1)
case m!=0&&n!=0:r=a(m-1,a(m,n-1))}
return r}
```

use it like `go run ack.go` and then supply two numbers, `m` and `n`. if m\>4 or n\>30, execution time may be in excess of half a minute.

for `m=3 n=11`:

```
$ time go run ack
16381
real    0m1.434s
user    0m1.432s
sys     0m0.004s

```

*edit*: saved total 17 bytes by switching to `switch` over `if/else` and dot-imports
> 1 votes

# Answer
## Ceylon, ~~88~~ ~~87~~ 85

```
alias I=>Integer;I a(I m,I n)=>m<1then n+1else(n<1then a(m-1,1)else a(m-1,a(m,n-1)));

```

This is a straightforward implementation. Formatted:

```
alias I => Integer;
I a(I m, I n) =>
        m < 1
        then n + 1
        else (n < 1
            then a(m - 1, 1)
            else a(m - 1, a(m, n - 1)));

```

The alias saves just one byte, without it (with writing `Integer` instead of `I`) we would get to 86 bytes. Another two bytes can be saved by replacing `== 0` by `< 1` twice.

With the default settings of `ceylon run`, it will work up to `A(3,12) = 32765` (and `A(4,0) = 13`), but `A(3,13)` (and therefore also `A(4,1)`) will throw a stack overflow error. (`A(3,12)` takes about 5 seconds, `A(3,11)` about 3 on my computer.)

Using `ceylon run-js` (i.e. running the result of compiling to JavaScript on node.js) is a lot slower (needs 1 min 19 s for `A(3,10)`), and breaks already for `A(3, 11)` with a »Maximum call stack size exceeded« (using default settings) after running for 1 min 30 s.

---

## Ceylon without recursion, 228

As a bonus, here is a non-recursive version (longer, of course, but immune to stack overflows – might get an out-of-memory error at some point).

```
import ceylon.collection{A=ArrayList}Integer a(Integer[2]r){value s=A{*r};value p=s.addAll;while(true){if(exists m=s.pop()){if(exists n=s.pop()){if(n<1){p([m+1]);}else if(m<1){p([n-1,1]);}else{p([n-1,n,m-1]);}}else{return m;}}}}

```

Formatted:

```
import ceylon.collection {
    A=ArrayList
}

Integer a(Integer[2] r) {
    value s = A { *r };
    value p = s.addAll;
    while (true) {
        if (exists m = s.pop()) {
            if (exists n = s.pop()) {
                if (n < 1) {
                    p([m + 1]);
                } else if (m < 1) {
                    p([n - 1, 1]);
                } else {
                    p([n - 1, n, m - 1]);
                }
            } else {
                // stack is empty
                return m;
            }
        }
    }
}

```

It is quite slower on my computer than the recursive version: `A(3,11)` takes 9.5 seconds, `A(3,12)` takes 34 seconds, `A(3,13)` takes 2:08 minutes, `A(3,14)` takes 8:25 minutes. (I originally had a version using lazy iterables instead of the tuples I now have, which was even much slower, with the same size).

A bit faster (21 seconds for `A(3,12)`) (but also one byte longer) is a version using `s.push` instead of `s.addAll`, but that needed to be called several times to add multiple numbers, as it takes just a single Integer each. Using a LinkedList instead of an ArrayList is a lot slower.
> 1 votes

# Answer
# UGL, ~~31~~ 30 bytes

```
iiRuldr%l%lR$d%rd:u%d:%+uRu:ro

```

Input separated by newlines.

Try it online!

(It has been implemented as a standard example in the interpreter.)
> 1 votes

# Answer
# Pyth, 15 bytes

```
M?GgtG?HgGtH1hH

```

Try it online! (sample usage of the function `g3T` added, which means `g(3,10)`)
> 1 votes

# Answer
# Tcl, 67 bytes

```
proc tcl::mathfunc::A m\ n {expr {$m?A($m-1,$n?A($m,$n-1):1):$n+1}}

```

Try it online!

---

~~Tcl, 77 bytes
```
proc A m\ n {expr {$m?[A [expr $m-1] [expr {$n?[A $m [expr $n-1]]:1}]]:$n+1}}

```
Try it online!<br>~~

In the online compiler it fails to run due to time-out, but in a local Tcl interpreter it runs well. I profiled of each root call to `A` function, to see how much time the calculation took for each pair `{m,n}` subject to be tested:

```
m=0, n=0, A=1, time=3.5e-5 seconds
m=0, n=1, A=2, time=2e-6 seconds
m=0, n=2, A=3, time=8e-6 seconds
m=0, n=3, A=4, time=1e-6 seconds
m=0, n=4, A=5, time=2e-6 seconds
m=0, n=5, A=6, time=1e-6 seconds
m=0, n=6, A=7, time=1e-6 seconds
m=0, n=7, A=8, time=1e-6 seconds
m=0, n=8, A=9, time=1e-6 seconds
m=0, n=9, A=10, time=0.0 seconds
m=0, n=10, A=11, time=1e-6 seconds
m=1, n=0, A=2, time=4e-6 seconds
m=1, n=1, A=3, time=6e-6 seconds
m=1, n=2, A=4, time=1e-5 seconds
m=1, n=3, A=5, time=1.2e-5 seconds
m=1, n=4, A=6, time=1.5e-5 seconds
m=1, n=5, A=7, time=2e-5 seconds
m=1, n=6, A=8, time=2e-5 seconds
m=1, n=7, A=9, time=2.6e-5 seconds
m=1, n=8, A=10, time=3e-5 seconds
m=1, n=9, A=11, time=3e-5 seconds
m=1, n=10, A=12, time=3.3e-5 seconds
m=2, n=0, A=3, time=8e-6 seconds
m=2, n=1, A=5, time=2.2e-5 seconds
m=2, n=2, A=7, time=3.9e-5 seconds
m=2, n=3, A=9, time=6.3e-5 seconds
m=2, n=4, A=11, time=9.1e-5 seconds
m=2, n=5, A=13, time=0.000124 seconds
m=2, n=6, A=15, time=0.000163 seconds
m=2, n=7, A=17, time=0.000213 seconds
m=2, n=8, A=19, time=0.000262 seconds
m=2, n=9, A=21, time=0.000316 seconds
m=2, n=10, A=23, time=0.000377 seconds
m=3, n=0, A=5, time=2.2e-5 seconds
m=3, n=1, A=13, time=0.000145 seconds
m=3, n=2, A=29, time=0.000745 seconds
m=3, n=3, A=61, time=0.003345 seconds
m=3, n=4, A=125, time=0.015048 seconds
m=3, n=5, A=253, time=0.059836 seconds
m=3, n=6, A=509, time=0.241431 seconds
m=3, n=7, A=1021, time=0.971836 seconds
m=3, n=8, A=2045, time=3.908884 seconds
m=3, n=9, A=4093, time=15.926341 seconds
m=3, n=10, A=8189, time=63.734713 seconds

```

It fails for the last pair `{m,n}={3,10}`, as it takes a very little more than one minute.

For higher values of `m`, it will be needed to increase the `recursionlimit` value.

---

I coult get it shorter to 65 bytes, but it will not meet the question's requirement "Your function must be able to find the value of A(m,n) for m ≤ 3 and n ≤ 10 in less than a minute.". Without the `{}` it will timeout on TIO and not do the demo of the last two entries.

# Tcl, 65 bytes

```
proc tcl::mathfunc::A m\ n {expr $m?A($m-1,$n?A($m,$n-1):1):$n+1}

```

Try it online!
> 1 votes

# Answer
# C (gcc), 36 bytes

```
A(m,n){m=m?A(m-1,n?A(m,n-1):1):n+1;}

```

Naive strategy with a little bit of optimization.

Try it online!
> 1 votes

# Answer
# Verilog (Icarus Verilog), 81 bytes

Based on the C answer. Verilog is not really intended for this kind of thing - Yosys crashes on this - but it's possible with Icarus.

```
function automatic[15:0]a;input[15:0]m,n;a=(m==0)?n+1:(n==0)?a(m-1,1):a(m-1,a(m,n-1));endfunction

```

Testbench:

```
module test();

function automatic[31:0]a;input[31:0]m,n;a=m?a(m-1,n?a(m,n-1):1):n+1;endfunction

initial begin
    $display("%d", a(3,10));
end

endmodule

```

Icarus is really not intended for this kind of constant abuse, though:

```
$ time ./a.out
 8189

real    0m55.422s
user    0m55.375s
sys     0m0.063s

```
> 1 votes

# Answer
# Haskell, 47 bytes

```
a 0 n=n+1
a m 0=a(m-1)1
a m n=a(m-1)(a m (n-1))

```

(Run using `ghci <filename>`) Almost directly copies from the problem definition (thank you pattern matching!).
> 1 votes

# Answer
# APL (Dyalog Unicode), 22 bytes

```
{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}

```

Try it online!

A port of proud haskeller's Haskell answer. Uses the fact that `Ack(m,n)` is equal to `Ack(m-1,?)` applied `n+1` times to `1`.

### How it works

```
{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}
{                    }  ⍝ ⍺←m, ⍵←n
 0=⍺:1+⍵⋄               ⍝ If m = 0, return 1 + n
          ∇      ⍨⍺-1   ⍝ Apply (m-1)∇ (∇ is recursive call)
           ⍣(⍵+1)       ⍝ n+1 times
         1              ⍝ to the initial value 1

```
> 1 votes

# Answer
# Io, 53 bytes

Yet another recursion solution.

```
a :=method(m,n,if(m<1,n+1,a(m-1,if(n<1,1,a(m,n-1)))))

```

Try it online!
> 1 votes

# Answer
# Jelly, 17 bytes

```
’çç’}¥ɗ’ç1Ɗṛ?‘}ḷ?

```

Try it online!

Requires a higher recursion limit for \\$A(3, 10)\\$ than the Jelly interpreter has, but finishes within 1 minute when I adjust the limit locally

Full program, due to some bugs with `ß`.

## How it works

```
’çç’}¥ɗ’ç1Ɗṛ?‘}ḷ? - Main link A(m, n). Takes m on the left and n on the right
                ? - If:
               ḷ  -   Condition: m is non-zero
                  -   Then:
            ?     -     If:
           ṛ      -       Condition: n in non-zero
      ɗ           -       Then:
’                 -         m-1
     ¥            -         Group the previous 2 links into a dyad f(m, n):
   ’}             -           n-1
  ç               -           A(m, n-1)
 ç                -         A(m-1, A(m, n-1)
          Ɗ       -       Else:
       ’          -         m-1
        ç1        -         A(m-1, 1)
              }   -   Else:
             ‘    -     n+1

```
> 1 votes

# Answer
# MMIX, 56 bytes (14 instructions)

```
5A000003 23000101 F8010000 27000001 5A010003 E3010001 F1FFFFFA
FE020004 23040001 27050101 FB03FFF6 F6040002 C9010003 F1FFFFF3

```

# Disassembly and explanation

```
ack PBNZ  $0,0F     // if(!m) {
    ADDU  $0,$1,1   //   m = n + 1
    POP   1,0       //   return m }
0H  SUBU  $0,$0,1   // m = m - 1
    PBNZ  $1,0F     // if(!n) {
    SETL  $1,1      //   n = 1
    JMP   ack       //   return ack(m,n) }
0H  GET   $2,rJ     // x = retaddr (to avoid trampling)
    ADDU  $4,$0,1   // m' = m + 1
    SUBU  $5,$1,1   // n' = n - 1
    PUSHJ $3,ack    // a = ack(m',n')
    PUT   rJ,$2     // retaddr = x
    SET   $1,$3     // n = a
    JMP   ack       // return ack(m,n)

```

There's hefty use here of tail recursion optimization, not that that'll help much (four words of stack are used here for every time we don't tail recurse, and the stack segment only holds \\$2^{58}\\$ words).
> 1 votes

# Answer
## J : 50

```
>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.

```

Returns in a fraction of a second for 0...3 vs 0 ... 10:

```
   A=:>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.
   timespacex 'res=:(i.4) A"0 table (i.11)'
0.0336829 3.54035e6
   res
┌───┬──────────────────────────────────────────┐
│A"0│0  1  2  3   4   5   6    7    8    9   10│
├───┼──────────────────────────────────────────┤
│0  │1  2  3  4   5   6   7    8    9   10   11│
│1  │2  3  4  5   6   7   8    9   10   11   12│
│2  │3  5  7  9  11  13  15   17   19   21   23│
│3  │5 13 29 61 125 253 509 1021 2045 4093 8189│
└───┴──────────────────────────────────────────┘

```

PS: the "0 serves to make A work on each single element, instead of gobbling up the left and right array, and generating length errors. But it's not needed for eg. 9 = 2 A 3 .
> 0 votes

# Answer
# Haskell: ~~81~~ 69 bytes

```
a::Int->Int->Int
a 0 n=n+1
a m 0=a (m-1) 1
a m n=a (m-1) a m (n-1)

```

`a 3 10` takes about 45 seconds.
> 0 votes

# Answer
# Ruby, 65

```
h,a={},->m,n{h[[m,n]]||=m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])}

```

## Explanation

This is a pretty straightforward translation of the algorithm given in the problem description.

* Input is taken as the arguments to a lambda. Two `Integer`s are expected.
* For speed and avoiding stack-overflow errors, answers are memoized in the `Hash` `h`. The `||=` operator is used to calculate a value that wasn't previously calculated.

`a[3,10]` is calculated in ~0.1 sec on my machine.

Here's an ungolfed version

```
h = {}
a = lambda do |m,n|
  h[[m,n]] ||= if m < 1
    n + 1
  elsif n < 1
    a[m-1,1]
  else
    a[m-1,a[m,n-1]]
  end
end

```
> 0 votes

# Answer
# Mouse-2002, ~~99~~ 83 bytes

```
$Y1%j:j.0=m:2%k:k.0=n:m.n.>[k.1+!|m.n.<[#Y,j.1-,1;|m.n.*0=[#Y,j.1-,#Y,j.,k.1+;;]]]@

```
> 0 votes

# Answer
# Java, 274 bytes

```
import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){if(b.equals(BigInteger.ZERO))return B.add(BigInteger.ONE);if(B.equals(BigInteger.ZERO))return A(b.subtract(BigInteger.ONE),BigInteger.ONE);return A(b.subtract(BigInteger.ONE),A(b,B.subtract(BigInteger.ONE)));}}

```

It calculates `A(3,10)` in a few seconds, and given infinite memory and stack space, it can calculate any combination of `b` and `B` as long as the result is below 2<sup>2147483647</sup>-1.
> 0 votes

# Answer
# Erlang (escript), 53 bytes

I tried to put the pattern matching in an if statement; turns out that makes the program longer...

```
a(0,N)->N+1;a(M,0)->a(M-1,1);a(M,N)->a(M-1,a(M,N-1)).

```

Try it online!
> 0 votes

# Answer
# Japt, 12 bytes

```
?ßUÉ!V´ªß:VÄ

```

Try it

```
?ßUÉ!V´ªß:VÄ     :Implicit input of integers U=m & V=n
?                :If U is not 0
 ß               :Recursive call with arguments
  UÉ             :  U-1 and
    !V´          :  Logical NOT of postfix decremented V
       ª         :  Logical OR with
        ß        :  Recursive call with arguments U and the now decremented V
         :VÄ     :Else return V+1

```
> 0 votes

# Answer
# Python 3.11, 96 bytes

```
def a(m,n):
    if m==0:return n+1
    elif n==0:return a(m-1,1)
    else:return a(m-1,a(m,n-1))

```

Ungolfed:

```
def a(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return a(m-1, 1)
    else:
        return a(m-1, a(m, n-1))

```
> 0 votes

# Answer
## Pascal, 110 B

To prevent death-by-boredom victims, the boilerplate recursive definition has been omitted. Using the boilerplate recursive definition as reference, you can *save 1 byte* in code length by doing the following:

* *Presume* the `m = 0` case the default case. Do not wrap it in an `if` statement, just calculate `A ≔ n + 1` (and possibly *overwrite* this value).
* This necessitates a different expression for the `m ≠ 0 ∧ n = 0` situation. The following code uses sets: `[n] − [m] = [0]`. It means, take the `integer` set consisting of the single element `n`, remove from it all elements found in the second set (`[m]`) and compare the resulting `set` value against the set `[0]`.
* The fallback can be phrased as `n × m > 0`. Recall that any product is zero as soon as at least one factor is zero. Phrasing the fallback like this is necessary, because there are no `else` clauses.

```
function A(m,n:integer):integer;begin
A:=n+1;if[n]-[m]=[0]then A:=A(m-1,1);if n*m>0 then A:=A(m-1,A(m,n-1))end

```

NB: The limits of `integer` are implementation-defined. For example, the GNU Pascal Compiler implementation will require the `‑‑setlimit=8189` parameter (or larger) to work correctly for \\$m \leq 3\\$, \\$n \leq 10\\$ test cases (beside the fact of having sufficient memory).
> 0 votes

---
Tags: code-golf, math, recursion
---


# Question
Title: Euler-Poincaré-Characteristic of Polyhedra
Given a *triangulation* of the surface of a polyhedron `p`, calculate its Euler-Poincaré-Characteristic `χ(p) = V-E+F`, where `V` is the number of vertices, `E` the number of edges and `F` the number of faces.

### Details

The vertices are enumerated as `1,2,...,V`. The triangulation is given as a list, where each entry is a list of the vertices of one face, given in clockwise or counterclockwise order.

Despite the name, the triangulation can also contain faces with more than 3 sides. The faces can assumed to be simply connected that means that the boundary of each faces can be drawn using one closed non-self-intersecting loop.

### Examples

**Tetrahedron**: This tetrahedron is convex and has `χ = 2`. A possible triangulation is

```
[[1,2,3], [1,3,4], [1,2,4], [2,3,4]]

```

**Cube**: This cube is convex and has `χ = 2`. A possible triangulation is

```
[[1,2,3,4], [1,4,8,5], [1,2,6,5], [2,3,7,6], [4,3,7,8],  [5,6,7,8]]

```

**Donut**: This donut/toroid shape has `χ = 0`. A possible triangulation is

```
[[1,2,5,4], [2,5,6,3], [1,3,6,4], [1,2,7,9], [2,3,8,7], [1,9,8,3], [4,9,8,6], [4,5,7,9], [5,7,8,6]]

```

**Double Donut**: This double-donut should have `χ = -2`. It is constructed by using two copies of the donut above and identifying the sides `[1,2,5,4]` of the first one with the side `[1,3,6,4]` of the second one.

```
[[2,5,6,3], [1,3,6,4], [1,2,7,9], [2,3,8,7], [1,9,8,3], [4,9,8,6], [4,5,7,9], [5,7,8,6], [1,10,11,4], [10,11,5,2], [1,10,12,14], [10,2,13,12], [1,14,13,2], [4,14,13,5], [4,11,12,14], [11,12,13,5]]

```

(Examples verified using this Haskell program.)

# Answer
# Haskell, 42 bytes

```
f m=maximum(id=<<m)-sum[0.5|_:_:l<-m,x<-l]

```

Try it online!

Combines the face and edge terms by subtracting 0.5 for every edge on a face beyond the first two.

Alt 42 bytes:

```
f m=maximum(id=<<m)-sum(0.5<$(drop 2=<<m))

```

Try it online!
> 6 votes

# Answer
# Haskell, ~~49~~ 46 bytes

```
u=length
f x|j<-x>>=id=maximum j+u x-u j`div`2

```

Try it online!

I get the number of vertices by concating the faces and finding the maximum. I find the number of faces by taking the length. I find the number of edges by summing the lengths of the faces and dividing by 2.
> 5 votes

# Answer
# Jelly, ~~18~~ ~~17~~ ~~11~~ ~~10~~ 9 bytes

*1 byte thanks to Erik the Outgolfer, and 1 more for telling me about `Ɗ`.*

```
FṀ_FLHƊ+L

```

Try it online!

Uses the actually intelligent not-hacked-together solution everybody else is probably using. (Credit to @totallyhuman for the only other solution I could understand enough to reimplement it.)

## Old solution (17 bytes)

```
ṙ€1FżFṢ€QL
;FQL_Ç

```

Try it online!

I hope I got everything right. Assumes that all faces contain at least 3 vertices and that no two faces have the same vertices; I'm not good enough in topology to come up with something that breaks the code.

Alternative 17 byte solution:

```
ṙ€1FżFṢ€,;F$QL$€I

```

### Explanation

```
;FQL_Ç    Main link. Argument: faces
            e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4]]
 F          Flatten the list. We now have a flat list of vertices.
            e.g. [1,2,3,1,3,4,1,2,4,2,3,4]
;           Append this to the original list.
            e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4],1,2,3,1,3,4,1,2,4,2,3,4]
  Q         Remove duplicates. We now have a list of faces and vertices.
            e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4],1,2,3,4]
   L        Get the length of this list. This is equal to V+F.
            e.g. 8
     Ç      Call the helper link on the faces to get E.
            e.g. 6
    _       Subtract the edges from the previous result to get V-E+F.
            e.g. 2

ṙ€1FżFṢ€QL    Helper link. Argument: faces
                e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4]]
ṙ€1             Rotate each face 1 position to the left.
                e.g. [[2,3,1],[3,4,1],[2,4,1],[3,4,2]]
   F            Flatten this result.
                e.g. [2,3,1,3,4,1,2,4,1,3,4,2]
     F          Flatten the original faces.
                e.g. [1,2,3,1,3,4,1,2,4,2,3,4]
    ż           Pair the items of the two flattened lists.
                e.g. [[2,1],[3,2],[1,3],[3,1],[4,3],[1,4],[2,1],[4,2],[1,4],[3,2],[4,3],[2,4]]
      Ṣ€        Order each edge.
                e.g. [[1,2],[2,3],[1,3],[1,3],[3,4],[1,4],[1,2],[2,4],[1,4],[2,3],[3,4],[2,4]]
        Q       Remove duplicates. We now have a list of edges.
                e.g. [[1,2],[2,3],[1,3],[3,4],[1,4],[2,4]]
         L      Get the length of the list to get E.
                e.g. 6

```
> 4 votes

# Answer
# APL (Dyalog Classic), 13 bytes

```
⌈/∘∊+≢-2÷⍨≢∘∊

```

Try it online!
> 4 votes

# Answer
# Python 2, 47 bytes

*-1 byte thanks to... user56656 (was Wheat Wizard originally).*

```
lambda l:len(l)-len(sum(l,[]))/2+max(sum(l,[]))

```

Try it online!
> 2 votes

# Answer
# Perl 5 `-a`, 29 bytes

This one is tailor made for the perl `-a` option which does almost all the work already

```
#!/usr/bin/perl -a
@V[@F]=$e+=@F}{say$#V+$.-$e/2

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 24 bytes

-3 bytes thanks to @att.

```
Max@#-Tr[Tr/@(1^#)/2-1]&

```

Try it online!
> 2 votes

# Answer
# Stax, 9 bytes

```
ÑF4╨Ω◙╜#├

```

Run and debug online

It's a straight-forward port of totallyhuman's python solution.

```
%   length of input (a)
x$Y flatten input and store in y
%h  half of flattened length (b)
-   subtract a - b (c)
y|M maximum value in y (d)
+   add c + d and output

```

Run this one
> 1 votes

# Answer
# Pari/GP, 28 bytes

```
x->#x+#Set(y=concat(x))-#y/2

```

Try it online!
> 1 votes

# Answer
# 05AB1E, ~~10~~ 9 bytes

```
ZsgI˜g;-+

```

Try it online!

**Explanation**

```
Z          # push number of vertices (V)
 sg        # push number of faces (F)
   I˜g;    # push number of edges (E)
       -   # subtract (F-E)
        +  # add (F-E+V)

```
> 1 votes

# Answer
# Pyth, 12 bytes

```
+-eSsQ/lsQ2l

```

**Try it here**
> 1 votes

# Answer
# Scala 3, 46 bytes

A port of @Wheat Wizard♦'s Haskell answer in Scala.

---

```
x=>{val j=x.flatten;j.max+x.length-j.length/2}

```

Attempt This Online!
> 1 votes

# Answer
# K (ngn/k), 22 bytes

```
{(#x)+(|/y)--2!#y}/,/\

```

Try it online!
> 1 votes

# Answer
## JavaScript (ES6), 60 bytes

```
a=>a.map(b=>(v=Math.max(v,...b),d+=b.length/2-1),d=v=0)&&v-d

```

Explanation: Loops over each face, keeping track of the largest vertex seen in `v` and tracking the number of edges minus the number of faces in `d` as per @xnor's answer.
> 0 votes

# Answer
# Ruby, 35 bytes

```
->a{a.size+a.flatten!.max-a.size/2}

```

Try it online!
> 0 votes

# Answer
# Proton, 35 bytes

```
l=>max(f=sum(l,[]))-len(f)/2+len(l)

```

Try it online!
> 0 votes

---
Tags: code-golf, math, geometry, polynomials, topology
---