按类别列出问题

161. 素数的筛法

Posted by haifeng on 2011-06-16 17:24:26 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

162. Thm. 关于 $\pi(x)$ 的一个重要定理.

Posted by haifeng on 2011-06-16 16:15:19 last update 2020-05-15 10:45:49 | Answers (0) | 收藏

设 $x>0$, $\pi(x)$ 指不超过 $x$ 的所有素数的个数. 若记 $p_i$ 为第 $i$ 个素数, 则 $\pi(x)=\max\{i|p_i\leq x\}$.

$\pi(n)<2\log 2\cdot\frac{n}{\log n}$, 对每个大于1的整数 $n$.
当 $x\rightarrow+\infty$ 时, $\pi(x)\sim\frac{x}{\log x}$.
存在常数 $A,B > 0$, 使得对每个大于1的整数 $n$, 有
\[ An\log n < p_n < B n\log n. \]

黎曼假设(Riemann Hypothesis)等价于

\[
\pi(x)=\text{Li}(x)+O(\sqrt{x}\ln x)
\]

其中

\[
\mathrm{Li}(x):=\int_{2}^{x}\frac{1}{\ln t}dt=\text{li}(x)-\text{li}(2).
\]

\[
\mathrm{Li}(x)\sim\frac{x}{\ln x}\sum_{k=0}^{\infty}\frac{k!}{(\ln x)^k}=\frac{x}{\ln x}+\frac{x}{(\ln x)^2}+\frac{2!\cdot x}{(\ln x)^3}+\frac{3!\cdot x}{(\ln x)^4}+\frac{4!\cdot x}{(\ln x)^5}+\cdots
\]

$\pi(x)$ 与 $\mathrm{Li}(x)$ 之间差值的估计也可以表述为

\[
\pi(x)=\sum_{p\leqslant x}1=\int_{2}^{x}\frac{1}{\ln t}dt+O(xe^{-c\sqrt{\ln x}})
\]

163. Sundaram sieve

Posted by haifeng on 2011-06-16 15:53:16 last update 0000-00-00 00:00:00 | Answers (1) | 收藏

考虑如下无限矩阵, 每一行都是等差数列, 公差依次是 3,5,7,9,11,...
\begin{matrix} 4&7&10&13&16&\cdots\\ 7&12&17&22&27&\cdots\\ 10&17&24&31&38&\cdots\\ 13&22&31&40&49&\cdots\\ 16&27&38&49&60&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots& \end{matrix} 证明 $2n+1$ 是素数当且仅当 $n$ 不在上面的矩阵中.

164. Bertrand\'s postulate 的直接推论

Posted by haifeng on 2011-06-16 14:58:41 last update 2016-08-30 17:19:53 | Answers (0) | 收藏

设 $\{p_i\}_{i\geq 1}$ 是一递增素数列. 则对每个 $i$, 有 $p_{i+1}\leq 2p_i$.
任给素数 $p$, 总存在一个素数 $q$ 使得 $p < q < p^2$.

特别的, 当 $p_i > 3$, 根据 Bertrand 假设(见问题661), $(p_{i},2p_i-2)$ 之间至少存在一个素数, 因此 $p_{i+1} < 2p_i$.

也就是说, 满足 $p_{n+1}=2p_n-1$ 的只有两个例子:

\[
2\times 2-1= 3 =p_2,\quad 2\times 3-1= 5 =p_3.
\]

165. (Bertrand\'s postulate) 设 $n$ 为正整数, 则总存在素数 $p$ 使得 $n < p\leq 2n$.

Posted by haifeng on 2011-06-16 14:51:54 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

1845年, Bertrand 给出了这个猜测, 5 年后, 也就是1850年, Tchebycheff 给出了证明. 参见

G.H.Hardy and E.M.Wright, An Introduction to the Theory of Numbers. Oxford Science Publications, 5th edition (1979). pp.343-344.

166. 设 $p$ 为大于 2 的素数. 从 $\mathbb{N}-\{1\}$ 中删去不超过 $p$ 的所有素数的倍数, 得到数列 $\{u_n\}_{n=1}^{+\infty}$. 求 $d_n=u_{n+1}-u_n$.

Posted by haifeng on 2011-06-16 13:00:53 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

$d_n$ 成周期分布, 可以证明存在递推关系. 周期为r \[ \prod_{\text{prime } k \leq p}(k-1). \]

167. 从 $\mathbb{N}-\{1\}$ 中删去 2,3,5,7,11 的倍数, 得到数列 $\{u_n\}_{n=1}^{+\infty}$. 求 $d_n=u_{n+1}-u_n$.

Posted by haifeng on 2011-06-16 12:53:22 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

$d_n$ 的周期为 (2-1)(3-1)(5-1)(7-1)(11-1)=480. 周期的构成为:

4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4 6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4 6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2 4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10 2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6 4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6 4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6 8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4 2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4 2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6 4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6 2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6 2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10 6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2 4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4 2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4 2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2 12

168. 从 $\mathbb{N}-\{1\}$ 中删去 2,3,5,7 的倍数, 得到数列 $\{u_n\}_{n=1}^{+\infty}$. 求 $d_n=u_{n+1}-u_n$.

Posted by haifeng on 2011-06-16 12:48:19 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

$d_n$ 成周期分布: 每个周期是 (2-1)(3-1)(5-1)(7-1)=48 个数, 具体为

2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10

169. 从 $\mathbb{N}-\{1\}$ 中删去 2,3,5 的倍数, 得到数列 $\{u_n\}_{n=1}^{+\infty}$. 求 $d_n=u_{n+1}-u_n$.

Posted by haifeng on 2011-06-16 12:44:36 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

$u_n$:

 
7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101

$d_n$:


4 2 4 2 4 6 2 6 | 4 2 4 2 4 6 2 6 | 4 2 4 2 4 6 2 6 | 4 ...

170. 从 $\mathbb{N}-\{1\}$ 中删去 2,3 的倍数, 得到数列 $\{u_n\}_{n=1}^{+\infty}$. 证明该数列存在一定的递推关系.

Posted by haifeng on 2011-06-16 12:38:14 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

\[ \begin{cases} u_{2k+1}=u_{2k}+4,\\ u_{2k}=u_{2k-1}+2, \end{cases} \] 其中 $k=1,2,\ldots,$