\section{Introduction}\label{section:Introduction}

Let $\mathbb{P}$ be the set of primes. In 1930, Pillai \cite{Pillai} introduced the \textbf{prime map} $x\mapsto x-\mathbf{p}(x)$, where $\mathbf{p}(x)$ is the largest element of $\mathbb{P}\cup\{0,1\}$ not exceeding $x$, under whose iteration every positive-integer initial condition is eventually fixed at $0$, the only fixed point of the map. Interesting results on the asymptotic behaviour of the time steps $\mathrm{R}(x)$ it takes for an initial condition $x$ to reach the fixed point were established, before subsequently improved by Luca and Thangadurai \cite{Luca} in 2009. The latter authors proved that $\mathrm{R}(x)$ grows no faster than $\ln\ln x$ \cite[Theorem 1.1]{Luca}, and that for every $k\in\mathbb{N}$, the proportion of initial conditions $t\leqslant x$ for which $\mathrm{R}(t)=k$ is asymptotic to $\left(\ln_k x\right)^{-1}$, where the subscript $k$ denotes $k$-fold self-composition \cite[Theorem 1.2]{Luca}.

In this paper we study a modification of the prime map, constructed essentially by letting the role of primes be taken over by prime-powers. A \textbf{prime-power}, as is well-known, is an integer of the form $p^k$, where $p\in\mathbb{P}$ and $k\in\mathbb{N}$. Letting $\mathbb{P}^{\ast}$ be the set of prime-powers, we define the \textbf{prime-power map} $\mathbf{P}:\mathbb{N}\to\mathbb{N}$ by
$$\mathbf{P}(x):=\left\{\begin{array}{ll}
1&\text{if }x=1,\\
x-\mathbf{q}(x)&\text{if }x\notin\mathbb{P}^\ast,\\
\frac{x}{p}&\text{if }x\in\mathbb{P}^\ast\text{ is a power }p\in\mathbb{P},\\
\end{array}\right.$$
where $\mathbf{q}(x)$ is the largest element of $\mathbb{P}^\ast_{1}:=\mathbb{P}^\ast\cup\{1\}$ not exceeding $x$ (see Figure \ref{fig:plotP}). By the \textbf{orbit} of an \textbf{initial condition} $x\in\mathbb{N}$ under $\mathbf{P}$ we mean the sequence $\left(x_n\right)_{n=1}^\infty$ where
$$x_1=x\qquad\quad\text{and}\quad\qquad x_{n+1}=\mathbf{P}\left(x_n\right)\quad\text{for every }n\in\mathbb{N}.$$
Clearly, every orbit under $\mathbf{P}$ is monotonically non-increasing and eventually reaches the sole fixed point $1$ at which it then stabilises (becomes constant).

In the subdomain $\mathbb{P}^\ast_1\subseteq\mathbb{N}$ the dynamics of $\mathbf{P}$ is predictable; it consists only of divisions by primes and stabilisation. In its complement, by contrast, the dynamics is non-trivial and resembles that of Pillai's prime map. Such hybrid dynamical behaviour naturally motivates associating to every initial condition $x$ the time steps
$$\rS(x):=\min\left\{n\in\mathbb{N}:x_n\in\mathbb{P}^\ast_1\right\}\qquad\text{and}\qquad \rT(x):=\min\left\{n\in\mathbb{N}:x_n=1\right\}$$
at which the orbit of $x$ enters the predictable subdomain $\mathbb{P}^\ast_1$, and at which it reaches $1$, respectively. These will be referred to as the \textbf{settling time} and \textbf{transient length} of $x$, respectively. The unboundedness of the transient length function is immediate ---the function diverges along the sequence of powers of any given prime--- whereas that of the settling time function is less obvious and will be established in this paper. We shall also be interested in the \textbf{attractor}
$$\rA(x):=x_{\rS(x)}$$
of $x$, i.e., the element of the predictable subdomain first visited by the orbit of $x$.

\begin{figure}[h!]
\centering
\input{fig-plotP}
\caption{\label{fig:plotP}\small
The values of $\mathbf{P}(x)$ for $x\in\{1,\ldots,250\}$.}
\end{figure}

The functions $\rT$ and $\rS$ defined above constitute our primary object of study. Our main results, along with the structure of this paper, will now be described. Following this introduction is Section \ref{sec:TandS}, where we establish \textit{a logarithmic upper bound for $\rT$} (Lemma \ref{lemma:Bertrand2} and Theorem \ref{thm:power2}). Subsequently, improved versions of Lemma \ref{lemma:Bertrand2}, derived from improved versions of Bertrand's Postulate currently known in the literature, will be discussed (Propositions \ref{prop:epsilon} and \ref{prop:Bertrandrefinement}) before we turn our attention to the function $\rS$, establishing \textit{its unboundedness} (Theorem \ref{thm:unboundednessS}) and \textit{a double-logarithmic upper bound} (Theorem \ref{thm:orderS(x)}); these are analogues of the results in \cite[pages 160-161]{Pillai} and \cite[Theorem 1.1]{Luca}, respectively. Next, we will study the densities of some subsets of $\mathbb{N}$ induced by $\mathbf{P}$ and prove that  \textit{almost every positive integer is coprime with its image under $\mathbf{P}$} (Theorem \ref{thm:coprime}). At the end of the section, we connect the map $\mathbf{P}$ to the representations of integers as sums of prime-powers; of note is the discussion on the smallest initial condition having a given settling time (Proposition \ref{prop:xis}).

The detailed behaviour of the functions $\rT$ and $\rS$ is difficult to explicitise. For a comparison, in Section \ref{sec:Pp} we introduce a more manageable variant of $\mathbf{P}$: a family of maps $\mathbf{P}_p$, under which the analogous functions $\rT_p$ and $\rS_p$ admit explicit descriptions (Theorem \ref{thm:Fr}). We prove that these two functions are asymptotic (Corollary \ref{corollary}), which, together with some experimental observations, suggests that the original functions $\rT$ and $\rS$ exhibit an analogous asymptoticity. Motivated by these observations, we conjecture that \textit{almost every orbit of the prime-power map contains no prime-power} (Conjecture \ref{finalconjecture}).\bigskip

\section{Results on the map $\mathbf{P}$}\label{sec:TandS}

Before entering into our main results, let us state some fundamentals. First, we state the famous \textbf{Bertrand's Postulate} \cite[Theorem 418]{HardyWright} which will be used frequently.\bigskip

\begin{lemma}[Bertrand's Postulate]\label{lemma:Bertrand}
	 For every integer $n\geqslant 2$, there exists a prime $p$ such that $n <p< 2n$.
\end{lemma}\bigskip

We will also use standard asymptotic notations which, to ensure clarity, will now be explained. Let $f(x)$ and $g(x)$ be positive for all sufficiently large values of $x\in\mathbb{N}$. We write $f(x)\sim g(x)$ to mean $f(x)$ \textbf{is asymptotic to} $g(x)$, i.e., $\frac{f(x)}{g(x)}\xrightarrow{x\to\infty}1$. In addition, $f(x)\ll g(x)$ means $f(x)$ \textbf{is asymptotically bounded above by} $g(x)$, i.e., there exist $C>0$ and $x_0\in\mathbb{N}$ such that $f(x)\leqslant C\,g(x)$ for every integer $x\geqslant x_0$. Finally, $f(x)=o(g(x))$ means $\frac{f(x)}{g(x)}\xrightarrow{x\to\infty}0$.

\subsection{The transient length function}

First, we have
$$\limsup_{x\to\infty}\rT(x)=\infty,$$
since $\rT$ diverges along, e.g., the sequence of powers of two. More precisely, if $x$ is a power of two, we have $\rT(x)= \log_2x +1$. Let us now prove that $\log_2x +1$ is an upper bound for $\rT$ (see Figure \ref{fig:transittime}) via the following lemma which exploits Bertrand's Postulate.\bigskip

\begin{lemma}\label{lemma:Bertrand2}
For every integer $x\geqslant 2$ we have $$\mathbf{P}(x)\leqslant\frac{x}{2}.$$
\end{lemma}
\begin{proof}
Let $x\geqslant 2$. If $x=p^k$ for some $p\in\mathbb{P}$ and $k\in\mathbb{N}$, then $\mathbf{P}(x)=\frac{x}{p}\leqslant\frac{x}{2}$. Otherwise, since Bertrand's Postulate guarantees the existence of a prime between $\frac{x}{2}$ and $x$, then $\mathbf{q}(x)\geqslant\frac{x}{2}$, and hence $\mathbf{P}(x)\leqslant\frac{x}{2}$.
\end{proof}\bigskip

\begin{theorem}\label{thm:power2}
	For every $x\in\mathbb{N}$ we have $\rT(x)\leqslant \log_2x +1$ with equality if and only if $x$ is a power of two.
\end{theorem}
\begin{proof}
	By Lemma \ref{lemma:Bertrand2}, in the orbit $\left(x_n\right)_{n=1}^\infty$ of $x\in\mathbb{N}$ we have
$$1=x_{\rT(x)}\leqslant \frac{x_{\rT(x)-1}}{2}\leqslant\frac{x_{\rT(x)-2}}{2^2}\leqslant\cdots\leqslant\frac{x_1}{2^{\rT(x)-1}}=\frac{x}{2^{\rT(x)-1}},$$
which implies the desired inequality. If $x$ is a power of two, we have $\rT(x)=\log_2 x + 1$ as previously remarked. Conversely, if $\rT(x)=\log_2 x + 1$, then $x=2^{\rT(x)-1}$.
\end{proof}\bigskip

\begin{figure}
\centering
\input{fig-transittime}
\caption{\label{fig:transittime}\small
The values of $\rT(x)$ for $x\in\{1,\ldots,250\}$ and the upper bound provided by Theorem \ref{thm:power2}.}
\end{figure}

In the literature there have been numerous refinements of Bertrand's Postulate which lead to improved versions of Lemma \ref{lemma:Bertrand2}. For instance, the Prime Number Theorem implies that, given any $\varepsilon>0$, there exists $X_0\in\mathbb{N}$ such that for every integer $x\geqslant X_0$, the interval $\left[x-\varepsilon x,x\right]$ contains a prime number \cite[Section 22.19]{HardyWright}, implying that $\mathbf{P}(x)\leqslant\varepsilon x$ if $x$ is not a prime-power. Therefore, we have the following proposition.\bigskip

\begin{proposition}\label{prop:epsilon}
For every $\varepsilon>0$ there exists $X_0\in\mathbb{N}$ such that
\begin{equation}\label{eq:epsilon}
\mathbf{P}(x)\leqslant\varepsilon x
\end{equation}
for every non-prime-power $x\geqslant X_0$.
\end{proposition}\bigskip

Notice that, since for every prime-power $x=p^k$ we have $\frac{\mathbf{P}(x)}{x}=\frac{1}{p}\leqslant\frac{1}{2}$ with equality if and only if $p=2$, there is no $\varepsilon<\frac{1}{2}$ such that \eqref{eq:epsilon} holds for \textit{all} sufficiently large $x$. In this sense, the non-universality of \eqref{eq:epsilon} ---the fact that it holds only for non-prime-powers--- is unavoidable. However, for every $\varepsilon>0$ one can always choose a sufficiently large $X_1\in\mathbb{N}$ such that \eqref{eq:epsilon} holds for all powers of all primes $p\geqslant X_1$.

Hoheisel \cite{Hoheisel}, as cited in \cite[Section 2]{Luca}, proved the following development of Bertrand's Postulate.\bigskip

\begin{lemma}\label{lemma:Hoheisel}
There exist $\theta\in(0,1)$ and $X_0\in\mathbb{N}$ such that for every $x\geqslant X_0$ the interval $\left[x-x^\theta,x\right]$ contains a prime number.
\end{lemma}\bigskip

\noindent This lemma immediately implies the following proposition.\bigskip

\begin{proposition}\label{prop:Bertrandrefinement}
There exist $\theta\in(0,1)$ and $X_0\in\mathbb{N}$ such that
$$\mathbf{P}(x)\leqslant x^{\theta}$$
for every non-prime-power $x\geqslant X_0$.
\end{proposition}\bigskip

\noindent The authors of \cite{Baker} have proved the existence of $X_0\in\mathbb{N}$ for which one could take $\theta=0.525$.\bigskip

\subsection{The settling time function}

In the first half of this subsection we follow the steps of Pillai's proof in \cite[pages 160-161]{Pillai} of the unboundedness of $\mathrm{R}$. In the work cited, Pillai proved that
$$\limsup_{x\to\infty}\mathrm{R}(x)=\infty$$
using a well-known result on the unboundedness of gaps between primes, i.e., that for every $n\in\mathbb{N}$, none of the $n-1$ consecutive positive integers
$$n!+2,\,\,\,n!+3,\,\,\,\ldots,\,\,\,n!+n$$
is prime, implying the existence of two consecutive primes $p_1$ and $p_2$ such that $p_2-p_1\geqslant n$ \cite[Lemma 1]{Pillai}. Here we first modify this argument to show the unboundedness of gaps between prime-powers. Then we will use the result to prove that
$$\limsup_{x\to\infty}\rS(x)=\infty.$$\smallskip

\begin{lemma}\label{lemma:PrimePowerGap}
	For every $n\in\mathbb{N}$ there exist two consecutive prime-powers $q_1$ and $q_2$ such that $q_2-q_1\geqslant n$.
\end{lemma}
\begin{proof}
    Let $n\in\mathbb{N}$. If $n=1$, clearly the lemma holds. Now, suppose $n\geqslant 2$. Let $p_1$, \ldots, $p_m$, where $m\in\mathbb{N}$, be all prime numbers not exceeding $n$. For every $i\in\{1,\ldots,m\}$, define
    $$k_i=\max\{k\in\mathbb{N}:p_i^k\leqslant n\}.$$
    Furthermore, let
    $$\mathcal{N}:=\prod_{i=1}^{m} p_i^{k_i+1}.$$

    We will now prove that none of the $n-1$ consecutive positive integers
    $$\mathcal{N}+2,\,\,\,\mathcal{N}+3,\,\,\,\ldots,\,\,\,\mathcal{N}+n$$
	is a prime-power. Let $i\in\{2,\ldots,n\}$. Consider the number $\mathcal{N}+i$ which is divisible by $i$. If $i$ is not a prime-power, this immediately implies that $\mathcal{N}+i$ is not a prime-power. If $i$ is a prime-power, say $p^\ell$, then $\mathcal{N}+i=\mathcal{N}+p^\ell$ is a number greater than $p^\ell$ which is not divisible by $p^{\ell+1}$ (since $\mathcal{N}$ is divisible by $p^{\ell+1}$ but $p^\ell$ is not), and so it has a prime factor other than $p$, meaning that it is not a prime-power.

	Now, let $q_1$ be the largest prime-power less than $\mathcal{N}+2$ and $q_2$ be the smallest prime-power greater than $\mathcal{N}+n$. Then $$q_2-q_1\geqslant (\mathcal{N}+n+1)-(\mathcal{N}+1)\geqslant n,$$
	proving the lemma.
\end{proof}\bigskip

\begin{theorem}\label{thm:unboundednessS}
	We have
	$$\limsup_{x\to\infty} \rS(x)=\infty.$$
\end{theorem}
\begin{proof}
The theorem follows if we can prove that for every non-prime-power $x\in\mathbb{N}$ there exists a non-prime-power $y\in\mathbb{N}$ such that $\rS(y)=\rS(x)+1$. Let $x\in\mathbb{N}$ be a non-prime-power. By Lemma \ref{lemma:PrimePowerGap}, there exist two consecutive prime-powers $q_1$ and $q_2$ such that $q_2-q_1\geqslant x+1$, i.e., $q_1+x+1\leqslant q_2$. Now, pick $y=q_1+x$. Then $q_1<y<q_2$, so $y$ is not a prime-power and the largest prime-power not exceeding $y$ is $q_1$. Therefore, $\mathbf{P}(y)=y-q_1=x$, meaning that $\rS(y)=\rS(x)+1$, as desired.
\end{proof}\bigskip

Luca and Thangadurai proved that $\mathrm{R}(x)\ll \ln\ln x$ \cite[Theorem 1.1]{Luca}. Now, we will prove that the same asymptotic upper bound also applies for the settling time function $\rS$, following the argument in the work cited. First, we take numbers $X_0\in\mathbb{N}$ and $\theta\in(0,1)$ which satisfy Lemma \ref{lemma:Hoheisel} (and hence Proposition \ref{prop:Bertrandrefinement}). Then we have the following lemma.\bigskip

\begin{lemma}\label{lemma:orderS(x)}
Let $x\geqslant X_0$, and let $\left(x_n\right)_{n=1}^\infty$ be the orbit of $x$. Then for every $k\in\mathbb{N}$ the following holds:
$$\text{If }x_k\geqslant X_0\text{ and }\rS(x)\geqslant k+1,\text{ then }x_{k+1}\leqslant x^{\theta^k}.$$
\end{lemma}
\begin{proof}
We use induction on $k\in\mathbb{N}$. For $k=1$ the statement reads
$$\text{If }x_1\geqslant X_0\text{ and }\rS(x)\geqslant 2,\text{ then }x_{2}\leqslant x^{\theta},$$
which is true since, if $x_1\geqslant X_0$ and $\rS(x)\geqslant 2$, the latter implying that $x_1$ is not a prime-power, then $$x_2=\mathbf{P}\left(x_1\right)\leqslant {x_1}^\theta=x^\theta,$$ by Proposition \ref{prop:Bertrandrefinement}.

Now let $k\geqslant 2$, and suppose the statement holds for $k-1$ replacing $k$. Suppose $x_k\geqslant X_0$ and $\rS(x)\geqslant k+1$. The former implies that $x_{k-1}\geqslant X_0$ since $x_{k-1}\geqslant x_k$, while the latter implies that $\rS(x)\geqslant k$ and that $x_{k}$ is not a prime-power. Therefore, our inductive hypothesis gives $x_k\leqslant x^{\theta^{k-1}}$, and so by Proposition \ref{prop:Bertrandrefinement},
$$x_{k+1}=\mathbf{P}\left(x_k\right)\leqslant {x_k}^\theta\leqslant \left(x^{\theta^{k-1}}\right)^\theta=x^{\theta^k},$$
completing the induction.
\end{proof}\bigskip

\begin{theorem}\label{thm:orderS(x)}
We have
$$\rS(x)\ll\ln\ln x.$$
\end{theorem}
\begin{proof}
Define $X_0':=\max\left\{X_0,e\right\}$. Let $x\geqslant X_0'$, and let $\left(x_n\right)_{n=1}^\infty$ be the orbit of $x$. Define
$$k:=\min\{\rS(x),\ell\}-1\in\mathbb{N}_0,\qquad\text{where}\qquad \ell:=\max\left\{\lambda\in\mathbb{N}:x_\lambda\geqslant X_0'\right\},$$
the existence of $\ell$ being guaranteed by the fact that $x_1=x\geqslant X_0'>1$.

By the definition of $k$ we have that $k\leqslant \rS(x)-1$ and $k\leqslant\ell-1$ (i.e., $k+1\leqslant\ell$), implying $\rS(x)\geqslant k+1$ and $x_k\geqslant x_{k+1}\geqslant x_{\ell}\geqslant X_0'\geqslant X_0$, respectively. Then we have the inequality
$$
x_{k+1}\leqslant x^{\theta^k},
$$
which is trivially true if $k=0$ and implied by Lemma \ref{lemma:orderS(x)} if $k\geqslant 1$. This inequality, together with the fact that $x_{k+1}\geqslant X_0'$, implies
$$X_0'\leqslant x^{\theta^k}.$$
Taking logarithms twice gives
$$\ln \ln X_0'\leqslant k \ln\theta + \ln\ln x.$$
Since $X_0'\geqslant e$, the left-hand side is non-negative, and hence so is the right-hand side, i.e.,
$$k\leqslant\frac{\ln\ln x}{\ln\frac{1}{\theta}}.$$
Letting $m:=\max\left\{\rS(1),\ldots,\rS\left(X_0'\right)\right\}$, by the definitions of $k$ and $\ell$ we have
$$\rS(x)\leqslant k+1+m\leqslant\frac{\ln\ln x}{\ln\frac{1}{\theta}}+1+m\ll \ln \ln x,$$
proving the theorem.
\end{proof}\bigskip

\subsection{Densities of subsets of $\mathbb{N}$ induced by $\mathbf{P}$} Let us now discuss the densities of some positive integer sets induced by $\mathbf{P}$, for which the following standard terminology \cite{Sonnenschein,Tenenbaum} will be used. Given a subset $A\subseteq\mathbb{N}$. For every $x\in\mathbb{N}$, we define
$$\mathbf{d}_x A:=\frac{|A\cap\{1,\ldots,x\}|}{x}.$$
The (\textbf{natural}) \textbf{density} of $A$ is the limit
$$\mathbf{d} A:=\lim_{x\to\infty}\mathbf{d}_x A,$$
if it exists. If $\mathbf{d} A=0$, we say that $A$ is \textbf{sparse}. If $\mathbf{d} A=1$, we say that $A$ has \textbf{full density}. If $\mathbf{d} A=1$ and a statement $\mathcal{P}(x)$ holds for every $x\in A$, we say that $\mathcal{P}(x)$ holds for \textbf{almost every} $x\in\mathbb{N}$.

It is fairly well known that the sets $\mathbb{P}$ and $\mathbb{P}^\ast$ are both sparse. This can be deduced by considering the prime and prime-power counting functions
$$\pi(x):=\left|\mathbb{P}\cap\{1,\ldots,\lfloor x\rfloor\}\right|\qquad\text{and}\qquad\Pi(x):=\left|\mathbb{P}^\ast\cap\{1,\ldots,\lfloor x\rfloor\}\right|$$
defined for real numbers $x>0$. Clearly, $\pi(x)\leqslant\Pi(x)$ for every $x>0$. The \textbf{Prime Number Theorem} \cite[page 10]{HardyWright} gives the asymptotic
$$
\pi(x)\sim\frac{x}{\ln x},
$$
from which it follows that $\mathbb{P}$ is sparse. Moreover, since
$$\Pi(x)-\pi(x)=\sum_{j=2}^{\left\lfloor\log_2 x\right\rfloor}\pi\left(x^{\frac{1}{j}}\right)\ll\frac{x^{\frac{1}{2}}}{\ln x^{\frac{1}{2}}}\left(\left\lfloor\log_2 x\right\rfloor-1\right)\ll x^{\frac{1}{2}},$$
then $\Pi(x)\sim\pi(x)$, implying that $\mathbb{P}^\ast$ is also sparse. Some immediate consequences are:\smallskip
\begin{enumerate}\setlength{\itemsep}{4pt}
\item[i)] The set $\rT^{-1}\left(\mathbb{N}_{\geqslant 3}\right)$ has full density because $\rT^{-1}(\{1\})=\{1\}$ and $\rT^{-1}(\{2\})=\mathbb{P}\cup\left(\mathbb{P}^\ast+1\right)$ are both sparse\footnote{For every $k\in\mathbb{N}$, we denote by $\mathbb{N}_{\geqslant k}$ the set of positive integers greater than or equal to $k$. Also, $\mathbb{P}^\ast+1:=\left\{q+1:q\in\mathbb{P}^\ast\right\}$.}.
\item[ii)] The set $\rS^{-1}\left(\mathbb{N}_{\geqslant 2}\right)$ has full density because $\rS^{-1}(\{1\})=\mathbb{P}^\ast_1$ is sparse.
\item[iii)] The set $\left\{x\in\mathbb{N}:\mathbf{P}(x)\leqslant\varepsilon x\right\}$ is sparse if $\varepsilon\leqslant 0$ and has full density if $\varepsilon>0$.
\item[iv)] There exists $\theta\in(0,1)$ such that the set $\left\{x\in\mathbb{N}:\mathbf{P}(x)\leqslant x^\theta\right\}$ has full density.
\end{enumerate}\smallskip
The last two follow from Propositions \ref{prop:epsilon} and \ref{prop:Bertrandrefinement}, respectively.

Every $x\in\mathbb{N}_{\geqslant 2}\backslash\mathbb{P}$ and its image under the \textit{prime map} is coprime; for if they have a prime common divisor then it must divide $\mathbf{p}(x)$, and so must equal to $\mathbf{p}(x)$, implying that $x\geqslant 2\mathbf{p}(x)$ which contradicts Bertrand's Postulate. Under the \textit{prime-power map}, however, the analogue does not hold. Indeed, the number $34\in\mathbb{N}_{\geqslant2}\backslash\mathbb{P}^\ast$ and its image $\mathbf{P}(34)=2$ are not coprime. Nonetheless, we shall now prove that $x$ and $\mathbf{P}(x)$ are coprime for almost every $x\in\mathbb{N}$. For this purpose, we define
$$\mathbb{G}:=\left\{x\in\mathbb{N}:\gcd(x,\mathbf{P}(x))>1\right\},$$
and we choose numbers $X_1\in\mathbb{N}$ and $\theta\in(0,1)$ such that for every $x\geqslant X_1$ the interval $\left[x,x+x^\theta\right]$ contains a prime number\footnote{The existence is again guaranteed by \cite{Baker}.}. Our aim is to show that $\mathbf{d}\mathbb{G}=0$ via the following lemma.\bigskip

\begin{lemma}\label{lemma:dG}
For every prime-power $p^k\geqslant X_1$, where $p\in\mathbb{P}$ and $k\in\mathbb{N}$, we have
$$\textstyle\left|\left[\mathbb{G}\cap \mathbf{q}^{-1}\left(\left\{p^k\right\}\right)\right]\backslash\mathbb{P}^\ast\right|\leqslant p^{k\theta-1}.$$
\end{lemma}
\begin{proof}
\sloppy Let $p^k\geqslant X_1$ be a prime-power, where $p\in\mathbb{P}$ and $k\in\mathbb{N}$. For every $x\in \left[\mathbb{G}\cap \mathbf{q}^{-1}\left(\left\{p^k\right\}\right)\right]\backslash\mathbb{P}^\ast$ we have that $x\notin\mathbb{P}^\ast$ is a preimage of $p^k$ under $\mathbf{q}$ satisfying
$$\textstyle 1<\gcd(x,\mathbf{P}(x))=\gcd\left(x,x-p^k\right)=\gcd\left(x,p^k\right),$$
so $x$ is a multiple of $p$, and that $x\in\left(p^k,p^k+p^{k\theta}\right]$. Therefore, the number of elements of $\left[\mathbb{G}\cap \mathbf{q}^{-1}\left(\left\{p^k\right\}\right)\right]\backslash\mathbb{P}^\ast$ is bounded above by the number of multiples of $p$ in the interval $\left(p^k,p^k+p^{k\theta}\right]$, namely
$$\left|\left\{p^k+p,\ldots,p\left\lfloor\frac{p^k+p^{k\theta}}{p}\right\rfloor\right\}\right|=\frac{p\left\lfloor\frac{p^k+p^{k\theta}}{p}\right\rfloor-p^k}{p}\leqslant p^{k\theta-1},$$
proving the lemma.
\end{proof}\bigskip

\begin{theorem}\label{thm:coprime}
The set $\mathbb{G}$ is sparse.
\end{theorem}
\begin{proof}
Since
$$\mathbf{d}\mathbb{G}=\mathbf{d}\left(\mathbb{G}\cap\mathbb{P}^\ast\right)+\mathbf{d}\left(\mathbb{G}\backslash\mathbb{P}^\ast\right)$$
and $\mathbf{d}\left(\mathbb{G}\cap\mathbb{P}^\ast\right)=0$, it suffices to prove that $\mathbf{d}\left(\mathbb{G}\backslash\mathbb{P}^\ast\right)=0$.

Notice that for every $x\in\mathbb{N}$ we have
$$\mathbf{d}_x\left(\mathbb{G}\backslash\mathbb{P}^\ast\right)=\frac{\left|\left(\mathbb{G}\backslash\mathbb{P}^\ast\right)\cap\{1,\ldots,x\}\right|}{x}\leqslant \frac{1}{x}\sum_{1\leqslant p^k\leqslant x}\textstyle\left|\left[\mathbb{G}\cap \mathbf{q}^{-1}\left(\left\{p^k\right\}\right)\right]\backslash\mathbb{P}^\ast\right|,$$
where the summation is taken over all prime-powers $p^k\in\{1,\ldots,x\}$. Now, the last expression is equal to
$$\frac{1}{x}\sum_{1\leqslant p\leqslant x}\sum_{k=1}^{\left\lfloor\log_p x\right\rfloor}\textstyle\left|\left[\mathbb{G}\cap \mathbf{q}^{-1}\left(\left\{p^k\right\}\right)\right]\backslash\mathbb{P}^\ast\right|,$$
where the outer summation is taken over all primes $p\in\{1,\ldots,x\}$. By Lemma \ref{lemma:dG}, this expression is asymptotically bounded above by
$$\frac{1}{x}\sum_{X_1\leqslant p\leqslant x}\sum_{k=1}^{\left\lfloor\log_p x\right\rfloor}p^{k\theta-1},$$
where the outer summation is taken over all primes $p\in\left\{X_1,\ldots,x\right\}$. This expression is bounded above by
$$\frac{1}{x}\sum_{j=2}^x\sum_{k=1}^{\left\lfloor\log_j x\right\rfloor}j^{k\theta-1} = \frac{1}{x}\sum_{j=2}^x \frac{j^{\theta-1}\left[\left(j^\theta\right)^{\left\lfloor\log_j x\right\rfloor}-1\right]}{j^\theta-1}\sim\frac{1}{x^{1-\theta}}\sum_{j=2}^x\frac{1}{j}\leqslant \frac{\ln x}{x^{1-\theta}}.$$
Since $\theta\in(0,1)$, the last expression vanishes as $x\to\infty$, so we have proved the theorem.
\end{proof}\bigskip

\subsection{Connection to prime-power representations} As the \textit{prime map} is closely connected to \textbf{prime representations} \cite[page 159]{Pillai}, so is the \textit{prime-power map} to \textbf{prime-power representations} of positive integers. More precisely, every initial condition $x\in\mathbb{N}$ is associated to, besides its orbit, the sequence $\left(\mathbf{q}\left(x_n\right)\right)_{n=1}^{\rS(x)}$ which gives a way to express $x$ as the sum of elements of $\mathbb{P}^\ast_1$:
\begin{eqnarray}\label{eq:primepowerrepresentation}
x &=& x_1\nonumber\\
  &=& \mathbf{q}\left(x_1\right) + x_2\nonumber\\
  &=& \mathbf{q}\left(x_1\right) + \mathbf{q}\left(x_2\right) + x_3\nonumber\\
  &=& \cdots\nonumber\\
  &=& \mathbf{q}\left(x_1\right) + \mathbf{q}\left(x_2\right)+\cdots+\mathbf{q}\left(x_{\rS(x)-1}\right)+x_{\rS(x)}\nonumber\\
  &=& \mathbf{q}\left(x_1\right) + \mathbf{q}\left(x_2\right)+\cdots+\mathbf{q}\left(x_{\rS(x)-1}\right)+\mathbf{q}\left(x_{\rS(x)}\right).
\end{eqnarray}
Here we have that
$$\mathbf{q}\left(x_1\right)> \mathbf{q}\left(x_2\right)> \cdots > \mathbf{q}\left(x_{\rS(x)}\right)$$
which follows from the following two lemmas.\bigskip

\begin{lemma}\label{lemma:monotonicity}
For every $x,y\in\mathbb{N}$, if $x\leqslant y$ then $\mathbf{q}(x)\leqslant \mathbf{q}(y)$.
\end{lemma}
\begin{proof}
If the hypothesis holds and $\mathbf{q}(x)>\mathbf{q}(y)$, then $\mathbf{q}(y)<\mathbf{q}(x)\leqslant x\leqslant y$, so $\mathbf{q}(x)$ is an element of $\mathbb{P}^\ast_1$ not exceeding $y$ which is greater than $\mathbf{q}(y)$, contradicting the definition of $\mathbf{q}(y)$.
\end{proof}\bigskip

\begin{lemma}\label{lemma:monotonicity2}
For every initial condition $x\in\mathbb{N}$, the sequence $\left(\mathbf{q}\left(x_n\right)\right)_{n=1}^{\rS(x)}$ is monotonically decreasing.
\end{lemma}
\begin{proof}
Let $x\in\mathbb{N}$. If $\rS(x)=1$ then there is nothing to prove. Otherwise, we have $\mathbf{q}\left(x_1\right)\geqslant \mathbf{q}\left(x_2\right)\geqslant \cdots \geqslant \mathbf{q}\left(x_{\rS(x)}\right)$ by Lemma \ref{lemma:monotonicity}. Suppose for a contradiction that there exists $n\in\{1,\ldots,\rS(x)-1\}$ such that $\mathbf{q}\left(x_n\right)=\mathbf{q}\left(x_{n+1}\right)$. Then $$2\mathbf{q}\left(x_n\right)=\mathbf{q}\left(x_n\right)+\mathbf{q}\left(x_{n+1}\right)=\left(x_n-x_{n+1}\right)+\left(x_{n+1}-x_{n+2}\right)\leqslant x_n.$$
But between $\mathbf{q}\left(x_n\right)$ and $2\mathbf{q}\left(x_n\right)$ there is a prime by Bertrand's Postulate, contradicting the definition of $\mathbf{q}\left(x_n\right)$.
\end{proof}\bigskip

Clearly, there could be many ways to represent $x\in\mathbb{N}$ as the sum of elements of $\mathbb{P}^\ast_1$. The one given by \eqref{eq:primepowerrepresentation} is the result of applying the \textbf{greedy algorithm}: for each $n\in\{1,\ldots,\rS(x)\}$, one chooses the largest element $\mathbf{q}\left(x_n\right)$ of $\mathbb{P}^\ast_{1}$ not exceeding $x_n$. As in \cite[page 164]{Pillai} and \cite[page 695]{Luca}, a question one could ask is, for every $s\in\mathbb{N}$, what is the smallest positive integer which is expressed by the greedy algorithm as the sum of exactly $s$ elements of $\mathbb{P}^\ast_1$? These are precisely the numbers $\xi_s:=\min\rS^{-1}(\{s\})$ for every $s\in\mathbb{N}$. The values of $\xi_1$, $\xi_2$, $\xi_3$, and $\xi_4$ are
$$1=1,\quad 6=5+1,\quad 95=89+5+1,\quad\text{and}\quad 360748=360653+89+5+1,$$
respectively. Anyone attempting to compute the subsequent values should take into consideration the following facts.\bigskip

\begin{proposition}\label{prop:xis}\textcolor{white}{a}
\begin{enumerate}
\item[i)] For every $s\in\mathbb{N}$ we have $\mathbf{P}\left(\xi_{s+1}\right)=\xi_s$.
\item[ii)] For every $s\in\mathbb{N}$ we have $\xi_{s+1}=\min\mathbf{P}^{-1}\left(\left\{\xi_{s}\right\}\right)$.
\item[iii)] For every integer $s\geqslant 3$, the number $\xi_s$ is not a prime-power.
\item[iv)] We have $$\frac{\xi_{s+1}}{\xi_s},\frac{\mathbf{q}\left(\xi_{s+1}\right)}{\mathbf{q}\left(\xi_s\right)}\xrightarrow{x\to\infty}\infty.$$
\end{enumerate}
\end{proposition}
\begin{proof}
First, we prove i). Let $s\in\mathbb{N}$. Since $\rS\left(\xi_{s+1}\right)=s+1$, then $\rS\left(\mathbf{P}\left(\xi_{s+1}\right)\right)=s$, so $\xi_s\leqslant \mathbf{P}\left(\xi_{s+1}\right)$. To prove that $\xi_s=\mathbf{P}\left(\xi_{s+1}\right)$, suppose for a contradiction that $\xi_s< \mathbf{P}\left(\xi_{s+1}\right)$. Then,
$$\mathbf{q}\left(\xi_{s+1}\right)<\mathbf{q}\left(\xi_{s+1}\right)+\xi_s<\mathbf{q}\left(\xi_{s+1}\right)+\mathbf{P}\left(\xi_{s+1}\right)=\xi_{s+1}.$$
Since $\mathbf{q}\left(\xi_{s+1}\right)$ is the largest prime-power not exceeding $\xi_{s+1}$, this implies that $\mathbf{q}\left(\xi_{s+1}\right)+\xi_s$ is not a prime-power, and that $\mathbf{q}\left(\xi_{s+1}\right)$ is also the largest prime-power not exceeding $\mathbf{q}\left(\xi_{s+1}\right)+\xi_s$. The latter implies that
$$\mathbf{P}\left(\mathbf{q}\left(\xi_{s+1}\right)+\xi_s\right)=\left[\mathbf{q}\left(\xi_{s+1}\right)+\xi_s\right]-\mathbf{q}\left(\xi_{s+1}\right)=\xi_s,$$
so $\mathbf{q}\left(\xi_{s+1}\right)+\xi_s$ is a positive integer less than $\xi_{s+1}$ having settling time
$$\rS\left(\mathbf{q}\left(\xi_{s+1}\right)+\xi_s\right)=\rS\left(\xi_s\right)+1=s+1,$$
contradicting the definition of $\xi_{s+1}$.

