On the Powers of the Collatz Function
摘要
For all natural numbers a, b and \(d > 0\) , we consider the function \(f_{a,b,d}\) which associates n/d with any integer n when it is a multiple of d, and \(an + b\) otherwise; in particular \(f_{3,1,2}\) is the Collatz function. To realize these functions by transducers (automata labelled by pairs of words), the coding in reverse base 2 is generally used. For the Collatz function, it gives a simple 5-states transducer but it is not suitable for the composition and so far, no one has been able to specify, for all integers p, a generic transducer computing its composition p times. Coding in direct base ad with \(b < a\) , we realize the functions \(f_{a,b,d}\) by synchronous sequential transducers. This particular form makes explicit the composition of such a transducer p times to compute \(f^p_{a,b,d}\) in terms of p and a, b, d. We even give an explicit construction of an infinite transducer realizing the closure under composition of \(f_{a,b,d}\) .