Sum of Multiplicative Function on Powerful Numbers

multiplicative function $f(n)$ に対し、$F(n) := \sum\limits_{m: \text{ powerful number}} f(m)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p^2) = g(p)$ とかけるとする。

このとき、$F(n)$ を時間計算量 $O(n^{1/3} \log{n})$、空間計算量 $O(n^{1/4})$ で求める。

Powerful Number

正の整数 $n$ は、「素数 $p$ が $n$ を割り切るならば、$p^2$ も $n$ を割り切る」という性質を満たすとき powerful number と呼ばれる。
powerful number $n$ は $n = a^2 b^3$ ($b$: squarefree) の形で一意にかけ、$n$ 以下の powerful number の個数は $\Theta(\sqrt{n})$ となる。

表記

  • $\pi(n)$: $n$ 以下の素数の個数
  • $p_i$: $i$ 番目の素数(e.g. $p_1 = 2, p_2 = 3, \dots$)
  • $P_i$: $i$ 番目の powerful number (e.g. $P_1 = 1$, $P_2 = 4$, $P_3 = 8$, $P_4 = 9$, $\dots$)
  • $\mathrm{lpf}(n) :=$ ($n$ の最小素因数) (if $n \ge 2$), $\mathrm{lpf}(1) := \infty$
  • $F_{\mathrm{prime}}^{(k)}(n) := \sum\limits_{2 \le p \le n,\,p:\,\mathrm{prime}} f(p^k)$
  • $F_k(n) := \sum_{i=1}^n [ \text{$i$ is powerful} \wedge \mathrm{lpf}(i) \ge p_k] \cdot f(i)$
  • $V(f, n) := \{ (P_i, f(P_i)) \mid 1 \le P_i \le \sqrt{n} \} \cup \{ (\lfloor{n/P_i}\rfloor, f(\lfloor{n/P_i}\rfloor)) \mid 1 \le P_i \le \sqrt{n} \}$ (便宜上の表記)
  • $V_\mathrm{sqrt}(f, n) := \{ (P_i, f(\lfloor\sqrt{P_i}\rfloor)) \mid 1 \le P_i \le \sqrt{n} \} \cup \{ (\lfloor{n/P_i}\rfloor, f(\lfloor{\sqrt{n/P_i}}\rfloor) \mid 1 \le P_i \le \sqrt{n} \}$ (便宜上の表記)
  • $V_\mathrm{cbrt}(f, n) := \{ (P_i, f(\lfloor\sqrt[3]{P_i}\rfloor)) \mid 1 \le P_i \le \sqrt{n} \} \cup \{ (\lfloor{n/P_i}\rfloor, f(\lfloor{\sqrt[3]{n/P_i}}\rfloor) \mid 1 \le P_i \le \sqrt{n} \}$ (便宜上の表記)

計算方法

以下の順で示す。

  1. $V_\mathrm{sqrt}(F_{\mathrm{prime}}^{(2)}, n)$, $V_\mathrm{cbrt}(F_{\mathrm{prime}}^{(3)}, n)$ は、$O(\sqrt[3]{n} \log{n})$ 時間で計算可能。
  2. $V_\mathrm{sqrt}(F_{\mathrm{prime}}^{(2)}, n)$, $V_\mathrm{cbrt}(F_{\mathrm{prime}}^{(3)}, n)$ を用いて、$V(F_{\pi(\sqrt[6]{n}) + 1}, n)$ は $O(\sqrt[3]{n})$ 時間で計算可能。
  3. $V(F_{\pi(\sqrt[6]{n}) + 1}, n)$ を用いて、$V(F_{\pi(\sqrt[12]{n}) + 1}, n)$ は $O(\sqrt[3]{n})$ 時間で計算可能。
  4. $V(F_{\pi(\sqrt[12]{n}) + 1}, n)$ を用いて、$V(F_{1}, n)$ は $O(\sqrt[3]{n})$ 時間で計算可能。

$V_\mathrm{sqrt}(F_\mathrm{prime}^{(2)}, n)$, $V_\mathrm{cbrt}(F_{\mathrm{prime}}^{(3)}, n)$ の計算

前記事の $O(n^{2/3})$ アルゴリズムを $\sqrt{n/b^3}$ ($b = 1, \dots, \lfloor\sqrt[3]{n}\rfloor$, $b$: square free) に対して適用すれば、$V_\mathrm{sqrt}(F_{\mathrm{prime}}^{(2)}, n)$ が得られる。 時間計算量は $O\left(\sum\limits_{b=1}^{\sqrt[3]{n}}\left(\sqrt{n/b^3}\right)^{2/3}\right) = O(\sqrt[3]{n} \log(n))$ となる。
(この計算量は改善できるような気がする。)

また、$V_\mathrm{cbrt}(F_{\mathrm{prime}}^{(3)}, n)$ は Eratosthenes の篩を用いて $O(\sqrt[3]{n} \log(\log(n))$ で計算できる。
($f(p^3)$ が $p$ の多項式でかける場合、この計算量もおそらく改善できる。)

$V(F_{\pi(\sqrt[6]{n}) + 1}, n)$ の計算

$q := p_{\pi(\sqrt[6]{n}) + 1}$ とする。

このとき、$F_{\pi(\sqrt[6]{n})+1}(m)$ の値は、$m$ の範囲によって以下のように計算できる:

  • $q^4 \le m \le n$ の場合: $$ \begin{aligned}F_{\pi(\sqrt[6]{n})+1}(m) &:= 1 \\ &+ (F_\mathrm{prime}^{(2)}(\lfloor \sqrt{m} \rfloor) - F_{\mathrm{prime}}^{(2)}(q-1)) \\ &+ (F_{\mathrm{prime}}^{(3)}(\lfloor \sqrt[3]{m} \rfloor) - F_{\mathrm{prime}}^{(3)}(q-1)) \\ &+ \sum_{q \le p \le \sqrt[4]{m}} \left(f(p^4) + f(p^2) \cdot \left(F_{\mathrm{prime}}^{(2)} \left(\sqrt{m/p^2}\right) - F_{\mathrm{prime}}^{(2)}\left(p\right) \right) \right) \\ &+ \sum_{q \le p \le \sqrt[5]{m}} \left(f(p^5) + f(p^2) \cdot \left(F_{\mathrm{prime}}^{(3)} \left(\sqrt[3]{m/p^2}\right) - F_{\mathrm{prime}}^{(3)}\left(p\right) \right) + f(p^3) \cdot \left( F_{\mathrm{prime}}^{(2)} \left(\sqrt{m/p^3}\right) - F_{\mathrm{prime}}^{(2)}(p) \right) \right) \end{aligned}$$ により $O(\pi(\sqrt[4]{m}))$ 回の演算で計算できる。
  • $1 \le m < q^4$ の場合: $O(1)$ 回の演算で計算できる。

よって、計算済みの値の取得に $O(\log(n))$ かかるとして、 $O\left(\sum\limits_{1 \le b \le \sqrt[9]{n}} \left(\sum\limits_{1 \le a \le \sqrt[6]{n}/b^{3/2}} \pi\left(\sqrt[4]{\frac{n}{a^2b^3}}\right)\right) \cdot \log(n) \right) = O\left( (\sqrt[3]{n}/\log(n)) \cdot \log(n)\right) = O(\sqrt[3]{n})$ 時間となる。

$V(F_{\pi(\sqrt[12]{n}) + 1}, n)$ の計算

前記事と同様の処理を行えばよい。

fenwick tree の query, update の回数は以下のようになる:

  • query の回数: $O(\pi(\sqrt[6]{n}) \cdot \sqrt[6]{n}) = O(\sqrt[3]{n} / \log{n})$ 回となる。
  • update の回数: $O\left(\sum\limits_{1 \le b \le n^{2/9}} \sum\limits_{1 \le m \le {\sqrt[3]{n}/b^{3/2}}}[\mathrm{lpf}(m) > \sqrt[12]{n}] \right) = O(\sqrt[3]{n}/\log(n))$ 回となる。

全体としての時間計算量は $O(\sqrt[3]{n}/\log(n) \cdot \log(n)) = O(\sqrt[3]{n})$ となる。

$V(F_{1}, n)$ の計算

$k = \pi(\sqrt[12]{n}), \dots, 1$ に対して、 $$F_{k}(m) = F_{k+1}(m) + \sum\limits_{e \ge 2} f(p^e) \cdot F_{k+1}(\lfloor{m/p^e\rfloor})$$ を用いて、更新する。
演算回数は $O\left(\sum_{2 \le p \le \sqrt[12]{n}} \sum_{1 \le P_i \le \sqrt{n}}\left(\log_{p}(n/P_i) + \log_{p}(P_i)\right) \right) = O(\sqrt[3]{n}/\log(n))$ となり、全体での時間計算量は $O(\sqrt[3]{n}/\log(n) \cdot \log(n)) = O(\sqrt[3]{n})$ となる。

以上により、$F(n) = F_1(n)$ は時間計算量 $O(\sqrt[3]{n} \log(n))$、空間計算量 $O(\sqrt[4]{n})$ で計算できる。
(※ まだ実装していないため、間違っている可能性があります。)