Both ii) and iii) are immediate consequences of i). To prove iv), notice that, by Proposition \ref{prop:Bertrandrefinement}, there exists $\theta\in(0,1)$ such that
$$\xi_{s}=\mathbf{P}\left(\xi_{s+1}\right)\leqslant{\xi_{s+1}}^\theta,\qquad\text{i.e.},\qquad \frac{\xi_{s+1}}{\xi_s}\geqslant {\xi_{s+1}}^{1-\theta},$$
for all sufficiently large values of $s$. This implies
$$\frac{\xi_{s+1}}{\xi_s}\xrightarrow{s\to\infty}\infty\qquad\text{and}\qquad\frac{\mathbf{q}\left(\xi_{s+1}\right)}{\mathbf{q}\left(\xi_s\right)}=\frac{\xi_{s+1}-\xi_s}{\xi_s-\xi_{s-1}}=\frac{\frac{\xi_{s+1}}{\xi_s}-1}{1-\frac{1}{\left(\frac{\xi_s}{\xi_{s-1}}\right)}}\xrightarrow{s\to\infty}\infty,$$
as desired.
\end{proof}\bigskip

Part i) of Proposition \ref{prop:xis} also means that for every $s\in\mathbb{N}$ we have $\xi_{s+1}=\xi_s+q_1$, where $\left(q_1,q_2\right)$ is the first pair of consecutive prime-powers with $q_2-q_1\geqslant\xi_s+1$. Therefore, to compute $\xi_5$ one must find the first pair of consecutive prime-powers differing by at least $360749$.\bigskip

