Ackerman function

Algebra Level 4

Ackermann(–Péter) function $A$ is a fairly well-known function that grows rapidly. It is defined as follows:

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

Define Ackerman function $\mathcal{A}(m,n)$ as follows:

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

Compute the last 3 digits of $\displaystyle\sum_{i=0}^{10} \sum_{j=0}^{10} \mathcal{A}(i,j)$ .

The answer is 894.

1 solution

Pebrudal Zanu
Jan 13, 2014

I don't know how to get direct the result, it's my solution:

Firstly, I make Accermann function in python:

def ackermann(m, n):

if m == 0:

    return n + 1

elif n == 0:

    return ackermann(m - 1, 1)

else:

    return ackermann(m - 1, ackermann(m-1, n - 1))

Then, I compiler(Using F5) this code, and I make this syntax

    total=0

     for m in range (0,11):

     for n in range (0,11):

         total+=f(m,n)

    print total

And then it's result:

1 3 6 10 15 21 28 36 45 55 66 68 70 73 77 82 88 95 103 112 122 133 135 138 141 145 150 156 163 171 180 190 201 204 207 211 215 220 226 233 241 250 260 271 274 278 282 287 292 298 305 313 322 332 343 347 352 357 362 368 374 381 389 398 408 419 424 430 436 442 448 455 462 470 479 489 500 506 513 520 527 534 541 549 557 566 576 587 594 602 610 618 626 634 642 651 660 670 681 689 698 707 716 725 734 743 752 762 772 783 792 802 812 822 832 842 852 862 872 883 $\fbox{894}$

Ackerman function

The answer is 894.

1 solution

0 pending reports