andr1y's blog

Proof of task Clown Fiesta
By andr1y, history, 4 years ago, In English

Hello Codeforces, recently, there was a contest on CSAcademy named "FiiCode 2021 Round 2" and there was a task "Clown Fiesta", in a editorial for the task, there were lines such like:

If we take a sequence, where $$$a_0 = m$$$, $$$a_1 = \varphi (a_0)$$$, $$$a_2 = \varphi (a_1)$$$, $$$...$$$, $$$a_{k-1} = \varphi (a_{k-2}) \neq 1$$$, $$$a_k = \varphi (a_{k-1}) = 1$$$ and $$$m$$$ is prime number less than $$$10^9$$$, then $$$k$$$ will be not greater than $$$log_2(m)$$$.

Can someone prove it?

P.S. link to problem.

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

»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

A not formal proof.

If x is odd, phi(x) is even

If x is even, phi(x) <= x/2

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    got it, thanks)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    This proofs, that $$$k \leq 2 * log_2(m)$$$. Actually we can proof, that $$$k \leq log_2(m) + 1$$$, because $$$\varphi(x)$$$ is even for all $$$x > 2$$$.

    Proof: If $$$gcd(n, x) = 1$$$, then $$$gcd(n, n - x) = 1$$$ too, and if $$$n$$$ is even and $$$n > 2$$$, then $$$gcd(n, \frac{n}{2}) \neq 1$$$, so all numbers coprime with $$$n$$$ are splited in pairs.

    → Reply