0%

Problem 652


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\ge 2$ has the property that
$f(m_1,n_1)=f(m_2,n_2)$ if

  1. $m_1=a^e$, $n_1=a^f$, $m_2=b^e$, $n_2=b^f$ for some integers $a, b, e, f$ or
  2. $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\ge 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\le m,n\le 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\ge 2$上的函数$f(m,n)=\log_m(n)$有如下性质:
$f(m_1,n_1)=f(m_2,n_2)$仅当

  1. $m_1=a^e$,$n_1=a^f$,$m_2=b^e$,$n_2=b^f$,其中$a, b, e, f$均为整数;或者
  2. $m_1=a^e$,$n_1=b^e$,$m_2=a^f$,$n_2=b^f$,其中$a, b, e, f$均为整数。

我们称定义在整数$m,n\ge 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\le m,n\le 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)$。