问题及解答

对于 $k,n\in\mathbb{N}$, 定义

\[f(n,k):=\sum_{n<v\leq n+k, P(v)\leq k}1\]

其中 $P(v)$ 指正整数 $v$ 的最大素因子.

当 $k\geq n$ 时, 显然有

\[f(n,k)=k-\bigl(\pi(n+k)-\pi(k)\bigr)\]

这里 $\pi(k)$ 指不超过 $k$ 的素数个数.

References

P. Erdos and J. Turk, Products of integers in short intervals,

$k\geq n$ 的情形比较简单. 首先

\[\pi(n+k)-\pi(k)=\text{Card}\{p\ \text{素数}\mid k<p\leq n+k\}\]

显然对于这些素数 $p$, $P(p)=p>k$, 因此不应计算在内, 要排除掉. 其次, $[n,k]$ 中的数的最大素因子显然不可能超过 $k$. 而 $[k,n+k]$ 中的合数 $m=p_1^{v_1}p_2^{v_2}\cdots p_l^{v_l}$, 设 $P(m)=p_l$, 则有

\[2k\geq n+k\geq m\geq 2p_l\]

这推出 $p_l\leq k$, 所以这些数应计算在内. 故当 $k\geq n$ 时

\[f(n,k)=k-[\pi(n+k)-\pi(k)].\]