1
$\begingroup$

The Ackerman function is defined as follows:

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

Is it possible to get the last few digits of Ackermann function?


I refer to the method in this article: Is this the correct way to compute the last $n$ digits of Graham's number?

If the iterations are large enough, the last 10 digits will be fixed at 3432948733.

But in many cases the number of iterations of the function is not so large.

Is there a more suitable algorithm to deal with the case of Ackerman function?

$\endgroup$
0
$\begingroup$

The Ackermann function is known to have the form

$$A(m,n)=2\uparrow^{m-2}(n+3)-3$$

to which the problem boils down in largely the same manner to finding the eventual last digits of

$$2\uparrow^2k$$

for large $k$ in much the same manner as the provided link, though you will have to take care of the fact that $2$ and $10$ are not relatively prime. A direct computation shows that the last $n$ digits of this should remain constant for $k\ge n+2$.

When the arguments are sufficiently small, then a more direct computation can be used instead.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.