MODULAR ARITHMETIC OF ITERATED POWERS
Academic Article

Overview

Identity

Additional Document Info

Other

View All

Overview

abstract

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 settingB1T=BTBD1=BBD+1(T+1)=BD(BD+1T).The function k(B, D, T) = BDT, which usually takes on large values, has interesting periodicity properties modulo every positive integer M. For fixed B, D, T 2 the sequences {BDn}, {BnT} and {Bnn} are eventually constant modulo M. Also {nDT}, {nDn}, {nnT} and {nnn} are eventually periodic modulo M. An algorithm for calculating BDT modulo M is given. 1983.