\section{The family of maps $\mathbf{P}_p$}\label{sec:Pp}

The unpredictability of the functions $\rT$ and $\rS$ largely originates from the fact that the prime number $p$ acting at each iteration of $\mathbf{P}$ is not fixed. Take as an initial condition, for instance, $x_1=35$. At the first iteration, which produces $x_2=\mathbf{P}(35)=35-2^5=3$, the acting prime is $2$. However, at the second, which produces $x_3=\mathbf{P}(3)=\frac{3}{3}=1$, the acting prime is $3$. In order to eliminate this unpredictability, and for a comparison, let us now consider a modification of the map $\mathbf{P}$ constructed by fixing the acting prime. This consists in a one-parameter family of maps $\mathbf{P}_p$, where $p\in\mathbb{P}$. As we shall see, all orbits of $\mathbf{P}_p$ are predictable via the base-$p$ representations of the iterates (Lemma \ref{transmap}), and hence so are their transient lengths and settling times (Theorem \ref{thm:Fr}).\bigskip

\subsection{The maps $\mathbf{P}_p$}

Fix a prime $p\in\mathbb{P}$. Define the map $\mathbf{P}_p:\mathbb{N}\to\mathbb{N}$ by
\begin{equation}\label{eq:Fr}
\mathbf{P}_p(x):=\left\{\begin{array}{cl}
x&\text{if }1\leqslant x\leqslant p-1,\\
x-\mathbf{q}_p(x)&\text{if }x\text{ is not a power of }p,\\
\frac{x}{p}&\text{if }x\text{ is a power of }p,
\end{array}\right.
\end{equation}
where $\mathbf{q}_p(x)$ is the largest power of $p$ not exceeding $x$. Notice that this map has $p-1$ distinct fixed points: $1$, \ldots, $p-1$.

As in the original map, the \textbf{orbit} of $x\in\mathbb{N}$ under the map $\mathbf{P}_p:\mathbb{N}\to\mathbb{N}$ is the sequence $\left(x_n\right)_{n=1}^\infty$ where
$$x_1=x\qquad\quad\text{and}\quad\qquad x_{n+1}=\mathbf{P}_p\left(x_n\right)\quad\text{for every }n\in\mathbb{N}.$$
The \textbf{transient length} and \textbf{limit} of $x$ under $\mathbf{P}_p$ are the positive integers
$$\rT_p(x):=\min\bigl\{n\in\mathbb{N}:x_n\in\{1,\ldots,p-1\}\bigr\}\qquad\text{and}\qquad \rL_p(x):=x_{\rT_p(x)},$$
respectively. Equivalently, $\rL_p(x)=\lim\limits_{n\to\infty} x_n$, and $\rT_p(x)$ is the index of the first term in the orbit having value $\rL_p(x)$. One immediately sees that $\rT_p$ is unbounded since it diverges along, e.g., the sequence of powers of $p$. The \textbf{settling time} and the \textbf{attractor} of $x$ under $\mathbf{P}_p$ are the positive integers
$$\rS_p(x):=\min\bigl\{n\in\mathbb{N}:x_n\in\{1,\ldots,p-1\}\cup\bigl\{p^k:k\in\mathbb{N}\bigr\}\bigr\}\qquad\text{and}\qquad \rA_p(x):=x_{\rS_p(x)},$$
respectively.

Our aim is to derive explicit formulae for $\rT_p(x)$, $\rL_p(x)$, $\rS_p(x)$, and $\rA_p(x)$ in terms of $p$ and $x$. This will be achieved using some number-theoretic tools; see \cite{HardyWright,Koshy} for background. First, the \textbf{$p$-adic value} \cite[page 562]{HardyWright} of $x$ is the non-negative integer
$$\nu_p(x):=\max\left\{m\in\mathbb{N}_0:p^m\mid x\right\},$$
i.e., the exponent of the largest power of $p$ which divides $x$. Moreover, we denote by $x\,\,\mathrm{mod}\,\, p$ the remainder when $x$ is divided by $p$ \cite[page 71]{Koshy}, $\mathcal{S}_p(x)$ the sum of the coefficients in the \textbf{base-$p$ representation} \cite[Section 2.2]{Koshy} of $x$, and
$$\mathcal{S}_p^\ast(x):=\mathcal{S}_p(x)-(x\,\,\mathrm{mod}\,\, p).$$
The formulae are given by the following theorem.\bigskip

\begin{theorem}\label{thm:Fr}
Let $p\in\mathbb{P}$. For every $x\in\mathbb{N}$ we have
\begin{eqnarray*}
\rT_p(x)&=&
\begin{cases}
\mathcal{S}_p^\ast(x)+\nu_p(x)&\text{if }p\mid x,\\
\mathcal{S}_p^\ast(x)+1&\text{otherwise},
\end{cases}\\
\rL_p(x)&=&\begin{cases}
1&\text{if }p\mid x,\\
x\,\,\mathrm{mod}\,\, p&\text{otherwise},
\end{cases}\\
\rS_p(x)&=&\begin{cases}
\mathcal{S}_p^\ast(x)&\text{if }p\mid x,\\
\mathcal{S}_p^\ast(x)+1&\text{otherwise},
\end{cases}\\
\rA_p(x)&=&\begin{cases}
p^{\nu_p(x)}&\text{if }p\mid x,\\
x\,\,\mathrm{mod}\,\, p&\text{otherwise}.
\end{cases}
\end{eqnarray*}
\end{theorem}\bigskip

To prove this theorem, we first study the structure of the orbits of the map $\mathbf{P}_p$. This will be done by looking at how the base-$p$ representation of $x$ changes under an application of $\mathbf{P}_p$. More formally, we study the conjugate map $\overline{\mathbf{P}}_p:=\Psi_p\circ \mathbf{P}_p\circ {\Psi_p}^{-1}$, where $\Psi_p$ is the bijection associating to every positive integer the infinite sequence whose terms are the coefficients $a_0,\ldots,a_k\in\mathbb{Z}_p$, where $a_k\neq0$ and $k\in\mathbb{N}_0$, in its base-$p$ representation $\sum_{i=0}^k a_ip^i$ followed by infinitely many zeros\footnote{Denoted using the standard notation $\overline{0}$.} [e.g., $\Psi_2(6)=\left(0,1,1,\overline{0}\right)$], as a self-map on the space $\Omega_p$ of all such sequences (see Figure \ref{fig:conjugation}). The action of the map $\overline{\mathbf{P}}_p$ is described by the following lemma.\bigskip

\begin{figure}
\centering
\input{fig-conjugation}
\caption{\label{fig:conjugation}\small
The commutative diagram representing the conjugation $\overline{\mathbf{P}}_p=\Psi_p\circ \mathbf{P}_p\circ {\Psi_p}^{-1}$.}
\end{figure}

\begin{lemma}\label{transmap}
The image of $\left(a_0,\ldots,a_k,\overline{0}\right)\in\Omega_p$, where $a_k\neq0$ and $k\in\mathbb{N}_0$, under $\overline{\mathbf{P}}_p$ is given by
\begin{equation}\label{eq:transmap}
\overline{\mathbf{P}}_p\left(a_0,\ldots,a_k,\overline{0}\right)=\begin{cases}
\left(a_0,\ldots,a_k,\overline{0}\right)&\text{if }k=0,\\
\left(a_1,\ldots,a_k,\overline{0}\right)&\text{if }k\geqslant 1\text{ and }a_0=\cdots=a_{k-1}=0\text{ and }a_k=1,\\
\left(a_0,\ldots,a_k-1,\overline{0}\right)&\text{otherwise}.
\end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Let $x:={\Psi_p}^{-1}\left(a_0,\ldots,a_k,\overline{0}\right)\in\mathbb{N}$. This means that $\sum_{i=0}^k a_ip^i$ is the base-$p$ representation of $x$.
\begin{enumerate}
\item[i)] If $k=0$ then $1\leqslant x\leqslant p-1$, so $\mathbf{P}_p(x)=x$. In other words, $\overline{\mathbf{P}}_p\left(a_0,\ldots,a_k,\overline{0}\right)=\left(a_0,\ldots,a_k,\overline{0}\right)$.\medskip
\item[ii)] Suppose $k\geqslant1$, $a_0=a_1=\cdots=a_{k-1}=0$, and $a_k=1$. Then $x=p^k\geqslant p$, so $\mathbf{P}_p(x)=\frac{x}{p}=p^{k-1}$. In other words, $\overline{\mathbf{P}}_p\bigl(\underbrace{0,\ldots,0}_k,1,\overline{0}\bigr)=\bigl(\underbrace{0,\ldots,0}_{k-1},1,\overline{0}\bigr)$, i.e., $\overline{\mathbf{P}}_p\left(a_0,\ldots,a_k,\overline{0}\right)=\left(a_1,\ldots,a_k,\overline{0}\right)$.
\item[iii)] Suppose $k\geqslant1$, and suppose at least one of the following is not true: $a_0=\cdots=a_{k-1}=0$ and $a_k=1$. Then, $x$ is not a power of $p$; for otherwise, since $x>p^k$, we must have that $x=p^\ell$ for some integer $\ell>k$, meaning that $p^\ell$ is the unique base-$p$ representation of $x$, in which the leading coefficient is $1$ and all the other coefficients are $0$, contradicting our supposition. Since $p^k$ is the largest power of $p$ not exceeding $x$, then $\mathbf{P}_p(x)=x-p^k=\sum_{i=0}^{k-1} a_ip^i + \left(a_k-1\right)p^k$. In other words, $\overline{\mathbf{P}}_p\left(a_0,\ldots,a_k,\overline{0}\right)=\left(a_0,\ldots,a_k-1,\overline{0}\right)$.
\end{enumerate}
\end{proof}\bigskip

