Two new blog posts by Brent Yorgey concern the Euler totient function: https://mathlesstraveled.com/2019/05/09/computing-the-euler-totient-function-part-1/ and https://mathlesstraveled.com/2019/05/18/computing-the-euler-totient-function-part-2-seeing-phi-is-multiplicative/
Computing it quickly would break RSA; Brent describes using factoring to do better than brute force. The problem is clearly in #P. I recently visited UCLA where Igor Pak asked me for natural candidates of #P-intermediate problems. I think this is one, and Igor thinks the prime-counting function is another, but neither is very combinatorial. Anyone have better candidates?