Given that the function $f$ satisfies $f (1)=1 $, and for $n\ge 2$, ↵
↵
$$\displaystyle f(n)=\sum_{d|n,d<n}^{}f(d)\varphi(n/d)$$↵
↵
where $\varphi$ is Euler totient function.↵
↵
You can find this sequence on [OEIS](https://oeis.org/A006874).↵
↵
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 ↵
↵
$$\displaystyle \tilde f=\frac 1{2-\tilde \varphi}$$↵
↵
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.↵
↵
$$\displaystyle \tilde f\leftarrow 2\tilde {f_0}-(2-\tilde \varphi)\tilde {f_0}^2$$↵
↵
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.↵
↵
↵
$$\displaystyle f(n)=\sum_{d|n,d<n}^{}f(d)\varphi(n/d)$$↵
↵
where $\varphi$ is Euler totient function.↵
↵
You can find this sequence on [OEIS](https://oeis.org/A006874).↵
↵
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 ↵
↵
$$\displaystyle \tilde f=\frac 1{2-\tilde \varphi}$$↵
↵
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.↵
↵
$$\displaystyle \tilde f\leftarrow 2\tilde {f_0}-(2-\tilde \varphi)\tilde {f_0}^2$$↵
↵
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.↵
↵
