Modular arithmetic of iterated powers Academic Article uri icon


  • To give examples of large combinatorial problems D. Knuth modified W. Ackermann's example of a recursive, but not primitive recursive, function to produce a class of nonassociative compositions. These arrow compositions, which we call krata, are defined on the positive integers by settingB↑1T=BTB↑D1=BB↑D+1(T+1)=B↑D(B↑D+1T).The function k(B, D, T) = B↑DT, which usually takes on large values, has interesting periodicity properties modulo every positive integer M. For fixed B, D, T ≥ 2 the sequences {B↑Dn}, {B↑nT} and {B↑nn} are eventually constant modulo M. Also {n↑DT}, {n↑Dn}, {n↑nT} and {n↑nn} are eventually periodic modulo M. An algorithm for calculating B↑DT modulo M is given. © 1983.

altmetric score

  • 2.5

author list (cited authors)

  • Blakley, G. R., & Borosh, I.

citation count

  • 2

publication date

  • January 1983