算法一千零一夜 · 第十八夜 万物皆数到底是谬论还是神明的裁决

第十八夜 万物皆数到底是谬论还是神明的裁决上一封信的末尾我把素数叫作数字的原子。你在回信里问原子之后呢。动笔之前桌上压着一句更老的口号。万物皆数。它有两千五百多岁有人说它是谬论有人说它是神明的裁决。一句话在公堂上站了两千五百年没有判决它是谬论还是裁决。这一夜把证人一个个请上来判决你在卷宗末尾落笔。第一位证人是公元前 6 世纪的一所学派。首领叫毕达哥拉斯信众把数当作信仰来研究传说他们主张万物由数写成。在他们手里数不是抽象的符号是鹅卵石。一颗两颗三颗在桌上摆出图形来。有些数总能摆成矩形6 颗摆二乘三8 颗摆二乘四12 颗摆三乘四。有些数怎么摆都不成235711只能孤零零排成一条线。摆不成矩形的数今天有正式的名字叫素数。顺便说一句摆得成正方形的那些数正是上一夜长街上亮着的那十盏灯。鹅卵石不会说谎。这一派最崇拜两个数。把 6 的因子请来123加起来恰好是 6。把 28 的因子请来124714加起来恰好是 28。一个数等于自身全部真因数之和他们给这样的数起了名字完全数。6 是头一个28 是第二个再往后的第三个是 496第四个是 8128要等到很多个世纪之后才被人们一个个找出来。完美如此稀少如此严丝合缝世界看起来确实像是用数写成的而且写得一丝不苟。万物皆数在那个年代不是口号是学派的教义。裂缝也是从学派内部裂开的。有位信徒叫希帕索斯他研究正方形。边长是 1对角线多长。他发现这条对角线不能写成两个整数之比怎么约都约不出。今天我们把它写作 $\sqrt{2}$。传说学派被吓坏了传说希帕索斯落了海有人说是被推下去的。第十夜讲方程四千年的时候我们提过这段传说今夜把它捞出来重审。后人常常说是 $\sqrt{2}$ 击碎了万物皆数。这个判词值得再看一眼。正方形的对角线最后不还是用 $\sqrt{2}$ 表示了吗。万物皆数说的是一切都能用数表示毕达哥拉斯只是摆了半辈子鹅卵石摆出来的全是整数和整数之比他没有想过数比那些鹅卵石大得多。希帕索斯没有埋葬这条教义他不是掘墓人他是第一个看见边界之外还有数的人第一个越境者。公元前 300 年前后欧几里得写《几何原本》。书里给素数留了三行字两千年没有人推翻。假如素数数得完把名单上的素数全部乘起来再加一。得到的数除以名单上任何一个素数都余一因为每一次除都恰好用掉对方完整的一份。所以它要么自己是名单之外的新素数要么素因子全部在名单之外。无论哪种名单都不完整。三行字素数就数不完了。《几何原本》的第九卷还给完全数发了一个形式。若 $2^{p}-1$ 是素数则 $2^{p-1}(2^{p}-1)$ 是完全数。把 p 取 2 代进去得 6取 3 得 28取 5 得 496取 7 得 8128。当时已知的四个完全数全从这一个模子里出来。欧几里得没有去一个个找完美的数他直接找到了完美的模子。八百年后这个模子收到了中世纪最重的背书。奥古斯丁在《上帝之城》第十一卷里写道上帝用六天创世不是因为六天够用恰恰相反六自身是完美的就算创世不曾发生六依然是完美的。他又指向天空月亮大约 28 天走完一次圆缺而 28 正是下一个完全数。有一笔要替他登记月亮 28 天是古人那时的说法今天天文年历写的是朔望月 29.5 天这不耽误 28 完美。神学家把 6 和 28 供了起来数字里头这两个最早领到神明亲手写的证明。十七世纪的巴黎有一座不寻常的修道院不烧香收发信件。笛卡尔费马帕斯卡全欧洲学者的通信与猜想都从一个人手里中转修士梅森修道院就是学术界的大邮局。1644 年梅森开出一个名单。p 取 23571317193167127257 时$2^{p}-1$ 是素数。$2^{p}-1$ 这样形式的数后来叫梅森数其中是素数的叫梅森素数。名单有对有错却把后人寻找完全数的路指向一条道因为偶完全数与梅森素数一一绑定找到一个梅森素数就得到一个完全数。1772 年欧拉把名单上最大的那个拿下了。他先用理论把除数范围砍到只剩形如 2kp1 的数再动手证明 $2^{31}-12147483647$ 是素数。这个十位数在世界最大已知素数的交椅上坐了 110 年。那一年欧拉 65 岁。他又把欧几里得那条公式补全了另一半。欧几里得说若 $2^{p}-1$ 是素数则 $2^{p-1}(2^{p}-1)$ 是完全数欧拉说反过去也对偶完全数只能是这个形式没有别的。相隔二十个世纪的两个人合写了同一条定理今天它叫欧几里得-欧拉定理是三个家族之间缝得最紧的那一针。到了 20 世纪人们终于把修士的名单彻底对了一遍表对出五处错。67 和 257 是错的6189107 三个漏了名单完全厘清已经将近两千年后。修士的表也会走错裁决从来不在人的手里。1903 年 10 月 31 日美国数学会在纽约开会一位叫科尔的学者走上讲台。台下等着他开口他没有说话。他走向黑板算出 $2^{67}-1147573952589676412927$又走向另一块黑板乘出 $193707721\times761838257287$。两个数相等。他放下粉笔回到座位自始至终没有说一个字全场起立。后来有人问他算了多久他说三年的星期天。梅森名单上那个错误的 67两百多年没有人推翻被三年的星期天推翻了。今天轮到机器了。分布式计算项目 GIMPS互联网梅森素数大搜索几十万台机器一起梳理数字。2024 年 10 月 12 日Luke Durant 用 GPU 算力找到了第 52 个梅森素数 $2^{136279841}-1$写出来有 41,024,320 位。一个人的心算一个人三年的星期天几十万台机器。公堂越开越大判决依然没有下来。故事讲完了。现在让说书人出场把这张长卷铺开。这场官司从来不止审过一次。数学史上有三次大危机每一次危机都是开庭每一次开庭数都比上一次更广大。说书人先把一笔旧话补上。素数也好完全数也好梅森素数也好这一夜讲的全是自然数家里的居民可自然数自己的出生证明1889 年才办下来。意大利人皮亚诺把五条写成了公理。零是自然数。每个自然数都有一个后继。零不是任何数的后继。后继不同原数就不同。从零出发沿着后继走能走到每一个自然数。有意思的是皮亚诺原著里自然数从 1 起步从 0 起步是后来的约定程序员们都说改得好。你天天写 for 循环i 从零出发i 每次取后继写的就是这五条。递归为什么可信因为它站在数学归纳法上。数学归纳法为什么可信因为它就是皮亚诺的第五条公理。你写下的每一段循环与递归地基都铺在 1889 年那本薄薄的拉丁文小册子里。然后是三次开庭。第一次就是希帕索斯那块 $\sqrt{2}$第二幕审过一回案子直到十九世纪戴德金造出实数才结案。第二次在十七八世纪微积分的无穷小说不清是什么贝克莱主教 1734 年讥它为消失量的幽灵直到柯西与魏尔斯特拉斯用极限重新浇了地基。第三次在 1902 年罗素问所有不包含自己的集合组成的集合包含不包含它自己朴素的集合论当场答不上话公理化运动与哥德尔不完备定理接踵而来。三次开庭三次扩张数越走越广大教义一步一步退守又一步一步站稳。所以判决到底是什么。说书人放下惊堂木如实说还没有判。奇完全数到底存不存在到今天没有人知道机器已经把 $10^{1500}$ 以内梳理了一遍一个也没有找到可谁也不敢断言往后也没有。毕达哥拉斯那一派没有输。万物皆数说的本就是一切都能用数表示正方形的对角线最后也确实用 $\sqrt{2}$ 表示了。毕达哥拉斯没有错他只是没有料到数比他摆过的鹅卵石更广大广大到装得下无理数装得下无穷装得下希尔伯特那家住满客人却永远能再住进一位的旅馆。那家旅馆的故事留给以后的某一夜。计算机的世界就是这么奇妙人对数字追寻了几千年。而程序算尽的却是人类所知的整个世界。这场判决迟迟没有落笔不是因为证据不足是因为被告比公堂想象的更广大。这一夜的回信写得比哪一夜都长。完全数把自己数得干干净净6284968128每一个都恰好数回自己。可有一种数数的不是自己是别人。220 数出来的是 284284 数回来的又是 220。中世纪的欧洲有人把 220 和 284 分戴在两人腕上一人一只一生不分离。下一夜我们去见这两个数见一见人们说的另一个我。publicclassNight18Verdict{// 试除判素只数到平方根i*in 是这条路的大门staticbooleanisPrime(longn){if(n2)returnfalse;for(longi2;i*in;i){if(n%i0)returnfalse;}returntrue;}// 真因数之和因子首尾成双各记一次落单的平方根只记一次最后减去自身staticlongsumProperDivisors(longn){longsum0;for(longd1;d*dn;d){if(n%d0){sumd;if(d*d!n)sumn/d;}}returnsum-n;}// 素因子分解边试除边报号staticStringfactorize(longn){StringBuildersbnewStringBuilder();longrestn;for(longd2;d*drest;d){while(rest%d0){if(sb.length()0)sb.append( x );sb.append(d);rest/d;}}if(rest1){if(sb.length()0)sb.append( x );sb.append(rest);}returnsb.toString();}publicstaticvoidmain(String[]args){// 一、完全数判定扫一遍 1 到 10000真因数之和等于自己的站出来StringBuilderperfectnewStringBuilder();for(longn2;n10000;n){if(sumProperDivisors(n)n)perfect.append(n).append( );}System.out.println(perfect up to 10000: perfect.toString().trim());// 二、欧几里得-欧拉一线穿p 取 2 到 312^p-1 是素数的按公式造完全数再验一遍for(longp2;p31;p){longm(long)Math.pow(2,p)-1;// 梅森数if(isPrime(m)){longbuilt(long)Math.pow(2,p-1)*m;// 欧几里得给的形式longchecksumProperDivisors(built);// 最后一行要算十几秒等它System.out.println(pp 2^p-1m is prime, built built, proper divisor sum check(checkbuilt? (perfect): (NOT perfect)));}}// 三、欧几里得的构造前十个素数连乘加一除以每个素数都该余一再找出它藏的素因子long[]primes{2,3,5,7,11,13,17,19,23,29};longproduct1;for(longq:primes)product*q;longcandidateproduct1;StringBuilderremaindersnewStringBuilder();for(longq:primes)remainders.append(candidate%q).append( );System.out.println(product of first ten primes 1 candidate);System.out.println(remainder by each of the ten: remainders.toString().trim());System.out.println(factorization: factorize(candidate));// 四、梅森的表走错在哪里p 是素数2^p-1 未必是素数System.out.println(2^11 - 1 ((long)Math.pow(2,11)-1) factorize((long)Math.pow(2,11)-1));System.out.println(2^23 - 1 ((long)Math.pow(2,23)-1) factorize((long)Math.pow(2,23)-1));// 五、给下一夜的钩220 的真因数之和是谁284 的真因数之和又是谁System.out.println(proper divisor sum of 220 sumProperDivisors(220));System.out.println(proper divisor sum of 284 sumProperDivisors(284));}}实跑输出如下。perfect up to 10000: 6 28 496 8128 p2 2^p-13 is prime, built 6, proper divisor sum 6 (perfect) p3 2^p-17 is prime, built 28, proper divisor sum 28 (perfect) p5 2^p-131 is prime, built 496, proper divisor sum 496 (perfect) p7 2^p-1127 is prime, built 8128, proper divisor sum 8128 (perfect) p13 2^p-18191 is prime, built 33550336, proper divisor sum 33550336 (perfect) p17 2^p-1131071 is prime, built 8589869056, proper divisor sum 8589869056 (perfect) p19 2^p-1524287 is prime, built 137438691328, proper divisor sum 137438691328 (perfect) p31 2^p-12147483647 is prime, built 2305843008139952128, proper divisor sum 2305843008139952128 (perfect) product of first ten primes 1 6469693231 remainder by each of the ten: 1 1 1 1 1 1 1 1 1 1 factorization: 331 x 571 x 34231 2^11 - 1 2047 23 x 89 2^23 - 1 8388607 47 x 178481 proper divisor sum of 220 284 proper divisor sum of 284 220这一夜的回信就写到这里。判决没有落笔鹅卵石还在桌上下一夜我们去见两个互相数着对方的数。① 真伪核对逐条照实登记。Ⅰ 毕达哥拉斯学派与希帕索斯 公元前 6 世纪学派以数为信仰鹅卵石摆数为其研究方式6 与 28 的完全数崇拜系教义真数学史通行记载正方形对角线不可公度归名希帕索斯溺海系传说无一手史料传说登记本夜翻案角度为作者判词。Ⅱ 欧几里得 《几何原本》素数无穷的归谬证明与卷九命题 36若 $2^{p}-1$ 为素数则 $2^{p-1}(2^{p}-1)$ 为完全数均为原书内容真通行记载。Ⅲ 奥古斯丁 《上帝之城》卷十一章 30六自身完美故上帝取六天创世若创世未曾发生六依然完美真已联网核查 New Advent 英译月亮约 28 天完成周期系其当时口径现代朔望月 29.5 天已在文中标注。Ⅳ 梅森 1644 年《Cogitata Physico-Mathematica》前言开列名单 p2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257其中 M67 与 M257 后证为合数M61、M89、M107 为素数而漏列名单 20 世纪中叶全部厘清真已联网核查。Ⅴ 欧拉 1772 年证明 $2^{31}-12147483647$ 为素数利用除数必为 2kp1 形态等数论工具缩小范围该纪录保持至 1883 年 M61时年 65 岁真已联网核查。偶完全数必为 $2^{p-1}(2^{p}-1)$ 形式的证明归欧拉真通行记载与欧几里得的充分性合称欧几里得-欧拉定理。Ⅵ 科尔 1903 年 10 月 31 日美国数学会纽约会议科尔无言在黑板上展示 $2^{67}-1193707721\times761838257287$被问用时答三年的星期天真已联网核查。Ⅶ GIMPS 第 52 个梅森素数 $2^{136279841}-1$41,024,320 位2024 年 10 月 12 日由 Luke Durant 发现系首个以 GPU 算力发现的梅森素数真已联网核查。Ⅷ 皮亚诺与三次危机 1889 年《算术原理》拉丁文发表自然数公理原著从 1 起步从 0 起步为后来约定真已联网核查三次危机即 √2 不可公度、无穷小之辩贝克莱 1734、罗素悖论 1902系教科书通行叙事真已联网核查。Ⅸ 奇完全数 是否存在未决Ochem 与 Rao 2012 年证明奇完全数若存在必大于 $10^{1500}$ 且至少 101 个素因子真已联网核查。Ⅹ 演示件 Night18Verdict 五路实跑完全数扫描、欧几里得-欧拉验证至第 8 个、欧几里得构造、梅森反例、220 与 284 互数输出与文中一致真JDK 21 实跑验证。② 术语对照卡本夜新增三条定义不含比喻。Ⅰ 完全数 真因数之和等于自身的自然数如 6 与 28。偶完全数均为 $2^{p-1}(2^{p}-1)$ 的形式且 $2^{p}-1$ 为素数奇完全数是否存在未决。Ⅱ 梅森数与梅森素数 形如 $2^{p}-1$ 的数称梅森数其中为素数的称梅森素数。p 为素数是必要条件而非充分条件。Ⅲ 后继 皮亚诺公理中每个自然数后面紧跟着的那个数。零不是任何数的后继从零出发沿后继可遍历全部自然数。③ 今夜习题三道评论区见。Ⅰ 把前十个素数 2357111317192329 全部乘起来再加一。先笔算它除以这十个素数余数各是几。再写程序把它的素因子全部找出来看看在不在原来的名单里。Ⅱ p 是素数$2^{p}-1$ 就一定是素数吗。写程序检验 $2^{11}-12047$ 和 $2^{23}-18388607$把它们分解开。Ⅲ 写出 220 的全部真因数求和看看得到什么数。再把那个数的全部真因数求和看看回到了哪里。本书目录导航上一篇第十七夜 长街点灯 下一篇第十九夜 数字王国的另一个我 起点卷首语·算法童话版权声明本文为作者原创受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作个人学习引用请注明作者与原文出处。转载授权请联系作者CSDN 私信。侵权必究。