Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Proof of task Clown Fiesta

Revision en3, by andr1y, 2021-05-08 17:16:48

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 a0=m, a1=φ(a0), a2=φ(a1), ..., ak=1 and m is prime number less than 109, then k will be not greater than log2(m).

Can someone prove it?

P.S link to problem.

Tags math, proof, csacademy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English andr1y 2021-05-08 17:21:48 34
en6 English andr1y 2021-05-08 17:20:29 38 Tiny change: '$...$, $a_k = ' -> '$...$, $a_{k-1} = \varphi (a_{k-2}) \neq 1$, $a_k = '
en5 English andr1y 2021-05-08 17:19:02 20 Tiny change: '$, $a_k = 1$ and ' -> '$, $a_k = \varphi (a_{k-1}) = 1$ and '
en4 English andr1y 2021-05-08 17:17:41 1 Tiny change: 'it?\n\nP.S [link](ht' -> 'it?\n\nP.S. [link](ht' (published)
en3 English andr1y 2021-05-08 17:16:48 112
en2 English andr1y 2021-05-08 17:15:57 5 Tiny change: ' than $log m$. Can som' -> ' than $log_2(m)$. Can som'
en1 English andr1y 2021-05-08 17:14:44 422 Initial revision (saved to drafts)