来自MathPuzzle的消息：新一轮的Al Zimmermann编程大赛开始了。这次比赛的问题描述如下：

对于一个给定的n，找出n个正整数，使得通过它们之间的加减运算能够得到尽可能多的质数。

    具体的说，对于一个指定的n，参数选手需要提交n个数A1, A2, ..., An。这n个数将由公式ΣAi*Ci产生3^n个和（其中每个Ci可以取-1、0和1中的任一个），这3^n个和中（不同的）质数越多越好。例如，当n=4时，10, 29, 82, 106可以产生9个不同的质数：

5 = 106 + 10 - 82 - 29
19 = 29 - 10
29 = 29
43 = 82 - 29 - 10
53 = 82 - 29
67 = 106 - 29 - 10
101 = 82 + 29 - 10
149 = 106 + 82 - 29 -10
227 = 106 + 82 + 29 + 10

    参赛者需要完成n=3, 4, ..., 14共12个问题，提交的每一组数的和不能超过2^32-1。比赛将在2008年11月10日结束，你可以在此之前提交任意多次。获胜者可以从下面两个网页中任选一个雕刻品作为奖品。说实话，奖品很诱人，我很想要。
    http://www.bathsheba.com/sculpt/
    http://www.bathsheba.com/math/

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

    不假，利用数论知识我们真的可以证明这个和数论八杆子打不着的题目。证明的关键就在于，质数有无穷多个。给定一个满足要求的大矩形，如果你宣称它的每条边都不是整数，它们都至少多出了大小为ε的“零头”。那么，我就找出一个足够大的质数p，使得1/p < ε，然后说明有一条边的长度除去整数部分后的“零头”不会超过1/p。这样的话，至少有一边恰好是整数长才行。
    仍然是把大矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑所有形如(i/p, j/p)的点所形成的点阵（其中i, j均为整数）。我们需要把整个点阵平移到一个合适位置，使得点阵中没有点恰好落在小矩形的边界上。这总是可以办到的，例如我们算出每个小矩形的横边到点阵中离它最近的点的距离，取所有这些最近距离中最小的非0的值，然后竖直方向上移动一个比这还小的距离；另一个方向亦是如此。注意到每个小矩形内部所含的点数都是两个数的乘积，由于其中至少有一个数是p的倍数，因此每个小矩形内都有p的倍数个点。那么，整个大矩形所含的点的个数（即每个小矩形所含点数之和）也是p的倍数。大矩形内的所有点的个数也是两个数的乘积，然而p是质数，因此两个数中至少一个是p的倍数（数论的一个基本结论）。那么，对应的那条边就应该是整数长，并且最多有1/p的误差。

（三）（四）两种证明均来自http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/May1999.html

    又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在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)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

查看更多 »

    调和级数是指无穷级数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的质数的乘积。
    前面我们已经看到，选择所有的集合所构成的无穷级数是发散的。现在的问题是，要想得到一个发散的级数，最少需要选取多少个集合？

查看更多 »

    期中告一段落。除了下下星期要交的现文史论文以外，最近似乎又清闲了不少，又有功夫在这里写点东西了。当然，我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》，进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我，有什么牛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中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。
查看更多 »

    今天又学到一个牛B东西。你相信吗？正则表达式竟然可以用来判定素数，甚至可以用来解方程！下面这段正则表达式可以用来判断，一个字符串的长度是否为合数（假设这个字符串里全是字符'1'）：
^1?$|^(11+?)\1+$
    不信的话，把下面这段代码复制到你浏览器的地址栏里运行一下，True表示这个数为合数，False表示这个数为素数：

javascript:var st="1";for(var i=2;i<100;i++)document.write(i," ",/^1?$|^(11+?)\1+$/.test(st=st+"1"),"<br/>");document.close();

    其实，它的原理很简单。加号表示匹配一次或多次（加上一个问号表示非贪婪模式），\1表示引用括号里的内容，头尾的^和$则避免了部分匹配的情况。这样，^(11+?)相当于枚举除数大小，而\1+$则用于检验整个字符串是否能按此大小恰好分完。如果除得尽，则匹配成功，字符串长度为合数。另外，前面的^1?$只是为了处理n=0或n=1时的特殊情况，而符号|则表示“或者”的意思。

    采用同样的方法，我们还可以想出正则表达式其它一些类似的用途。比如，我们可以用这个正则表达式检查方程11x + 2y + 5z = 115是否有自然数解：
^(.*)\1{10}(.*)\2{1}(.*)\3{4}$
    正则表达式中，{x}表示和前面的内容匹配x次。只要用这个表达式去检测一个有115个字符的字符串，匹配成功则表示有自然数解。它的原理和上面的基本一样，我就不再重复了。

参考资料：http://blog.stevenlevithan.com/archives/algebra-with-regexes

  

    画一个三角形阵列，初始时只有每一行的两头有标记，然后从上到下依次把每一行复制两份，摆放成一个等边三角形。最后你会发现，第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个不同的素因子。这就说明了素数的个数可以任意多。