What are the largest values terminate the fastest in this sequence?

Question

If we have any integer $N$ greater than $1$, $$N=\prod_{n=1}^bP_n^{a_n}$$ where $P_i$ is prime and $P_i<P_{(i+1)}$, let$$F(N)=\prod_{n=1}^b(P_n^{a_n}-1)$$ Repeat $F$ until the sequence terminates, i.e. reaches $1$. We know that it will terminate since $F(N)<N$.

Is there a maximum value $N$ that will terminate in a given $a$ moves? For instance $2\to 1$, so that would be $1$ move. No other number terminates in $1$ move. Is there a cap for every number of moves? It seems that the answer is yes, but I'm not sure exactly why. I think it has to do with the fact that only finitely many integers will return any given integer.

Answer 1

Let's fix $N$ and therefore $b$, the $P_i$ and the $a_i$. Then for each $i$,

$$\begin{eqnarray} P_i && \geq && i+1 \\ \therefore P_i^{a_i} && \geq && i+1 \\ \therefore 1-\frac{1}{P_i^{a_i}} && \geq && 1-\frac{1}{i+1} \\ \therefore \frac{P_i^{a_i}-1}{P_i^{a_i}} && \geq && \frac{i}{i+1} \end{eqnarray}$$

Taking the product from $i=1$ to $i=b$,

$$\frac{F(N)}{N} \geq \frac{1}{b+1}$$

$N$ is at least $(b+1)!$. Therefore $b+1$ is at most the inverse factorial of $N$. Therefore the inverse factorial of $F(N)$ is less than the inverse factorial of $N$ by at most 1. By induction, any $N$ larger than $(b+1)!$ takes at least $b$ moves.

Answer 2

It holds that $F(N) > \sqrt{N}$ for $N > 6$. We need to compare the factors in the products $$F(N) = \prod (p_n^{a_n} - 1) \quad \text{and} \quad \sqrt{N} = \prod p_n^{a_n/2}.$$ Indeed, suppose we wanted $N$ to satisfy $F(N) \le \sqrt{N}$. The only natural number $m = p_n^{a_n}$ for which $m - 1 \le \sqrt{m}$ is $m = 2^1$, and the ratio of these quantities in this case is $1/\sqrt{2}$. For $m = 3$, the ratio is $2/\sqrt{3}$; for $m \ge 4$, it's at least $3/2$.

So if $N$ is divisible by a prime power at least 4, then the ratio $F(N)/\sqrt{N}$ is better than $3/2 \cdot 1/\sqrt{2} > 1$. In particular, this is true for $N > 6$.

Now fix $a \ge 1$. If $N > 2^{2^{a+2}}$, then by iterating the inequality $F(N) > \sqrt{N}$ you get $F^a(N) > 2^{2^2}$. Thus there is a cap on numbers terminating after $a$ steps.

Answer 3

Alternative method: $F(N) \ge \varphi(N)$ and it's well known that $\varphi(N)/N^{1-\varepsilon}$ goes to infinity for any $\varepsilon > 0$; see Wikipedia. Here $\varphi$ is Euler's totient function.