For every $x\in\mathbb{N}$, Lemma \ref{transmap} gives a complete description of the orbit of $\Psi_p(x)$ under $\overline{\mathbf{P}}_p$, and hence that of the orbit of $x$ under $\mathbf{P}_p$. For instance, a complete description of the orbit of $108$ under $\mathbf{P}_2$,
$$108\mapsto 44\mapsto 12\mapsto 4\mapsto 2\mapsto 1,$$
can be obtained from the fact that $\Psi_2(108)=\left(0,0,1,1,0,1,1,\overline{0}\right)$ and, under $\overline{\mathbf{P}}_2$,
$$\left(0,0,1,1,0,1,1,\overline{0}\right)\mapsto \left(0,0,1,1,0,1,\overline{0}\right)\mapsto \left(0,0,1,1,\overline{0}\right)\mapsto \left(0,0,1,\overline{0}\right)\mapsto \left(0,1,\overline{0}\right)\mapsto \left(1,\overline{0}\right).$$

Now, let $\alpha=\left(a_k,\ldots,a_0\right)$. Based on the definitions of the analogues under $\mathbf{P}_p$, the \textbf{transient length}, \textbf{limit}, \textbf{settling time}, and \textbf{attractor} of $\alpha$ under $\overline{\mathbf{P}}_p$ are
\begin{eqnarray*}
\overline{\rT}_p(\alpha)&=&\min\bigl\{n\in\mathbb{N}:\text{only the first term of }\alpha_n\text{ is non-zero}\bigr\},\\
\overline{\rL}_p(\alpha)&=&\alpha_{\overline{\rT}_p(\alpha)},\\
\overline{\rS}_p(\alpha)&=&\min\bigl\{n\in\mathbb{N}:
\alpha_n\in\bigl\{ \bigl( \underbrace{0,0,\ldots,0}_t,1,\overline{0}\bigr):t\in\mathbb{N}_0\bigr\}\cup
\bigl\{\bigl(1,\overline{0}\bigr),\ldots,\bigl(p-1,\overline{0}\bigr)\bigr\}\bigr\},\\
\overline{\rA}_p(\alpha)&=&\alpha_{\overline{\rS}_p(\alpha)},
\end{eqnarray*}
respectively, where $\left(\alpha_n\right)_{n=1}^\infty$ is the orbit of $\alpha$ under $\overline{\mathbf{P}}_p$, which is determined by
$$\alpha_1=\alpha\qquad\quad\text{and}\quad\qquad\alpha_{n+1}=\overline{\mathbf{P}}_p\left(\alpha_n\right)\quad\text{for every }n\in\mathbb{N}.$$\smallskip

