修正：$\varphi^*(0)=0,\varphi^*(1)=1$
by fast_proton @ 2024-03-18 23:30:09
$\varphi^*$ = [A049108](https://oeis.org/A049108) = [A003434](https://oeis.org/A003434) - 1
后者满足 $\log_3(\frac{n}{2})+1\le a_n\le \log_2n+1$
by rui_er @ 2024-03-18 23:38:19
@[fast_proton](/user/302805)
by rui_er @ 2024-03-18 23:38:26
写错了，A049108 = A003434 + 1
by rui_er @ 2024-03-18 23:39:02
就是一个数取欧拉函数值，迭代多少次归 1 的问题
考虑当 n 为偶数时，phi(n) 中肯定会比 n 少一个 2 的因子，相当于至少减半
当 n 为奇数时，phi(n) 是偶数，转化到上一种情况
所以大致为 log n
扩展欧拉定理降幂的题常用到这个性质
by Iniaugoty @ 2024-03-18 23:52:57
@[fast_proton](/user/302805)
这个资料对你有帮助吗？
by 小粉兔 @ 2024-03-19 04:01:57
P3934 那种东西吗
by lonely_seele @ 2024-03-19 09:01:59
@[fast_proton](/user/302805) 兄弟为啥不回复
by 小粉兔 @ 2024-03-19 23:28:32
@[小粉兔](/user/10703) 很有帮助。兔/se
by fast_proton @ 2024-03-20 17:22:44