A131619 A general two modulo Ackermann recursion at 6 and 5.

1, 2, 2, 3, 3, 3, 0, 0, 4, 4, 3, 3, 2, 0, 5, 1, 1, 4, 4, 1, 0, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 0, 3, 3, 2, 1, 1, 1, 1, 3, 3, 0, 4, 3, 1, 1, 1, 1, 1, 1, 4, 2, 0, 4

Offset

1,2

Comments

This double modulo Ackermann function was inspired by the tiling problem given in "Elements of the Theory of Computation" which resembles an Ackermann recursion. The {a,b}->{5,6} was designed for the 10 X 10 output given to be active. Without the modulo this function is effectively limited to 4 X 4 in Mathematica by computation time.

References

S. Wolfram, A New Kind of Science. Champaign, IL: Wolfram Media, p. 906, 2002.

Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981, page 296 and 345.

Links

Table of n, a(n) for n=1..55.

Eric Weisstein's World of Mathematics, Ackermann function.

Formula

a(1, n) = n mod 6; a(m, 1) = a(m - 1, 2); a(m, n) = a(m - 1, a(m, n - 1) + 1) mod 5.

aout(n,m) = AntidiagonalTransform(a(n,m)).

Example

{1},
{2, 2},
{3, 3, 3},
{0, 0, 4, 4},
{3, 3, 2, 0, 5},
{1, 1, 4, 4, 1, 0},
{1, 1, 3, 1, 1, 2, 1},
{1, 1, 1, 1, 0, 3, 3, 2},
{1, 1, 1, 1, 3, 3, 0, 4, 3},
{1, 1, 1, 1, 1, 1, 4, 2, 0, 4}

Mathematica

f[1, n_] := Mod[n, 6]; f[m_, 1] := f[m - 1, 2]; f[m_, n_] := Mod[f[m - 1, f[m, n - 1] + 1], 5];
a0 = Table[f[a, b], {a, 1, 10}, {b, 1, 10}];
ListDensityPlot[%, ColorFunction -> (Hue[2# ] &)];
Dimensions[a0];
(* antidiagonal transform*)
c = Delete[Table[Reverse[Table[a0[[n, l - n]], {n, 1, l - 1}]], {l, 1, Dimensions[a0][[1]] + 1}], 1];
Flatten[c]

Crossrefs

Cf. A001695, A014221.

Sequence in context: A036012 A084401 A236465 * A048485 A127714 A283763

Adjacent sequences: A131616 A131617 A131618 * A131620 A131621 A131622

Keyword

nonn,tabl,uned

Author

Roger L. Bagula, Oct 02 2007

Status

approved