调和级数是指无穷级数1 + 1/2 + 1/3 + 1/4 + …，即取遍所有正整数n所得到的Σ1/n。虽然n趋于无穷时1/n趋于0，但这个无穷级数却是发散的。一个经典的证明是，把1/3和1/4都缩小到1/4，把1/5、1/6、1/7和1/8都缩小成1/8，把1/9到1/16这8个数全部缩小为1/16，以此类推，这样就可以得到无穷多个1/2，它们的和显然是无穷大的。
    现在，让我们把所有的质数划分为若干个子集，其中质数p属于编号为floor(p/1000)的那个子集（floor()是取下整的意思）。现在，你可以用这样的方式来定义一个“部分的”调和级数：先选出一些质数集合出来，然后列出所有这样的数，它所有的质因子都落在你选的集合里。显然，这样的数有无穷多个，它们的倒数和就形成了一个部分调和级数。例如，选择子集①和子集②，我们可以得到一个无穷级数Σ1/n，其中n取所有这样的数，它可以表示为大于等于1000小于3000的质数的乘积。
    前面我们已经看到，选择所有的集合所构成的无穷级数是发散的。现在的问题是，要想得到一个发散的级数，最少需要选取多少个集合？

Read more…

    期中告一段落。除了下下星期要交的现文史论文以外，最近似乎又清闲了不少，又有功夫在这里写点东西了。当然，我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》，进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我，有什么牛B一点的数学书没。我毫不犹豫地脱口而出，《什么是数学》。如果我要去一个荒岛上，只能带三本书，我会选择《算法导论》、《组合数学》和《什么是数学》。如果叫我舍弃一样，我估计会扔掉《组合数学》。如果还得再丢弃一本，我只好忍痛丢下《算法导论》了。
    读《什么是数学》的收获太多了。在这里，我只更新一些我原来不知道，又很有趣的东西。如果你希望迅速对此书有一个全面的了解，千万不要错过dd牛的《什么是数学》笔记。

    阅读《什么是数学》的前面几章时，你经常会跟随着书中的文字重新看待一个显而易见的结论，然后对这个结论有了一个全新的认识。比如，书中曾提到，为什么数学归纳法是合理的？我已经知道n=1时结论成立，也知道若n=k成立则n=k+1结论也成立，那么对于任意一个给定的正整数t，n=t时的结论是成立的，因为经过有限次迭代后最终我们总可以到达n=t的情况。但是，为什么我们敢断言对所有这无穷多个n，结论都是成立的？显然，你不能说“我们可以迭代无穷多次”，一个有限的证明过程当然不允许有无限多个步骤。因此，为了说明对于所有正整数n结论都成立，我们不得不使用反证法把“无穷”变成“有穷”。我们假设对于某些n，这个结论是不成立的。那么，这里面一定存在一个最小的数p，它使得结论不成立。由于我们已知n=1时结论成立，因此p一定是大于1的。但n=p是“最早”使结论不成立的情形，因此n=p-1时结论一定为真。这就与我们已知的第二个条件“若n=k成立则n=k+1结论也成立”矛盾了。因此我们说，对于所有正整数n，结论都是成立的。
    这个推理过程中用到了另一个显而易见的结论：对于一个非空的正整数集C，C中一定存在一个最小的元素。这又是为什么呢？你可能会说，废话，把所有元素拿出来两个两个的比，一定能比出一个最小的数来。这种说法是错误的。注意到集合C有可能有无穷多个元素，你是比不完的。为了更清晰地认识这个结论，我们只需要注意到，如果把条件换成“有理数集C”或者“实数集C”，结论就不再成立了，因为集合{1, 1/2, 1/3, 1/4, …}显然不存在一个最小的数。可以看到，上述结论是否成立是和数的稠密性紧紧相关的。事实上，为了说明正整数集C中存在最小元素，我们任意从集合中取出一个元素n，那么1, 2, …, n这有限多个数当中一定存在一个最小的数，它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。
