今天见到一种看上去很帅的质数筛选法。在平面直角坐标系上画出抛物线 y = x2 的图像，然后标出抛物线上的所有格点（两坐标均为整数的点）。其中，只有点 (0, 0) 正好在 y 轴上，其余的点要么在 y 轴左侧，要么在 y 轴右侧。把 y 轴左侧除了 (-1, 1) 以外的所有格点与 y 轴右侧除了 (1, 1) 以外的所有格点相连，这些连线将自动避开 y 轴上纵坐标为质数的点。连接足够多的线条之后，质数就逐渐露了出来。
这是因为， (-a, a2) 和 (b, b2) 的连线将经过 (0, a · b) ，这可以通过计算斜率的方法得到验证。这个颇具创意的质数筛选法叫做 visual sieve ，它是由 Yuri Matiyasevich 和 Boris Stechkin 提出的。
查看更多：
http://plus.maths.org/content/catching-primes
http://www.mathteacherctk.com/blog/2011/10/the-parabolic-sieve-of-prime-numbers/
今天又学到一种证明素数无穷多的方法。它是由 Filip Saidak 发现的，论文曾发表在 2006 年的 The American Mathematical Monthly 上。
首先注意到，两个相邻自然数一定是互质的（否则，假设它们有大于 1 的公因数 k ，则它们的差也能被 k 整除，这显然是不可能的）。现在，取一个自然数 n > 1 。由于 n 和 n + 1 是相邻自然数，因此 n 和 n + 1 是互质的。也就是说，n 的质因数和 n + 1 的质因数完全没有重合，因而 n(n + 1) 至少有两个不同的质因数。类似地，由于 n(n + 1) 和 n(n + 1) +1 是相邻自然数，因此它们是互质的，这说明 n(n + 1) 和 n(n + 1) +1 没有相同的质因数，也就是说 (n(n + 1))(n(n + 1) +1) 至少有三个不同的质因数。我们可以无限地这样推下去，从而得出，素数必然是无穷多的。
心电图数列 (EKG Sequence) 的定义简单而有趣：第一项为 1 ，第二项为 2 ，以后的每一项都是最小的和前一项不互质并且不曾出现过的数。换句话说，数列 a(1)=1 ， a(2)=2 ，且当 n>2 时取 a(n) 为所有满足以下两个条件的数中最小的那一个：该数与 a(n-1) 有大于 1 的公约数，并且该数与前面 n-1 项都不相等。心电图数列的前面 20 项为
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 ...
为什么它叫做心电图数列呢？原因很简单——因为把它描绘在图象上时，看上去像一张心电图。
搞过 OI/ACM 的同学们想必对一道经典题目印象极深：求 n 的阶乘末尾有多少个 0 。注意到末尾的一个 0 是由一个因子 2 和一个因子 5 相乘产生的；但在 n 的阶乘里，因子 5 的个数通常远远少于因子 2 。因此这个问题就等价于问 n 的阶乘里有多少个因子 5 。在 n 的阶乘式中，每个 5 的倍数里都含有一个因子 5 ，每个 25 的倍数里都还含有另外一个因子 5 ，每个 125 的倍数里都还有第三个因子 5 ……因此， n 的阶乘里因子 5 的个数的计算公式就是 ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... 。如果把 K 的阶乘里素因子 p 的个数记作 Φ(p, K) ，则 Φ(p, K) = Σ⌊K/(p^i)⌋ 。有意思的是，最近 The American Mathematical Monthly 上的一篇文章利用这个公式瞬间证明了素数无穷多的定理。
如果素数是有限的，则 K 的阶乘就可以写成所有 p^Φ(p, K) 的乘积，其中的 p 取遍所有的素数。注意到 Φ(p, K) = Σ⌊K/(p^i)⌋ < Σ(K/(p^i)) = K/(p-1) < K ，因此对任意正整数 K 都有 K! < (Πp)^K ，其中 Πp 表示所有素数的乘积。但当 K 充分大的时候， K! 显然会超过一个常数的 K 次方，矛盾。因此素数不可能是有限的。
UyHiP上个月的题目：把所有大于 1 的自然数划分成两个集合，证明至少能在其中一个集合里找到互不相同的三个数 a 、 b 、 c 满足 a^b=c 。然后，试着给出一种划分，使得只有其中一个集合里存在这样的三元组。
Update: 后一个问题要求两个集合都是无限集。感谢网友 Triple.J 的提醒。
证明：如果集合 A 里只有有限个数，那就在集合 B 里选两个比集合 A 中的最大数还大的数 a 和 b ，显然 a^b 也在集合 B 里。类似的，若集合 B 里只有有限个数，我们立即可知 A 中存在满足 a^b=c 的三元组。因此，我们只需要讨论两个集合里都有无穷多个数的情况。
从集合 A 里选一个数 x ，从集合 B 里选一个数 y 。无妨假设 xy 在集合 A 中。在集合 A 中选一个比 xy 大的数 r 。由于集合 A 是无限大的，因此这样的数总存在。由于 r 比 xy 大，因此 x 、 y 、 xy 、 r 、 r^x 、 r^(xy) 这六个数两两不同。为了避免在同一集合里出现满足要求的三元组， r^x 和 r^(xy) 都必须在集合B里面，但这样的话， r^x 、 y 和 r^(xy) 就成了符合要求的三元组了。
后一个问题则出奇的简单：把所有素数放进一个集合，所有合数放进另一个集合。显然，一个素数不可能是另一个素数的整数次幂
。
这个月的题目非常有意思，点击这里围观。
偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * ... * Pm^Xm，其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵，我们有：
log(n) = H(N)
= H(X1, X2, ..., Xm)
≤ H(X1) + H(X2) + ... + H(Xm)
≤ log(log(n)+1) * m
上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的：由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, ..., Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。
去年就看过Proofs from THE BOOK第一章中的素数无穷多的拓扑学证明，不过当时似乎并没有看懂。今天看到cut-the-knot的一篇新文章，又把Proofs from THE BOOK拿出来翻了一下，终于看明白了，果然是一个令人拍案叫绝的经典证明，可谓又一神来之笔。
定义N(a,b) = {a + nb| n∈Z}，例如N(1,3)就等于{..., -5, -2, 1, 4, 7, ...}。每一个N(a,b)实质上都是一个以b为公差的“双向无限等差数列”。我们说整数集Z上的一个子集S是开的，如果集合S为空，或者对于任意一个a∈S，总能找到一个b>0使得N(a,b)⊆S。形象地说，开集的意思就是，集合中的每一个元素都能在集合内扩展出一个无限长的双向等差数列。我们又称一个集合S是闭的，如果它是某个开集的补集。
显然，有限个开集的并集仍然是开集。
假设S_1和S_2都是开集，如果a∈S_1∩S_2，并且N(a,b1)⊆S_1，N(a,b2)⊆S_2，那么S_1∩S_2中有一个公差为b1*b2的含a的双向无限等差数列，也即a∈N(a, b1*b2)⊆S_1∩S_2。这说明，有限个开集的交集仍然是开集。
再假设C_1和C_2都是闭集。由De Morgan定律，C_1和C_2的并集就相等于它们各自的补集相交后再取补集，由定义可知它们的补集都是开集，而由上面的结论可知开集的交集仍是开集。于是，C_1和C_2的并集是某个开集的补集，这说明闭集的并仍然是闭集。类似地，闭集的交集相当于补集的并集的补集，它也仍然是闭的。
还有两点值得引起我们注意：
1. 任意非空开集都是无穷的。这由定义可以直接看出来。
2. 任一双向无限等差数列N(a,b)既是开集又是闭集。由定义可知N(a,b)是开集，而同时N(a,b)又可以看作是N(a+1,b)∪N(a+2,b)∪N(a+3,b)∪...∪N(a+b-1,b)的补集，这是有限个开集的并集的补集，说明N(a,b)也是闭集。
Matrix67 |
2011-11-05 22:49 | 