\paragraph{\textit{Proof of Theorem \ref{thm:Fr}}} Proving Theorem \ref{thm:Fr} is equivalent to proving that
\begin{eqnarray*}
\overline{\rT}_p(\alpha)&=&
\begin{cases}
\nu_p\left({\Psi_p}^{-1}(\alpha)\right)+a_k+\cdots+a_1&\text{if }a_0=0,\\
1+a_k+\cdots+a_1&\text{if }a_0\geqslant 1,
\end{cases}\\
\overline{\rL}_p(\alpha)&=&\begin{cases}
\left(1,\overline{0}\right)&\text{if }a_0=0,\\
\left(a_0,\overline{0}\right)&\text{if }a_0\geqslant 1,
\end{cases}\\
\overline{\rS}_p(\alpha)&=&\begin{cases}
a_k+\cdots+a_1&\text{if }a_0=0,\\
1+a_k+\cdots+a_1&\text{if }a_0\geqslant 1,
\end{cases}\\
\overline{\rA}_p(\alpha)&=&\begin{cases}
\bigl( \underbrace{0,0,\ldots,0}_{\nu_p\left({\Psi_p}^{-1}(\alpha)\right)},1,\overline{0}\bigr)&\text{if }a_0=0,\\
\left(a_0,\overline{0}\right)&\text{if }a_0\geqslant 1.
\end{cases}
\end{eqnarray*}
We consider each of the two cases.\bigskip

