As in another question, let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise} \end{cases}$$

where $\phi(N)$ is Euler's totient function.

Tasse kindly reasoned that we can write

$$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3$$

I can't at all see why this is true. How is this equation derived? I do understand his proof that $\phi(\phi(N)) < N/2$.


Here's the relevant part of the proof, quoting verbatim:

First, show that $\phi(\phi(n)) < n/2$. This can be done as such:

Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$)

  • Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) < n/2$.
  • Suppose $n$ is odd and $n > 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) < n/2$.

So we get the desired result.

This lemma is slightly mis-stated, because when $n=2$, $\phi(\phi(n)) = n/2$. But it doesn't invalidate the main result. We will state the lemma as:

Lemma For all $n \ge 2$, $\phi(\phi(n)) \le \frac{n}{2}$.

Tasse's proof sketch is a proof by induction in disguise, but this may not have been obvious to you. I'm going to simplify the proof sketch a little bit and lay it out more like a proper proof by induction.

Proof By induction on $n$.

Base case: If $n=2$, see above.

Inductive step: Suppose that for all $2 \le m < n$, $\phi(\phi(m)) \le \frac{m}{2}$. We want to prove that $\phi(\phi(n)) \le \frac{n}{2}$.

Case 1: Suppose $n$ is even, that is, $n = 2q$ for some $q$. In this case, the multiplicative property of the totient function says that $\phi(2q) = \phi(2) \phi(q) = \phi(q)$.

That is, $\phi(n) = \phi(\frac{n}{2})$. However, another useful property of the totient function is that for all $m \ge 2$, $\phi(m) \le m-1$. Therefore $\phi(\phi(n)) \le \frac{n}{2} - 1$.

This proves what we wanted for this case, but we have also incidentally proven another useful thing: If $n$ is even, then $\phi(n) \le \frac{n}{2}$. This will be important in the next step.

Case 2: Suppose $n$ is odd. That is, $n = p^k q$ for some odd prime $p$, and some positive integer $k$, and some $q$ which doesn't have $p$ as a divisor. Then:

$\phi(n) = \phi(p^k) \phi(q) = \left(p^k - p^{k-1}\right) \phi(q)$.

Now there are two things you need to notice about the right-hand side.

First off, it's less than $n$. Why? Because clearly $p^k - p^{k-1} < p^k$, and it's a standard property of the totient function that $\phi(q) \le q$. (Note that this is also true if $q = 1$.)

Secondly, it's even. Why? Because if $p$ is odd, $p^k - p^{k-1}$ is even.

So by that incidental result we discovered in case 1:

$\phi(\phi(n)) = \phi(\left(p^k - p^{k-1}\right) \phi(q)) \le \frac{\left(p^k - p^{k-1}\right) \phi(q)}{2} < \frac{n}{2}$.


  • $\begingroup$ It looks like you've clarified quite a bit the result that $\phi(\phi(N)) \le N/2$, and I will dutifully review it, but the question is actually about the equation $$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3,$$ which is what I don't have any idea why it's true. If you could explain it with the level of clarity you seem to explain the lemma, that'd be really great. Thanks! $\endgroup$ – R. Chopin Oct 1 '19 at 13:15
  • 1
    $\begingroup$ Oh, sorry, I clarified the wrong part! I'll take a look tomorrow. $\endgroup$ – Pseudonym Oct 1 '19 at 13:36
  • $\begingroup$ Pseudonym, $\phi(2q) = \phi(2)\phi(q)$ provided $\gcd(2,q) = 1$, but all we have in your case 1 is that $2q$ is even; we don't know $q$ is odd, so you cannot use the multiplicative property of $\phi$. What do you say? $\endgroup$ – R. Chopin Oct 2 '19 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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