Abstract
We consider the map given by , where denotes the smallest integer greater than or equal to , and study the problem of finding, for each rational, the smallest number of iterations by that sends it into an integer. Given two natural numbers and , we prove that the set of numerators of the irreducible fractions that have denominator and whose orbits by reach an integer in exactly iterations is a disjoint union of congruence classes modulo . Moreover, we establish a finite procedure to determine them. We also describe an efficient algorithm to decide whether an orbit of a rational number bigger than one fails to hit an integer until a prescribed number of iterations have elapsed, and deduce that the probability that such an orbit enters is equal to 1.
Acknowledgements
This research is partially funded by the European Regional Development Fund through the programme COMPETE and by the Portuguese Government through the Fundação para a Ciência e a Tecnologia (FCT), under the projects PEst-C/MAT/UI0144/2011 [Centro de Matemática da Universidade do Porto (CMUP)] and PEst-C/MAT/UI0013/2011 [Centro de Matemática da Universidade do Minho (CMAT)].
The authors are grateful to the referee for valuable comments and suggestions that helped to improve the text.
Notes
1. We thank the referee for calling our attention to these references.
2. The question of whether one can prove the Erdös–Straus conjecture by showing its validity on an infinite covering system of congruences is unclear, although there are good reasons to believe it to be an approach riddled with difficulties: see Terrence Tao considerations on this matter in his blog, at http://terrytao.wordpress.com/2011/07/07/on-the-number-of-solutions-to-4p-1n_1-1n_2-1n_3.