I would like to check if this limit :$$\liminf \frac{\sigma_{k}(({2}^{m-1})({2^m-1}))}{\phi_{k}(({2}^{m-1})({2^m-1}))}$$ finite for every $k$?

where :$\phi_{k}$ is iterating Euler - totient function and $\sigma_{k}$ is iterating sum divisor .

note(01) : Here :$\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of divisors function. and :$\phi_{k}(n)=\phi(\phi(\phi(\dots n)))$ is the $k$-th iterate of the euler totiont function.

Note(02) :I tried to evaluate the recent limit I accrossed this problem :can I write :$${\phi_{k}(({2}^{m-1})({2^m-1}))}=({2}^{m-1-k})\phi_{k}({2^m-1})$$ ? I know only that is true iff gcd $({2}^{m-1},{2^m-1})=1$ for $m\geq 1$ and $k=1$ ?

Thank you for any help

  • 2
    $\begingroup$ For all $m\geq 1$ we have $gcd(2^{m-1},2^m-1)=1$. $\endgroup$ Commented Dec 29, 2015 at 11:39
  • $\begingroup$ and it is the same for what i wrote but what about more iteration of k ? $\endgroup$ Commented Dec 29, 2015 at 11:40
  • $\begingroup$ The "proof theory" tag should be reserved to (certain) questions in mathematical logic, namely those which concern formal proofs and their theory. $\endgroup$
    – GH from MO
    Commented Dec 29, 2015 at 16:36
  • $\begingroup$ Personally, I think this question is beyond current technology. $\endgroup$
    – GH from MO
    Commented Dec 29, 2015 at 18:37
  • $\begingroup$ in note(02) , just i would like to write my limit in other form for using shinzel and sieve conjecture using simplification which montioned in note 2 " using property of multiplicative function and i asked also in this note if it is true for all m, and k ? $\endgroup$ Commented Dec 29, 2015 at 22:04

2 Answers 2


The problem is probably beyond current knowledge. It is well possible that $\liminf\omega(2^m-1)=\infty$, where $\omega(n)$ denotes the number of distinct prime divisors of $n$. If this was the case, one could expect that for each small prime $p$ there is some $m_0$, such that for $m>m_0$ we have that $2^m-1$ has a prime divisor $q\equiv 1\pmod{p}$. If this was the case, then $\frac{\varphi(\varphi(2^m-1))}{2^m-1}\rightarrow 0$, thus for $k=2$ the $\liminf$ in question would be infinite.

Excluding these possibilities is probably not much easier then proving that there are infinitely many Mersenne primes, which is certainly difficult.


For $k=1$ and $m$ a not too small prime, there are fewer than $f=m/(\log_2 m)$ prime factors of $2^m-1$, all of them at least as large as $m$, and your ratio is $O((m/(m-2))^f)$, which is bounded, so the answer is yes the lim inf is finite for $k=1$.

For $k \gt 1$ fixed, we have no nice estimates on the number or size of distinct prime factors of either numerator or denominator of your fraction, and at present we don't have a good understanding of the dynamics of the $\sigma$ or the $\phi$ functions to give a good guess. I am looking at a concept with the working title "factoral abundance" to address questions like this. Getting some help with the estimates raised in How to get a good upper bound on $\sum_{1 \lt d, d|n} \phi(d)/\log d$? would push us nearer to such answers.

Gerhard "And Help On Other Questions" Paseman, 2015.12.29

  • $\begingroup$ A good start would be analyzing the numerics for k=1: what is the shape of the point cloud for (m, ratio(m)) for the first million m? It is not clear to me that lim sup of the ratio is unbounded for arbitrary m. Similarly for k=2 and 3. Gerhard "See If WolframAlpha Eats It" Paseman, 2015.12.29 $\endgroup$ Commented Dec 29, 2015 at 21:30
  • $\begingroup$ @Gerahrd paseman, my point of starting to proof this problem in "note (02) in the question $\endgroup$ Commented Dec 29, 2015 at 21:43
  • $\begingroup$ I think the equation in that note fails for many values of m and k. Can you tell for k=2 or 3 some m for which it holds? Gerhard "Really, Try Some Small Examples" Paseman, 2015.12.29 $\endgroup$ Commented Dec 29, 2015 at 21:48
  • $\begingroup$ I don't know , it's seems to poste a new question here to know for which values it hold $\endgroup$ Commented Dec 30, 2015 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.