Read more…

    画一个三角形阵列，初始时只有每一行的两头有标记，然后从上到下依次把每一行复制两份，摆放成一个等边三角形。最后你会发现，第i行为空行（除两头外不再有其它标记），当且仅当i为素数。对于其它行，标记的位置也与该行行号的质因子有关。这是为什么呢？
    照惯例，给个YouTube链接：http://youtube.com/watch?v=sbjPwyPT1AI

    设f[i,j]表示第i行左起第j个位置是否有标记。j从0开始计数（即第i行最左边用f[i,0]表示）。对于每个f[i,j]，我们将它的值赋给了f[i+j,j]和f[2*i-j,i]。也就是说，对于每组i和j，我们都进行以下两个操作：
f[i+j,j] <- f[i,j]
f[2*i-j,i] <- f[i,j]
    而这实际上就是辗转相除的变形，不断递归下去后，最终f[i,j]表示的其实就是i和j是否互质。这样一来，上面那些东西就全解释清楚了。
    用这种方法描述数论问题是一件很有趣的事，给人感觉很神奇。如果你感兴趣的话，这里有一个类似的例子，你可以看到Sierpinski三角形、杨辉三角和组合数的奇偶性是如何联系在一起的。

    我们已经知道，素数有无穷多个。当时我们用的是最普遍的证明方法：

假设存在最大的素数P，那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1（所有的素数乘起来加1）。显然这个数不能被任一素数整除（所有素数除它都余1），这说明我们找到了一个更大的素数。

    这里，我们将再提供两种新的证明方法，来自cut-the-knot两篇新文。

用Fermat数证明素数无穷多
    Fermat数是指形为2^(2^n)+1的数，我们把2^(2^n)+1记作F(n)，其中n可以取所有自然数。显然所有的Fermat数都是奇数。一会儿我们将看到任两个Fermat数都是互素的，也就是说，每一个Fermat数的每一个素因子都与其它Fermat数的素因子不同。这也就说明，素数个数有无穷多。
    引理1：F(0) * F(1) * F(2) * … * F(n-1) = F(n) – 2, n>=1
    证明：数学归纳法。F(0)=3且F(1)=5，那么k=1时显然成立。假设k=n成立，则当k=n+1时：
    F(0) * F(1) * F(2) * … * F(n)
  = ( F(0) * F(1) * F(2) * … * F(n-1) ) * F(n)
  = ( F(n)-2 ) * F(n)
  = ( 2^(2^n)-1 ) * ( 2^(2^n)+1 )
  = 2^(2^(n+1))-1
  = F(n+1)-2

    引理2：对任意两个不相等的自然数n和m，有F(n)和F(m)互素。
    证明：假设t同时整除F(n)和F(m)，m<n。根据引理1，有：
    F(n)=F(0) * F(1) * F(2) * … * F(m) * … * F(n-1) – 2
    这说明t可以整除
    F(0) * F(1) * F(2) * … * F(m) * … * F(n-1) – F(n) = 2
    注意到2只有两个因数1和2。前面说过Fermat数都是奇数，因此不可能被2整除。这样，t只能为1，这就证明了两个数互素。

用*-集合证明素数无穷多
    *-集合是一个正整数集合{a1, a2, … an}，使得对所有不相等的i和j都有ai-aj整除ai。
    引理1：对所有n>=2，都存在一个大小为n的*-集合。
    证明：数学归纳法。{1,2}显然是一个大小为2的*-集合。假设{a1, a2, … an}是一个*-集合。定义b0为a1*a2*…*an（即所有ai的乘积）。对所有不超过n的正整数k，令bk=b0+ak，那么{b0, b1, b2, …, bn}就是一个大小为n+1的*-集。

    引理2：假设{a1, a2, … an}是一个*-集合。对所有不超过n的正整数i，定义fi=2^ai+1，那么f1, f2, …, fn两两互素。
    证明：显然fi都是奇数。假设fk和fm(fk>fm)可以被同一个素数p整除，那么p也只能是奇数。p可以整除fk-fm即2^am * ( 2^(ak-am)-1 )。由于p是奇数，那么它只可能是整除2^(ak-am)-1。
    如果有s整除t，那么2^s-1整除2^t-1。于是，根据*-集合的定义，2^(ak-am)-1整除2^ak-1。那么p就可以整除2^ak-1。但p也能整除2^ak+1，于是我们得出p整除2，这与p为奇数矛盾。

    定理：素数有无穷多个
    证明：根据引理1和2，对任意大的n，都存在大小为n的集合，里面的数两两互素，即至少存在n个不同的素因子。这就说明了素数的个数可以任意多。