Fly37510's blog

By Fly37510, history, 9 hours ago, In English

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.

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.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Fly37510 (previous revision, new revision, compare).