Problem 652

Distinct values of a proto-logarithmic function

Consider the values of $\log_{2} (8)$ , $\log_{4} (64)$ and $\log_{3} (27)$ . All three are equal to $3$ .

Generally, the function $f (m, n) = \log_{m} (n)$ over integers $m, n \geq 2$ has the property that
$f (m_{1}, n_{1}) = f (m_{2}, n_{2})$ if

$m_{1} = a^{e}$ , $n_{1} = a^{f}$ , $m_{2} = b^{e}$ , $n_{2} = b^{f}$ for some integers $a, b, e, f$ or
$m_{1} = a^{e}$ , $n_{1} = b^{e}$ , $m_{2} = a^{f}$ , $n_{2} = b^{f}$ for some integers $a, b, e, f$

We call a function $g (m, n)$ over integers $m, n \geq 2$ proto-logarithmic if

$g (m_{1}, n_{1}) = g (m_{2}, n_{2})$ if any integers $a, b, e, f$ fulfilling 1. or 2. can be found
and $g (m_{1}, n_{1}) \neq g (m_{2}, n_{2})$ if no integers $a, b, e, f$ fulfilling 1. or 2. can be found

Let $D (N)$ be the number of distinct values that any proto-logarithmic function $g (m, n)$ attains over $2 \leq m, n \leq N$ .
For example, $D (5) = 13$ , $D (10) = 69$ , $D (100) = 9607$ and $D (10000) = 99959605$ .

Find $D (10^{18})$ , and give the last $9$ digits as answer.

Note: According to the four exponentials conjecture the function $\log_{m} (n)$ is proto-logarithmic. While this conjecture is yet unproven in general, $\log_{m} (n)$ can be used to calculate $D (N)$ for small values of $N$ .

原型对数函数的不同取值

$\log_{2} (8)$ 、 $\log_{4} (64)$ 和 $\log_{3} (27)$ 这三个表达式都等于 $3$ 。

一般地，定义在整数 $m, n \geq 2$ 上的函数 $f (m, n) = \log_{m} (n)$ 有如下性质：
$f (m_{1}, n_{1}) = f (m_{2}, n_{2})$ 仅当

$m_{1} = a^{e}$ ， $n_{1} = a^{f}$ ， $m_{2} = b^{e}$ ， $n_{2} = b^{f}$ ，其中 $a, b, e, f$ 均为整数；或者
$m_{1} = a^{e}$ ， $n_{1} = b^{e}$ ， $m_{2} = a^{f}$ ， $n_{2} = b^{f}$ ，其中 $a, b, e, f$ 均为整数。

我们称定义在整数 $m, n \geq 2$ 上的函数 $g (m, n)$ 为原型对数函数，如果它满足

如果存在满足1. 或2. 的整数组 $a, b, e, f$ ，则 $g (m_{1}, n_{1}) = g (m_{2}, n_{2})$ ；
并且，如果不存在满足1. 或2. 的整数组 $a, b, e, f$ ，则 $g (m_{1}, n_{1}) \neq g (m_{2}, n_{2})$ 。

记 $D (N)$ 记为任意原型整数函数 $g (m, n)$ 在 $2 \leq m, n \leq N$ 上不同取值的数目。
已知， $D (5) = 13$ ， $D (10) = 69$ ， $D (100) = 9607$ ， $D (10000) = 99959605$ 。

求 $D (10^{18})$ ，并给出最后 $9$ 位数字作为你的答案。

注意：根据四指数猜想，函数 $\log_{m} (n)$ 是原型对数函数。尽管这个猜想尚未被证实，但是对较小的 $N$ 可以用 $\log_{m} (n)$ 来计算 $D (N)$ 。