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.