关于n/k(1≤k≤n)分数部分≥1/2的元素占比极限的已知性与原理解析问询
嘿,这个发现真的很有意思!你观察到的这个≈2.588的极限其实是数论领域里已经被研究过的内容,咱们来一步步拆解它的来龙去脉:
首先明确一下:你代码里输出的n/count,其实是总元素个数除以满足条件的元素个数,对应的是满足${n/k} \geq 1/2$(这里${x}$表示$x$的分数部分)的元素占比的倒数。当$n$趋向无穷时,这个值的极限确实是你看到的≈2.588,背后的核心思路是用「离散求和转连续积分」的方法来推导:
核心推导过程
当$n$足够大时,我们可以把离散的变量$k$转化为连续变量来近似:令$x = k/n$(即$k$是$n$乘以一个$(0,1]$区间内的连续变量),此时$n/k = 1/x$,条件${n/k} \geq 1/2$就等价于${1/x} \geq 1/2$。
满足条件的元素占比$\frac{\text{count}(n)}{n}$,当$n \to \infty$时可以用积分来近似:
$$
\frac{\text{count}(n)}{n} \approx \int_{0}^{1} \mathbf{1}{{1/x} \geq 1/2} dx
$$
这里的$\mathbf{1}{\text{条件}}$是指示函数,满足条件时取1,否则取0。
接下来计算这个积分:
- 做变量替换$t = 1/x$,则$x = 1/t$,$dx = -\frac{1}{t^2}dt$,积分范围从$t=\infty$变为$t=1$,积分转化为:
$$
\int_{1}^{\infty} \mathbf{1}_{{t} \geq 1/2} \cdot \frac{1}{t^2} dt
$$ - ${t} \geq 1/2$意味着$t$落在区间$[m+1/2, m+1)$($m$是≥1的整数),因此可以把积分拆成无穷级数求和:
$$
\sum_{m=1}^{\infty} \int_{m+1/2}^{m+1} \frac{1}{t^2} dt
$$ - 计算每个区间的定积分:$\int_{a}^{b} \frac{1}{t^2} dt = \frac{1}{a} - \frac{1}{b}$,代入后得到:
$$
\sum_{m=1}^{\infty} \left( \frac{1}{m+1/2} - \frac{1}{m+1} \right)
$$ - 利用已知的交错调和级数结果$\sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} = \log 2$,可以化简这个级数,最终得到和为$2\log 2 - 1 \approx 0.386$。
对应你的观察
既然$\frac{\text{count}(n)}{n}$的极限是$2\log 2 - 1$,那么$\frac{n}{\text{count}(n)}$的极限就是$\frac{1}{2\log 2 - 1} \approx 2.588$,和你代码运行得到的结果完全吻合!
已知性说明
这个结论是数论中关于分数部分分布的经典结果之一,这类问题通常会用到「离散求和的连续近似」技巧——当$n$足够大时,离散的$k$在$1$到$n$之间的分布可以用连续变量在$(0,1]$区间的分布来逼近,从而通过积分计算出极限值。
备注:内容来源于stack exchange,提问作者MikeTeX




