ackerman function

ackerman.txt

ack(x, y) =
    (x == 0) ? (y + 1) :
    (y == 0) ? ack(x - 1, 1) :
    ack(x - 1, ack(x, y - 1));
         X
      |  0   1   2   3   4   5   6   7   8   9
    --+--------------------------------------
Y   0 |  1   2   3
    1 |  2   3   5
    2 |  3   4   7
    3 |  4   5   9
    4 |  5   6   11
    5 |  6   7   13
    6 |  7   8   15
    7 |  8   9   17
    8 |  9   10  19

ack(0,N) = N+1
    0,0 => 1
    0,1 => 2
    0,2 => 3
    0,3 => 4
    0,4 => 5

ack(N,0) = ack(N-1, 1)
    1,0 => ack(0,1) => 2
    2,0 => ack(1,1) => _ => 3
    3,0 => ack(2,1) => _
    4,0 => ack(3,1) => _
    5,0 => ack(4,1) => _
    6,0 => ack(5,1) => _
    7,0 => ack(6,1) => _
    8,0 => ack(7,1) => _

ack(N,1) = ack(N-1, ack(N, 0)) = ack(N-1, ack(N-1, 1))
    1,1 => ack(0, ack(1,0) = ack(0,1) = 2) => ack(0,2) => 3
    2,1 => ack(1, ack(2,0) = ack(1,1) = 3) => ack(1,3) => _
    3,1 => ack(2, ack(3,0) = ack(2,1) = _) => ack(2,_) => _
    4,1 => ack(3, ack(4,0) = ack(3,1) = _) => ack(3,_) => _
    5,1 => ack(4, ack(5,0) = ack(4,1) = _) => ack(4,_) => _

ack(1,N) = ack(0, ack(1, N-1)) = ack(1, N-1) + 1 = N + 2
    1,0  = 2
    1,1  = 3
    1,2  = 4
    1,3  = 5
    1,N  = N + 2

ack(2,N) = ack(1, ack(2, N-1)) = ack(2,N-1) + 2 = 3 + N * 2
    2,0  = 3
    2,1  = 3 + 2 = 5
    2,2  = 5 + 2 = 7
    2,3  = 7 + 2 = 9
    2,N  = 3 + 2 * N

ack(3,N) = ack(2, ack(3,N-1)) = ack(3,N-1) * 2 + 3  = 5 + 8 * (2^N - 1)
                                                    = 2^(N+3) - 3
    3,0  = ack(2,1) = ack(1,3) = 5      (0 + 5)
    3,1  = 5 * 2 + 3           = 13     (8 + 5)
    3,2  = 13 * 2 + 3          = 29     (8*3 + 5)
    3,3  = 29 * 2 + 3          = 61     (8*7 + 5)
    3,4  = 61 * 2 + 3          = 125    (8*15 + 5)
    3,5  = 125 * 2 + 3         = 253    (8*31 + 5)

ack(4,N) = ack(3, ack(4,N-1)) = 5 + 8 * (2^(ack(4,N-1)) - 1)
    4,0  = ack(3,1)                          = 13
    4,1  = 5 + 8 * (2^13 - 1) = 5 + 8 * 8191 = 65533
    4,2  = 5 + 8 * (2^65533 - 1)            ~= 2^65536
    4,3  = 5 + 8 * (2^(...) - 1)            ~= 2^(2^65536 + 3)

ack(4,N) = ack(3, ack(4,N-1)) = 2^(ack(4,N-1) + 3) - 3
    4,0 = ack(3,1)                          = 13
    4,1 = 2^16 - 3                          = 65533
    4,2 = 2^(2^16 - 3) - 3                  = 2^65533 - 3
    4,3 = 2^(2^(2^16 - 3) - 3) - 3

ack(5,N)
    5,0 = ack(4,1)                          = 65533


ack(x, y) =
    (x == 0) ? (y + 1) :
    (y == 0) ? ack(x - 1, 1) :
    ack(x - 1, ack(x, y - 1));

         X
      |  0   1   2   3   4   5   6   7   8   9
    --+----------------------------------------
Y   0 |  1   2   3   5   13  65533
    1 |  2   3   5   13  65533
    2 |  3   4   7   29  2^65533 - 3
    3 |  4   5   9   61
    4 |  5   6   11  125
    5 |  6   7   13  253
    6 |  7   8   15  509
    7 |  8   9   17  1021
    8 |  9   10  19  2045

         ^   ^   ^   ^    ^
         N+1 N+2 |   |    +- fold( (^2) . (-3) , start=16 , count=N )
                 |   |
                 |   +- 2^(N+3) - 3
                 |
                 +- N*2 + 3