Integer Dynamics

Abstract

Let $b\ge 2$ be an integer, and write the base $b$ expansion of any non-negative integer $n$ as $n=x_0+x_{1}b+\cdots +x_d{b}^d$, with $x_d>0$ and $0\le x_i<b$ for $i=0,\dots ,d$. Let $\varphi (x)$ denote an integer polynomial such that $\varphi (n)>0$ for all $n>0$. Consider the map $S_{\varphi ,b}:{\mathbb{Z}}_{\ge 0}\to {\mathbb{Z}}_{\ge 0}$, with $S_{\varphi ,b}(n):=\varphi (x_0)+\cdots +\varphi (x_d)$. It is known that the orbit set $\{n,S_{\varphi ,b}(n),S_{\varphi ,b}(S_{\varphi ,b}(n)),\dots \}$ is finite for all $n>0$. Each orbit contains a finite cycle, and for a given $b$, the union of such cycles over all orbit sets is finite. Fix now an integer $\ell \ge 1$ and let $\varphi (x)=x^2$. We show that the set of bases $b\ge 2$ which have at least one cycle of length $\ell$ always contains an arithmetic progression and thus has positive lower density. We also show that a 1978 conjecture of Hasse and Prichett on the set of bases with exactly two cycles needs to be modified, raising the possibility that this set might not be finite.

15 pages; to appear in International Journal of Number Theory