\noindent\underline{\textsc{Case I}}: $a_0\geqslant 1$. If $k=0$, then the orbit of $\alpha=\left(a_0,\overline{0}\right)$ is constant, so $\overline{\rL}_p(\alpha)=\overline{\rA}_p(\alpha)=\left(a_0,\overline{0}\right)$ and $\overline{\rT}_p(\alpha)=\overline{\rS}_p(\alpha)=1$, obeying the desired formulae. Now suppose $k\geqslant 1$. Since $a_0\geqslant 1$, then each iteration is prescribed by the last branch in \eqref{eq:transmap}. Since
$$\alpha_1=\left(a_0,\ldots,a_k,\overline{0}\right),$$
then
$$\alpha_{1+a_k}={\overline{\mathbf{P}}_p}^{a_k}\left(\alpha_1\right)=\left(a_0,\ldots,a_{k-1},\overline{0}\right).$$
Continuing this, we have, for every $j\in\{k-1,\ldots,1\}$,
$$\alpha_{1+a_k+\cdots+a_j}={\overline{\mathbf{P}}_p}^{a_{j}}\left(\alpha_{1+a_k+\cdots+a_{j+1}}\right)=\left(a_0,\ldots,a_{j-1},\overline{0}\right),$$
which means that
$$\overline{\rT}_p(\alpha)=\overline{\rS}_p(\alpha)=1+a_k+\cdots+a_1\qquad\text{and}\qquad\overline{\rL}_p(\alpha)=\overline{\rA}_p(\alpha)=\left(a_0,\overline{0}\right),$$
as desired.\bigskip

