Given that the function $$$f$$$ satisfies $$$f (1)=1 $$$, and for $$$n\ge 2$$$,

where $$$\varphi$$$ is Euler totient function.

You can find this sequence on OEIS.

The first 10 items of $$$f$$$ are: $$$1,1,2,3,4,6,6,9,10,12$$$.

The question is that how to find $$$f(1),f(2),\cdots,f(n)$$$ in $$$\mathcal O(n\log \log n)$$$ time.

I think this is a quite interesting problem, you can think for a while before see the solution below.

A wrong approach is assuming that $$$f$$$ is a multiplicative function, and trying to find $$$f(p),f(p^2),\cdots$$$ for every prime $$$p$$$.

Because from the example above, $$$f(6)=6\neq 1\times 2=f(2)\times f(3)$$$. The relaxed multiplication eliminates the multiplicative property.

Now here is the algorithm I found to solve this problem.

Firstly, we can rewrite this recursive formula as the DGF (Dirichlet Generating Function) form, that is

where $$$\tilde f$$$ stands for the DGF of $$$f$$$.

According to the Newton's method of DGF (I do not intend to elaborate on its principle here), if the first $$$\sqrt n$$$ items of $$$\tilde {f_0}$$$ are correct, we can find $$$f$$$ whose first $$$n$$$ items are correct through the following iterative formula.

In this formula, the time complexity for calculating $$$\tilde {f_0} ^ 2$$$ brutely is $$$\mathcal O(n) $$$, and the time complexity for multiplying by $$$2-\tilde \varphi$$$ is $$$\mathcal O(n \log \log n) $$$. As for $$$\tilde {f_0}$$$, we can directly calculate it through the definition in $$$\mathcal O(\sqrt n\log n)$$$ time.

In summary, we have an algorithm for calculating $$$f(1),f(2),\cdots,f(n)$$$ in $$$\mathcal O(n\log \log n)$$$ time, which is unexpected.