千万不要迷信规律——大反例合集

千万不要迷信规律——大反例合集

ID:14278078

大小:167.00 KB

页数:9页

时间:2018-07-27

千万不要迷信规律——大反例合集_第1页
千万不要迷信规律——大反例合集_第2页
千万不要迷信规律——大反例合集_第3页
千万不要迷信规律——大反例合集_第4页
千万不要迷信规律——大反例合集_第5页
资源描述:

《千万不要迷信规律——大反例合集》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、千万不要迷信规律:大反例合集    数学猜想并不总是对的,错误的数学猜想不占少数。关键在于,有时反例太大,找出反例实在是太困难了。这篇日志收集了很多“大反例”的例子,里面提到的规律看上去非常诱人,要试到相当大的数时才会出现第一个反例。千万不要迷信规律    圆上有n个点,两两之间连线后,最多可以把整个圆分成多少块?          上图显示的就是n分别为2、3、4的情况。可以看到,圆分别被划分成了2块、4块、8块。规律似乎非常明显:圆周上每多一个点,划分出来的区域数就会翻一倍。    事实上真的是这样吗?让我们看看当n

2、=5时的情况:          果然不出所料,整个圆被分成了16块,区域数依旧满足2n-1的规律。此时,大家都会觉得证据已经充分,不必继续往下验证了吧。偏偏就在n=6时,意外出现了:          此时区域数只有31个。  最有名的素数生成公式    1772年,Euler曾经发现,当n是正整数时,n2+n+41似乎总是素数。事实上,n从1一直取到39,算出来的结果分别是:43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461

3、,503,547,593,641,691,743,797,853,911,971,1033,1097,1163,1231,1301,1373,1447,1523,1601    这些数全都是素数。第一次例外发生在n=40的时候,此时402+40+41=402+40+40+1=(40+1)(40+1)=41×41。  xn-1的因式分解    x2-1分解因式后等于(x+1)(x-1)。x20-1分解因式后等于(x-1)(x+1)(x2+1)(x4-x3+x2-x+1)(x4+x3+x2+x+1)(x8-x6+x4-x2+

4、1)    对于所有的正整数n,xn-1因式分解后各项系数都只有可能是1或者-1吗?据说有人曾经算到了x100-1,均没有发现反例,终于放心大胆地做出了这个猜想。悲剧的是,这个猜想是错误的,第一个反例出现在n=105的情况,x105-1分解出来等于(x-1)(x2+x+1)(x4+x3+x2+x+1)(x6+x5+x4+x3+x2+x+1)(x8-x7+x5-x4+x3-x+1)(x12-x11+x9-x8+x6-x4+x3-x+1)(x24-x23+x19-x18+x17-x16+x14-x13+x12-x11+x10

5、-x8+x7-x6+x5-x+1)(x48+x47+x46-x43-x42-2x41-x40-x39+x36+x35+x34+x33+x32+x31-x28-x26-x24-x22-x20+x17+x16+x15+x14+x13+x12-x9-x8-2x7-x6-x5+x2+x+1)  以2为底的伪素数    下面是当n较小的时候,n与2n-2的值。          似乎有这样的规律:n能整除2n-2,当且仅当n是一个素数。如果真是这样的话,我们无疑有了一种超级高效的素数判定算法(2n可以用二分法速算,期间可以不断模n

6、)。国外数学界一直传有“中国人2000多年前就发现了这一规律”的说法,后来发现其实是对《九章算术》一书的错误翻译造成的。再后来人们发现,这个规律竟然是错误的。第一个反例是n=341,此时341能够整除2341-2,但341=11×31。    事实上,根据Fermat小定理,如果p是素数,那么p一定能整除2n-2。不过,它的逆定理却是不成立的,上面提到的341便是一例。我们把这种数叫做以2为底的伪素数。由于这种素数判定法的反例出人意料的少,我们完全可以用它来做一个概率型的素数判定算法。事实上,著名的Miller-Rabi

7、n素性测试算法就是用的这个原理。  Perrin伪素数    定义f(n)=f(n-2)+f(n-3),其中f(1)=0,f(2)=2,f(3)=3。这个数列叫做Perrin数列。          似乎有这么一个规律:n能整除Perrin数列的第n项f(n),当且仅当n是一个素数。如果这个规律成立的话,我们也将获得一个效率非常高的素数检验方法。根据MathWorld的描述,1899年Perrin本人曾经做过试验,随后Malo在1900年,Escot在1901年,以及Jarden在1966年都做过搜索,均未发现任何反例。

8、直到1982年,Adams和Shanks才发现第一个反例n=271441,它等于521×521,却也能整除f(271441)。下一个反例则发生在n=904631的时候,再下一个反例则是n=16532714。这种反例被称为Perrin伪素数。  最经典的大反例    说到大反例,这是我最喜欢举的例子。下面是大于1的正整

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。