\noindent\underline{\textsc{Case II}}: $a_0=0$. In this case, $k\geqslant 1$. Let $t:=\nu_p\left({\Psi_p}^{-1}(\alpha)\right)$, then $a_0=\cdots=a_{t-1}=0$ and $a_t\geqslant 1$, so
$$\alpha_1=\bigl( \underbrace{0,\ldots,0}_t,a_t,\ldots,a_k,\overline{0}\bigr).$$
By the last branch in \eqref{eq:transmap}, we have
$$\alpha_{1+a_k}={\overline{\mathbf{P}}_p}^{a_k}\left(\alpha_1\right)=\bigl( \underbrace{0,\ldots,0}_t,a_t,\ldots,a_{k-1},\overline{0}\bigr),$$
and, for every $j\in\{k-1,\ldots,t+1\}$,
$$\alpha_{1+a_k+\cdots+a_{j}}={\overline{\mathbf{P}}_p}^{a_{j}}\left(\alpha_{1+a_k+\cdots+a_{j+1}}\right)=\bigl( \underbrace{0,\ldots,0}_{t},a_t,\ldots,a_{j-1},\overline{0}\bigr).$$
Next,
$$\alpha_{a_k+\cdots+a_t}={\overline{\mathbf{P}}_p}^{a_{t}-1}\left(\alpha_{1+a_k+\cdots+a_{t+1}}\right)=\bigl( \underbrace{0,\ldots,0}_t,1,\overline{0}\bigr).$$
At this point we have proved that
$$\overline{\rS}_p(\alpha)=a_k+\cdots+a_1\qquad\text{and}\qquad\overline{\rA}_p(\alpha)=\bigl( \underbrace{0,\ldots,0}_t,1,\overline{0}\bigr)=\bigl( \underbrace{0,0,\ldots,0}_{\nu_p\left({\Psi_p}^{-1}(\alpha)\right)},1,\overline{0}\bigr).$$
Finally, the dynamics concludes with $t$ iterations prescribed by the second branch in \eqref{eq:transmap}:
$$\alpha_{a_k+\cdots+a_t+t}={\overline{\mathbf{P}}_p}^t\left(\alpha_{a_k+\cdots+a_t}\right)=\left(1,\overline{0}\right).$$
Therefore,
$$\overline{\rT}_p(\alpha)=t+a_k+\cdots+a_1=\nu_p\left({\Psi_k}^{-1}(\alpha)\right)+a_k+\cdots+a_1\qquad\text{and}\qquad\overline{\rL}_p(\alpha)=\left(1,\overline{0}\right),$$
as desired.\hfill$\square$\bigskip

