Ackermann function and its computation string

Computer Science Level 5

The Ackermann function $A \colon \N^2 \to \N$ is defined by the recursive relation $A(m, n) = \begin{cases} n+1 & (m = 0) \\ A(m-1, 1) & (m > 0, n = 0) \\ A(m-1, A(m, n-1)) & (m > 0, n > 0). \end{cases}$ As an example, compute: $A(1, 2) = A(0, A(1, 1)) = A(0, A(0, A(1, 0))) = A(0, A(0, A(0, 1))) = A(0, A(0, 2)) = A(0, 3) = 4.$ Consider the above computation string as a raw string of characters, i.e.

1	`A(1, 2) = A(0, A(1, 1)) = A(0, A(0, A(1, 0))) = A(0, A(0, A(0, 1))) = A(0, A(0, 2)) = A(0, 3) = 4`

One can see, that it has $97$ characters. How long is the raw computation string for $A(3, 5)$ ?

Details and assumptions

the computation string is generated by simply using the above recursive formula (there is no remembering of the values known form dynamic programing etc.),
the arguments are separated by two characters: comma and a single space,
there is exactly one space on both sides of the equal sign,
there is no extra character at the end of the string.

Test cases

Let $L(m, n)$ be the length of the raw computation string of $A(m, n)$ . Then:

$L(0, 0) = 11$ ,
$L(0, 10) = 13$ ,
$L(1, 1) = 53$ ,
$L(1, 2) = 97$ ,
$L(2, 2) = 649$ (cf. here for the full string),
$L(3, 3) = 399212$ (cf. here for the full string).

The answer is 27964559.

4 solutions

Piotr Idzik
May 7, 2020

Below you will find my python code. As a bonus exercise, you can try to adapt it in such a way, that it will solve a similar problem for the greatest common divisor calculated with Euclid's algorithm.

"""
solution of:
    https://brilliant.org/problems/ackermann-function-and-its-computation-string/
"""
class StrExpr:
    """
    StrExpr represents an expression in a single recursive step
    """
    def __init__(self, arg_list, fun_symbol, next_fun):
        self.arg_list = arg_list
        self.fun_symbol = fun_symbol
        self.next_fun = next_fun
    def next_step(self):
        """
        returns the next StrExps after performing the recursive step
        """
        for (cur_arg_pos, cur_arg) in enumerate(self.arg_list):
            if isinstance(cur_arg, StrExpr):
                self.arg_list[cur_arg_pos] = cur_arg.next_step()
                res = self
                break
        else:
            res = self.next_fun(self.arg_list)
        return res

    def __str__(self):
        arg_list_str = ', '.join([str(_) for _ in self.arg_list])
        return f"{self.fun_symbol}({arg_list_str})"

def ackermann_symbol():
    """
    returns a symbol used to denote the Ackermann function
    """
    return 'A'

def ackermann_next(arg_list):
    """
    performs a single recursive step
    in computation of the value of the Ackermann function for given input
    """
    assert len(arg_list) == 2
    for _ in arg_list:
        assert isinstance(_, int)
    m_val, n_val = arg_list
    assert m_val >= 0 and n_val >= 0
    if m_val == 0:
        res = n_val+1
    elif n_val == 0:
        res = StrExpr([m_val-1, 1], ackermann_symbol(), ackermann_next)
    else:
        res = StrExpr([m_val-1, StrExpr([m_val, n_val-1], ackermann_symbol(), ackermann_next)],
                      ackermann_symbol(), ackermann_next)
    return res


def get_comp_str(initial_expr):
    """
    returns the full computation string for given initial expression
    """
    cur_expr = initial_expr
    res_list = [str(cur_expr)]
    while isinstance(cur_expr, StrExpr):
        cur_expr = cur_expr.next_step()
        res_list.append(str(cur_expr))
    return ' = '.join(res_list), cur_expr

def get_ackerman_str_len(in_m, in_n):
    """
    returns the length of the full computation string
    for the Ackermann function for given input
    """
    res_str, res_val = get_comp_str(StrExpr([in_m, in_n], ackermann_symbol(), ackermann_next))
    if in_m <= 3:
        if in_m == 0:
            assert res_val == in_n+1
        elif in_m == 1:
            assert res_val == 2+(in_n+3)-3
        elif in_m == 2:
            assert res_val == 2*(in_n+3)-3
        else:
            assert res_val == 2**(in_n+3)-3
    return len(res_str)

assert get_ackerman_str_len(0, 0) == 11
assert get_ackerman_str_len(0, 10) == 13
assert get_ackerman_str_len(1, 1) == 53
assert get_ackerman_str_len(1, 2) == 97
assert get_ackerman_str_len(2, 2) == 649
assert get_ackerman_str_len(3, 3) == 399212

