Prove that $\sigma(n)\le \lceil\log_2(n)\rceil$

Question

Let $f:\mathbb{N}\to\mathbb{N}$ be defined as $f(1)=1$ and if $n=\prod_{r=1}^{k}p_r^{\alpha_r}$ is the prime decomposition of $n$ then: $$ f\left(n\right)=\prod_{r=1}^{k}(p_r-1)^{\alpha_r} $$ Let $\sigma:\mathbb{N}\to\mathbb{N}$ be defined as the function which associates each number with the number of iterations of $f$ it takes until we reach $1$, i.e: $$ f^{(\sigma(n)-1)}(n)\neq 1\\ f^{(\sigma(n))}(n)= 1 $$ Prove that $\sigma(n)\le \lceil\log_2(n)\rceil$.

I actually have no idea how to solve this, so any help would be greatly appreciated.

Answer 1

Hint. Look what happens to the size of the prime divisors of a number when applying $f$.

In general, the largest prime divisor of a composite number $m$ is at most $\frac m2$. Consequently, if $p\neq3$ is prime, then the largest prime divisor of $p-1$ is at most $\frac p2$.
If all prime divisors $p\mid n$ are $\leq q$ (for some $q\geq4$), then the largest prime divisor of $f(n)$ is at most $\frac q2$. So the largest prime divisor of $f^{(k)}(n)$ is at most $\frac q{2^k}$, if $\frac q{2^{k-1}}\geq4$. Because $q\leq n$, this is $\leq\frac n{2^k}$. So as soon as $\frac n{2^k}\leq2$, $f^{(k)}(n)$ must be a power of $2$, and then $f^{(k+1)}(n)=1$. Hence $\sigma(n)\leq\lceil\log_2n\rceil$.

Answer 2

First assume that $n$ is a prime and write $n$ as a binary number $n_{(2)}$. We can verify that $\sigma(n)$ equals the number of 1 in $n_{(2)}$, which is no more than $⌈\log_2(n)⌉$.

Furthermore,we can also see that for non-prime $n$, $f^{(m)}(n)=\prod_{r=1}^k f^{(m)}(p_r)^{a_r}$ and hence $\sigma(n)=\max_{p\mid n}\sigma(p)$, where $p$ is a prime factor of $n$. Using the result above, we can reach the conclusion of OP.