ABSTRACT
Reccurence sequences appear almost everywhere in mathematics and computer science. Their study, is as well, plainly of intrinsic interest and has been a central part of number theory for many years. It is well known that for many recurrence sequences, such as the famous generalized 3 ⋅ x + 1 mapping [6], typical cases are easy to solve; so that computionally hard cases must be rare. This paper shows that the generalized 3x + 1 mapping can be summarized mainly by at least one parameter: how fast an input number reach a smaller one. Hard problems occur at critical values of such a parameter. The main steps of our method are: classification of numbers, construction of d–trees, searching and measuring the density of terminal nodes (numbers which reach a smaller number or a divergent class). We prove that a family of these recurrence sequences has terminal nodes’ density 1.