M_VAL = 3
N_VAL = 5
STR_LEN = get_ackerman_str_len(M_VAL, N_VAL)
print(f"Length of the computation string for {ackermann_symbol()}({M_VAL}, {N_VAL}): {STR_LEN}")

Veryyyyyyyyyyyyyyyyyyyyy confusinggggggggggggggggggg

Razing Thunder - 12 months ago

Sahil Goyat
May 11, 2020

def A(m,n):     
    m=int(m)
    n=int(n)
    if m==0:
        return str(n+1)
    elif m>0 and n==0:
        return 'A('+str(m-1)+', 1)'
    else:
        return 'A('+str(m-1)+', A('+str(m)+', '+str(n-1)+'))'
def eva(s):
    n=s.rfind('A')
    k=s.find(')',n)
    return s[:n]+eval(s[n:k+1])+s[k+1:]
cs=t='A(3, 5)'
while not(str(t).isnumeric()):   
    t=eva(t)
    cs+=' = '+t
print(len(cs))

@Piotr Idzik can you comment on the efficiency of my code i am not sure if it the most efficient and short at at same time

Sahil Goyat - 11 months, 2 weeks ago

I did a quick benchmark. Your code needs about 47.63 [s] to complete, my code requires 8.02 [s] and the code by @David Vreken needs incredible 0.17 [s].

Few remarks:

I like how memory efficient is the solution presented by mention[5001876:David Vreken] (he is not storing the entire computational string but just the currently considered piece),
I think, that the performance of the solution published by comes from the fact, that lists in python are implemented as dynamic array , therefore replace can be really fast (cf. line 18 in his code), I think you loose time in the line 13 of your code (+ is always slow for strings/arrays etc.).
it turns out, that the function isinstance in Python in painfully slow. I suspect, that if I would store an information if a given argument is atomic (in this case integer) or not (i.e. I would not need the function isinstance), my code would be comparably efficient as the one by mention[5001876:David Vreken]. Or maybe even a bit faster, because I do not need to find the active part of the current string (cf. lines 11-12 in your code and 8 in code of mention[5001876:David Vreken]) - it is like comparing searching a very long string with diving into a deep tree.

Concerning the compactness of the code: people doing code golf are incredible (take a look here for some crazy examples). I am almost sure that one can write a program solving this puzzle, which uses only "few" bytes. However, it is not always the case, that the shorted program is better. There is this saying, that the program is written once but read many times. (Slightly) Longer code can be easier to read, maintain, understand and reuse by the others. And for the computer, it does not really matter how long the code is.

Piotr Idzik - 11 months, 2 weeks ago

Why the function is instance is so slow ?

Sahil Goyat - 11 months, 2 weeks ago

Abir Hasan
Apr 12, 2021

Quite efficient and concise python code:

def A(m, n, s ="{}", l=0):
    print((s.format("A({}, {})".format(m, n))), end=" = ") # print compution string
    l += len(s.format("A({}, {})".format(m, n))) + 3 # add running length of computation string
    if m == 0:
        return n + 1, l
    if n == 0:
        return A(m - 1, 1, s, l)
    n2, l = A(m, n - 1, s.format("A({}, {{}})".format(m - 1)), l)
    return A(m - 1, n2, s, l)

n, l = A(3, 5)
print(n) # print Ackermann function output
print(l + len(str(n))) # print computation string

David Vreken
May 8, 2020

The Python program below computes $L(3, 5) = \boxed{27964559}$ .

# Ackermann function and its computation string
# Python

# Take in an Ackermann computational part, find the last
#   A(m, n) part, and replace it as defined by the given
#   recursive relation.
def A(s):
    lastA = s[s.rfind("A("):s.find(")", s.rfind("A(")) + 1]
    m = int(lastA[2:lastA.find(",")])
    n = int(lastA[lastA.find(",") + 2:-1])
    if m == 0:
        newlastA = str(n + 1)
    elif m > 0 and n == 0:
        newlastA = "A(" + str(m - 1) + ", 1)"
    elif m > 0 and n > 0:
        newlastA = "A(" + str(m - 1) + ", A(" + str(
            m) + ", " + str(n - 1) + "))"
    return s.replace(lastA, newlastA)

# Find the length of the computational string by keeping
#   a running total of each computational part using A(s).
def L(m, n):    
    s = "A(" + str(m) + ", " + str(n) + ")"
    total = len(s)
    while "A" in s:
        s = A(s)
        total += (len(" = ") + len(s))
    return total

# Display the results.
print(L(3, 5))

Ackermann function and its computation string

The answer is 27964559.

4 solutions

0 pending reports