49
\$\begingroup\$

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}$$

\$\endgroup\$
8
  • 17
    \$\begingroup\$ How has this not been asked before?? \$\endgroup\$ Commented Oct 22, 2014 at 4:56
  • 15
    \$\begingroup\$ I think it'd be more fun to make this fastest-code \$\endgroup\$
    – Sp3000
    Commented Oct 22, 2014 at 7:43
  • 24
    \$\begingroup\$ Downvoting because there's no challenge here. The obvious answer -- just naively implementing the function exactly according to its definition -- is always going to be the best answer. So the question is just "Which language has the least number of characters in the obvious expression of Ackermann's function?" The true winner is the programming language, not the person who wrote the obvious program in it. \$\endgroup\$ Commented Oct 22, 2014 at 7:52
  • 1
    \$\begingroup\$ I agree that this challenge would be more interesting as a fastest code, currently this challenge seems to be mostly, how can I implement the ackerman function in as little characters without much consideration to speed. Instead of how can I make use of any patterns in the ackerman function to speed it up \$\endgroup\$
    – Tally
    Commented Oct 22, 2014 at 8:55
  • 9
    \$\begingroup\$ @DavidRicherby "The obvious answer [...] is always going to be the best answer." This is not true of all languages. I feel a little dirty for only having an example in my home language, but there are multiple ways to express Ackermann and in some languages you can get savings by using that fact. This was my intention for the challenge. \$\endgroup\$ Commented Oct 22, 2014 at 13:15

46 Answers 46

1
2
1
\$\begingroup\$

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

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!

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

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
\$\endgroup\$
2
  • \$\begingroup\$ I wonder if it's possible to adjust the limit via the python eval command \$\endgroup\$
    – Razetime
    Commented Apr 28, 2021 at 11:34
  • \$\begingroup\$ @Razetime Unfortunately, the problem on TIO is that Jelly segfaults if it recurses too much: Try it online!, whereas it doesn't when run locally \$\endgroup\$ Commented Apr 28, 2021 at 11:40
1
\$\begingroup\$

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

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

Pyth, 15 bytes

M?GgtG?HgGtH1hH

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

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

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

\$\endgroup\$
0
\$\begingroup\$

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 .

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

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ this is code golf, so you should try to have the shortest code possible. for example, remove unnecessary spaces and the explicit type \$\endgroup\$ Commented Oct 22, 2014 at 13:34
  • \$\begingroup\$ you're also missing the parens on the fourth line \$\endgroup\$ Commented Oct 22, 2014 at 13:36
0
\$\begingroup\$

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 Integers 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
\$\endgroup\$
2
  • \$\begingroup\$ a[3,10] throw a SystemStackError on my machine... \$\endgroup\$ Commented Jun 18, 2016 at 15:44
  • \$\begingroup\$ Golf nitpicks: You could change m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]]) to m<1?n+1:a[m-1,n<1?1:a[m,n-1]] \$\endgroup\$ Commented Nov 6, 2017 at 23:32
0
\$\begingroup\$

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+;;]]]@
\$\endgroup\$
0
\$\begingroup\$

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 22147483647-1.

\$\endgroup\$
1
  • \$\begingroup\$ I know it's been a while, but you can golf this to 185 bytes: import java.math.*;BigInteger A(BigInteger b,BigInteger B){return b.equals(B.ZERO)?B.add(B.ONE):B.equals(B.ZERO)?A(b.subtract(B.ONE),B.ONE):A(b.subtract(B.ONE),A(b,B.subtract(B.ONE)));} \$\endgroup\$ Commented Mar 21, 2018 at 10:28
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

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

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

\$\endgroup\$
0
\$\begingroup\$

Scala 3, 138 bytes

Use BigInteger. Attempt This Online!

type Q=BigInteger
def a(m:Q,n:Q):Q=if(m==ZERO)n.add(ONE)else if(n==ZERO)a(m.subtract(ONE),ONE)else a(m.subtract(ONE),a(m,n.subtract(ONE)))

use Int. Attempt This Online!

def a(m:Int,n:Int):Int=if(m==0)n+1 else if(n==0)a(m-1,1)else a(m-1,a(m,n-1))
\$\endgroup\$
1
2

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.