A sequence that grows faster than the ackermann function?

Question

Ackermann's function and all the up-arrow notation is based on exponentiating. We know for a fact that the factorial function grows faster than any power law so why not build an iterative sequence based on factorials? I am thinking of the simple function defined by $$ a(n)=a(n-1)! $$ and to start things off we need $a(1)=3$. The numbers generated are $3,6,24,720$ and the next one ($720!$) is roughly $10^{1746}$ and I can't even start to imagine what happens next!

Is it primitive recursive? Can it be coded up using for loops avoiding calls to itself? I think not but this is just a hunch. Computer scientists might have better chances of answering that than I.

Thanks in advance, I appreciate it.

Answer 1

So you mean the function $a(n)$ defined by $a(1)=3$ and $a(n) = a(n-1)!$.

This function is primitive recursive. Multiplication can be defined by a primitive recursive scheme. Based on this, the factorial function can be defined by a primitive recursive scheme. From here, you can use induction on $n$ to show that $a(n)$ is primitive recursive.

Answer 2

To answer the question concerning writing this in for loops, here's some python-like pseudocode to consider:

# Some integer to compute a(n).
n: int
# Start with 3,
solution = 3
# and then apply the factorial n-1 times.
for i in [1, 2, ..., n-1]:
    # To compute the factorial, start with 1,
    factorial = 1
    # and then multiply by everything from 1 to the current solution
    for j in [1, 2, 3, ..., solution]:
        factorial *= j
    # and save the results.
    solution = factorial
print(solution)