\subsection{A comparison of $\mathbf{P}_p$ and $\mathbf{P}$}

Let $p\in\mathbb{P}$. For every $x\in\mathbb{N}$, let
$$\hat{\rT}_p(x):=\frac{1}{x}\sum_{t=1}^x \rT_p(t)\qquad\quad\text{and}\quad\qquad \hat{\rS}_p(x):=\frac{1}{x}\sum_{t=1}^x \rS_p(t)$$
be the $x$-th Ces\'aro mean of the sequences $\left(\rT_p(x)\right)_{x=1}^\infty$ and $\left(\rS_p(x)\right)_{x=1}^\infty$, respectively. From Theorem \ref{thm:Fr}, noticing that
$$\frac{\bigl|\{t\leqslant x:p\mid t\}\bigr|}{x}=\frac{1}{x}\left\lfloor\frac{x}{p}\right\rfloor\sim\frac{1}{p}$$
and
$$\frac{1}{x}\sum_{t=1}^x \nu_p(t)=\frac{1}{x}\sum_{t=1}^{\left\lfloor\log_p x\right\rfloor}\left\lfloor\frac{x}{p^t}\right\rfloor\sim\sum_{t=1}^{\left\lfloor\log_p x\right\rfloor}\frac{1}{p^t}\sim\frac{1}{p-1}$$
and applying \cite[Theorem 1]{Bush},
$$\frac{1}{x}\sum_{t=1}^x\mathcal{S}_p(t)\sim \frac{(p-1)\ln x}{2\ln p},$$
one proves the following corollary.\bigskip

\begin{corollary}\label{corollary}
We have
$$\hat{\rT}_p(x)\sim\hat{\rS}_p(x)\sim \frac{(p-1)\ln x}{2\ln p}.$$
\end{corollary}\bigskip

\begin{figure}
\centering
\input{fig-TSasymptotics}
\caption{\label{fig:TSasymptotics}\small
Plots of $\hat{\rT}(x)$ and $\hat{\rT}_2(x)$ versus $\ln x$ (left) and $\hat{\rS}(x)$ and $\hat{\rS}_2(x)$ versus $\ln x$ (right) for $x\in\left\{1,\ldots,1\cdot 10^4\right\}$.}
\end{figure}

Thus, the growths of $\hat{\rT}_p(x)$ and $\hat{\rS}_p(x)$ with $x$ are both logarithmic. By contrast, letting
$$\hat{\rT}(x):=\frac{1}{x}\sum_{t=1}^x \rT(t)\qquad\quad\text{and}\quad\qquad \hat{\rS}(x):=\frac{1}{x}\sum_{t=1}^x \rS(t),$$
from Theorems \ref{thm:power2} and \ref{thm:orderS(x)} we know that the former grows at most logarithmically, and the latter at most double-logarithmically. In fact, Figure \ref{fig:TSasymptotics} suggests that both quantities grow at most double-logarithmically. This is confirmed by Figure \ref{fig:TSasymptotics2} which suggests the existence of $\lambda\geqslant 1$ such that
\begin{equation}\label{eq:TsimS}
\frac{\hat{\rT}(x)}{\hat{\rS}(x)}\sim\lambda.
\end{equation}

\begin{figure}
\centering
\input{fig-TSasymptotics2}
\caption{\label{fig:TSasymptotics2}\small
Plot of $\hat{\rT}(x)$ versus $\hat{\rS}(x)$ for $x\in\left\{1,\ldots,1\cdot 10^5\right\}$.}
\end{figure}

Now, since
\begin{eqnarray*}
\left(\hat{\rT}-\hat{\rS}\right)(x)&=&\frac{1}{x}\sum_{t=1}^x(\rT-\rS)(t)\\
&=&\frac{1}{x}\sum_{u=0}^{\max\limits_{1\leqslant t\leqslant x}(\rT-\rS)(t)}u\,\left|(\rT-\rS)^{-1}(\{u\})\cap\{1,\ldots,x\}\right|\\
&=&\sum_{u=1}^{\max\limits_{1\leqslant t\leqslant x}(\rT-\rS)(t)} u\,\mathbf{d}_x(\rT-\rS)^{-1}(\{u\}),
\end{eqnarray*}
then we have $$\left(\hat{\rT}-\hat{\rS}\right)(x)\xrightarrow{x\to\infty}0\qquad\text{if}\qquad \mathbf{d}_x(\rT-\rS)^{-1}(\{u\})\xrightarrow{x\to\infty}0\quad\text{for every }u\in\mathbb{N}.$$
The latter holds if and only if the set $(\rT-\rS)^{-1}\left(\mathbb{N}\right)=\rA^{-1}\left(\mathbb{N}_{\geqslant 2}\right)$ is sparse. Indeed, an extensive set of values of $\mathbf{d}_x\rA^{-1}\left(\mathbb{N}_{\geqslant 2}\right)$ suggests that this quantity decays algebraically to zero as $x\to\infty$ (Figure \ref{fig:melaluiprimepower}), leading to the following conjecture.\bigskip

\begin{figure}
\centering
\input{fig-melaluiprimepower}
\caption{\label{fig:melaluiprimepower}\small
Plot of $\mathbf{d}_x\rA^{-1}\left(\mathbb{N}_{\geqslant 2}\right)$ versus $x$ for $x\in\{5\cdot10^4,\ldots,1\cdot 10^6\}$ in log-log scale (left) together with the least-squares line determined using its values for $x\in\{6\cdot 10^5,\ldots,1\cdot 10^6\}$ which has slope $\alpha\approx -0.006$ and ordinate intercept $\beta\approx -0.243$, and in linear-linear scale (right) together with the curve $e^{\beta}x^\alpha$.}
\end{figure}

\begin{samepage}
\begin{conjecture}\label{finalconjecture}
There exists a function $\Phi(x)=cx^\alpha$, where $c\in(0,1)$ and $\alpha\in\left(-10^{-2},-10^{-3}\right)$, such that
$$\left|\mathbf{d}_x\rA^{-1}\left(\mathbb{N}_{\geqslant2}\right) - \Phi(x)\right|=o\left(\Phi(x)\right).$$
In particular, almost every orbit of $\mathbf{P}$ contains no prime-power.
\end{conjecture}\bigskip
\end{samepage}

\noindent Notice that if this conjecture holds, then so does \eqref{eq:TsimS} with $\lambda=1$.\bigskip