物理

素数分布估计

$问题：1到n中有多少素数$

$\huge{\pi(n)的估计}$

$\pi(n)=\sum_{p≤n}1表示不超过n的素数个数$

$定理：(素数定理) lim_{n→∞}\frac{\pi(n)}{\frac{n}{ln~n}}=1.$

$这个定理我们可以知道n→∞，\pi(n)～\frac{n}{ln~n}$

$下面我们给出比这个定理弱的一个上界，证明工具很少，就比如先注意到6ln2=4.15…$

$定理①：对所有n≥2，有n^{\pi(n)} \lt 64^n(⇔\pi(n) \lt 6ln2·\frac{n}{ln~n}).$

$证：$

$由C_{2n}^n是\prod_{n \lt p≤2n}p的倍数$

$得n^{\pi(2n)-\pi(n)}=\prod_{n \lt p≤2n}n \lt \prod_{n \lt p≤2n}p≤C_{2n}^n≤4^n.$

$考虑n=2^k，有k(\pi(2^{k+1})-\pi(2^k))≤2^{k+1}$

$结合\pi(2^{k+1})≤2^k与上式相加得到：$

$(k+1)\pi(2^{k+1}-k\pi(2^k)≤3·2^k.$

$求和\sum_{k=1}^{n-1}(k+1)\pi(2^{k+1}-k\pi(2^k)≤\sum_{k=1}^{n-1}3·2^k.$

$整理得到n·\pi(2^k) \lt 3·2^k.$

$于是对于一般的n，设k=[log_2(n)]，则2^k≤n≤2^{k+1}$

$那么最终有：$

$n^{\pi(n)} \lt (2^{k+1})^{\pi(2^{k+1})} \lt 8^{2^{k+1}}≤64^n. $                 □

$定理②：对n≥2，有n^{\pi(n)}≥\sqrt{2}^n(⇔\pi(n)≥\frac{ln~2}{2}·\frac{n}{ln~n}.$

$证：$

$n≤5时显然成立，考虑n \gt 5.$

$记n=2k或2k-1，利用\pi(2k-1)=\pi(2k)，k≥2$

$只需证(2k-1)^{\pi(2k-1)}≥2^k，k≥3$

$由定理①得到：$

$对所有素数p \mid C_{2k}^{k}，有p^{v_p(C_{2k}^k)}≤(2k-1)^{\pi(2k-1)}.$

$故C_{2k}^k=\prod_{p≤2k-1}p^{v_p(C_{2k}^k)}≤(2k-1)^{\pi(2k-1)}.$

$由C_{2k}^k≥\frac{4^k}{2k+1}$

$只需k≥3，2^k≥2k+1，显然成立！$                                                     □

好累啊，睡觉啦 更新ing