wakanda-forever's blog

Finding an upperbound for the minimum number of iterations on the Euler Totient Function
By wakanda-forever, 5 weeks ago, In English

Hello everyone. This is my first blog on codeforces.

Coming to the topic, consider the task where you are given an integer $$$n$$$ and you are asked to find the minimum value of $$$k$$$ such that $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$ (where $$$\phi$$$ is applied $$$k$$$ times on $$$n$$$ in a nested manner and $$$\phi$$$ is the euler totient function). This task can be solved, but for now let's only focus on finding an upperbound for $$$k$$$.

We have,

$$$ \phi(n) = n \cdot (1-\frac{1}{p_1}) \cdot (1-\frac{1}{p_2}) .... (1-\frac{1}{p_m}) $$$

where $$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... p_m^{a_m}$$$ and $$$p_1,p_2...,p_m$$$ are prime factors of $$$n$$$. Proof can be found here.

Now, if $$$n$$$ is even, $$$2$$$ is a prime factor of $$$n$$$ so $$$\phi(n)$$$ $$$\le$$$ $$$\frac{n}{2}$$$ and if $$$n$$$ is odd and $$$n>1$$$, $$$\phi(n) < n$$$ and $$$\phi(n)$$$ is even. So we can safely say that $$$\phi(\phi(n)) \le \frac{n}{2}$$$ for all $$$n>1$$$. Repeating this process, it is obvious that after applying $$$\phi$$$ for $$$2 \cdot \lceil \log_2(n) \rceil$$$ times on $$$n$$$, we have $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$. So we have $$$k \le 2 \cdot \lceil \log_2(n) \rceil$$$.

We can find an even tighter bound using the fact that $$$\phi(n)$$$ is even for all $$$n \ge 3$$$. So for any $$$n \ge 3$$$, $$$\phi(n)$$$ is even and $$$\phi(\phi(n)) \le \frac{n}{2}$$$, $$$\phi(\phi(\phi(n))) \le \frac{n}{4}$$$, $$$\phi(\phi(\phi(\phi(n)))) \le \frac{n}{8}$$$ and so on. Thus after applying $$$\phi$$$ for $$$\lceil \log_2(n) \rceil$$$ times on $$$n$$$, we have $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$. So we have $$$k \le \lceil \log_2(n) \rceil$$$.

I hope atleast someone finds this interesting.

  • Vote: I like it
  • +37
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

If you count for each $$$k \geq 1$$$ the number of integers $$$n$$$ such that $$$k = \lceil log_2(n) \rceil$$$, the sequence generated would be $$$1, 1, 2, 3, 5, 7, 13, 16, 24, 33, 47, 60...$$$. Such numbers $$$n$$$ are all odd and mostly prime (probably for obvious reasons, that's how $$$\phi$$$ works). Searching the sequence above up on OEIS returned one 1-1 match which was very interesting to me until I looked at the definition of the sequence (it was created specifically because of this problem). Still, interesting blog, and made me remember my number theory.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

In fact, the base of the logarithm can be improved to 3. See here.

Edit: sorry, misread the post. The linked problem is about a lower bound for $$$k$$$, this is about an upper bound.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks for sharing this.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    That link says that the base is 3 for the lower bound, while this blog is about an upper bound. $$$3^k$$$ takes $$$k+1$$$ iterations to reach 1, and $$$2^k$$$ takes $$$k$$$, so neither of the bases can be improved.

    → Reply