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.
Auto comment: topic has been updated by Fly37510 (previous revision, new revision, compare).