下面给出一种算法，该算法只需要使用加法运算和比较运算就可以求出n个数的最小公倍数：每一次操作都把当前最小的那个数加上它的初始值，直到所有数都相等为止。下面这个列表显示了用这个算法寻找30, 12, 18三个数的最小公倍数的全过程。初始时12是三个数中的最小数，于是该数加上12；接下来18成了最小的数，于是该数加上18变成了36；此时第二个数24又变成了最小数，于是再加上其对应的初始值12；以此类推直到三个数都变成相同的数180为止，这个180就是30, 12, 18的最小公倍数。

30 12 18
30 24 18
30 24 36
30 36 36
60 36 36
60 48 36
60 48 54
60 60 54
60 60 72
90 60 72
90 72 72
90 84 72
90 84 90
90 96 90
120 96 90
120 96 108
120 108 108
120 120 108
120 120 126
150 120 126
150 132 126
150 132 144
150 144 144
150 156 144
150 156 162
180 156 162
180 168 162
180 168 180
180 180 180

    这个算法为什么是正确的呢？它有什么实际用途呢？

Read more…

    又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

    很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+…)(1+1/3+1/9+…)(1+1/5+1/25+…)…展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+…+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

Read more…

对于哪些n，存在一个1到n-1的排列S_1, S_2, …, S_n-1，使得T_1, T_2, …, T_n-1也是一个1到n-1的排列，其中，

T_1 = S_1 mod n,
T_2 = (S_1 + S_2) mod n,
T_3 = (S_1 + S_2 + S_3) mod n,
…….
T_n-1 = (S_1 + S_2 + … + S_n-1) mod n.

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…