判断素数的5种方法(素数的魅力)

判断素数的5种方法(素数的魅力)(1)

[遇见数学翻译小组] 核心成员: 柠檬酸菜鱼, 英文: https://dwz.cn/wbVWCr6i

这些不可拆分的素数依然不断展现出新的数学奥秘。

2018 年 3 月 20 日挪威科学与文学院宣布,将该年度阿贝尔奖授予美籍加拿大数学家罗伯特·朗兰兹(Robert Langlands),以表彰他在数学领域所作出的终身成就。他提出的最终以他名字命名的数学理论“朗兰兹纲领”(Langlands program),通过与素数的共同联系将几何学、代数学和分析学等概念结合起来,在数学的众多分支领域之间架起了“桥梁”。

判断素数的5种方法(素数的魅力)(2)

罗伯特·朗兰兹,著名的朗兰兹纲领的提出者。1996年他获得了沃尔夫奖。在2007年获得了邵逸夫奖数学科学奖。2018年获得阿贝尔奖。

当时挪威国王将为朗兰兹颁奖,致敬这项最新的科研成果。素数,可以说是数学领域中最庞大、最古老的数据集,数学家们历经 2300 年的努力一直在不断探索它的奥秘。那么是什么吸引无数杰出的数学家,数千年来前仆后继地投身于素数研究中?

寻找素数的历程

为了研究素数,数学家们将正整数通过素数筛选算法,直至仅剩素数保留下来。在 19 世纪,用试除法来筛选获得了数百万以内的素数列表。当然,现代计算机可以在不到一秒钟的时间内找出数十亿以内的素数,但所用筛法的核心思想 2000 年来从未改变。

公元前 300 年,亚历山大里亚的数学家欧几里得描述到:“素数是只能用 1 来计数的数。”这意味着素数不能被除了 1 以外的任何小于自身的数整除。并且为了保证整数的唯一分解,数学家们并不把 1 看作素数。此外,欧几里得还证明了素数的个数是无限的、没有穷尽。

公元前 200 左右,古希腊数学家埃拉托斯特尼(Eratosthenes)提出了素数的快速筛选法,这是一种简单且历史久远的筛法,用来找出一定范围内所有的素数。

判断素数的5种方法(素数的魅力)(3)

在 2~100 范围内进行 2,3,5,7 筛选后留下的所有素数

埃拉托斯特尼素数筛法的思路是这样的:首先,留下 2 ,把 2 的倍数都划掉;2 后面第一个没划去的数是 3 ,留下 3 ,把 3 的倍数都划掉;然后留下 5 ,把 5 的倍数都划掉;再留下 7 ,把 7 的倍数都划掉。如此这般,将最小的四个质数——2,3,5,7——的倍数依次筛掉。此时,下一个未被筛掉 11 的平方已经大于 100,所以停止。这样在 2 到 100 之间的整数只执行这 4 次筛选,最终只留下了素数集合。

从 1 ~ 100 之间的数字中筛除 2, 3, 5 和 7 的倍数,留下就是素数 通过 8 次筛选步骤,可以分离出 400 以内的全部素数。通过 168 次筛选,可以分离出 100 万以内的全部素数。这便是埃氏筛法的强大之处。

为素数制表的早期代表人物是英国数学家约翰·佩尔(John Pell),他致力于将有用的数字制成表格。其研究动力来源于对古希腊数学家丟番图(Diophantos) 所提出的古老算术问题的研究热情,还来自于对数学真理进行系统整合的个人追求。由于他的不懈努力,在 18 世纪早期 10 万以内的素数得以广泛传播。截止 1800 年,各种独立的研究项目列出了百万以内的全部素数。

判断素数的5种方法(素数的魅力)(4)

从左至右, 1611-1685 英国数学家约翰·佩尔,1741-1808 德国数学家卡尔·弗里德里希·兴登堡,1793-1863 奥地利数学家雅各布·菲利普·库利克

为了将这项繁琐的筛选工作自动化,德国数学家卡尔·弗里德里希·兴登堡 (Carl Friedrich Hindenburg)使用一种可调节的滑块,可以一次性排除整张纸上的所有倍数。另一种技术含量低却高效的方法是使用模版来定位特定素数的倍数。到19世纪中叶,数学家雅各布·库利克(Jacob Kulik)开展了一项雄心勃勃的项目:找出 1 亿以内的所有素数。但直至库利克逝世,这些工作还没有完成,不过已经找出来的素数填满了 4212 页表格.

如果不是"数学王子"高斯(Carl Friedrich Gauss)决定对素数自身进行分析整理,19 世纪这样一套“大数据”的结果可能也仅限于用作素数参考表。

17 世纪,对数表的诞生大大推动了天文、航海的蓬勃发展。一本作为给高斯生日礼物的对数工具书后附录了一张300万以内的素数表,这个在旁人看起来无实际用途的表格却激发了他的强烈兴趣。他开始着手进行数据分析统计工作。

他每次以 1000 个数为一组,分别计数这一范围内素数的个数。先计数 1000 以内素数的个数,接着是 1001 到 2000 之间,然后是 2001 到 3000 之间,以此类推,高斯开始探索这个在旁人看来毫无乐趣的素数列表。

高斯发现,随着数值增大,素数出现的频率会逐渐降低,遵循“反对数”定律。虽然高斯的素数分布定理并没有算出素数数目的精确值,但他给出了一个非常好的近似值。例如,根据素数定理预测在 1000000 到 1001000 之间存在 72 个素数,而正确结果是 75,误差在 4% 左右。这令他提出一个猜想:,其中 为不大于 x 的素数个数。也就说当 x 趋近无限时,有下式成立:

而在这个猜想提出一个世纪之后,这个称之为素数定理(prime number theorem)才得到了证明。

判断素数的5种方法(素数的魅力)(5)

π(x), x/lnx 和 π(x)/(x/lnx) 的比较

随着素数计数范围越来越大,估计值与真实值的相对误差将趋近于 0。悬赏百万奖金,位列当今数学界七大难题之一的黎曼猜想(Riemann hypothesis),也描述了高斯定理估算的精确程度。

素数定理和黎曼猜想已经得到了人们的广泛关注,但它们在早期,都是从枯燥的素数表数据分析开始的。现在,我们获取数据的方式都来自于计算机程序的运算,不再需要手算筛选,但数学家们仍在寻找素数研究的新模式。除了 2 和 5 之外,所有素数都以 1,3,7 或 9 结尾。19 世纪,人们发现这几个末位数字在素数中存在相同的出现频率。换句话说,如果你计数到 100 万,25%的素数末位为 1,25% 末位为 3,25% 末位为 7,25% 末位为 9。

对素数末位数字的分析

除了 2 和 5 之外,所有素数都以 1,3,7 或 9 结尾。19 世纪,人们发现这几个末位数字在素数中存在相同的出现频率。

判断素数的5种方法(素数的魅力)(6)

图表来自:The Conversation, CC-BY-ND,作者Martin Weissman

几年前,斯坦福大学的数论学家莱姆克·奥利弗(Lemke Oliver) 和坎南·桑德拉贾恩(Kannan Soundararajan)在实验中观察素数及其下一个相邻素数的末位数字规律,意外发现了一个问题。例如,23 之后的素数是 29,它们的末位数字是前 3 后 9。那么,相邻两个素数的末位数字,是前 3 后 9 常见,还是前 3 后 7 常见呢?

判断素数的5种方法(素数的魅力)(7)

100 万以内的连续素数末位数字对出现的频率。相同颜色代表末位数字对具有相同的间距值。(M.H. Weissman, CC BY)

数论学家们预计会存在一些差异,但实验结果远超预期。将相邻素数末位数字对按照间距不同进行分组,譬如,23 与 29 间距为 6。结果发现,像 23 和 29 这样前 3 后 9 的素数对儿的占比,超过先 7 后 3 的素数对儿占比,尽管两种情况中相邻素数对儿的间距都为 6。虽然数学家们很快给出了一种较为可信的解释。但是,当涉及到连续素数的研究时,数学家们大部分还局限在分析数据进而寻找合理解释的阶段,距离揭示真相的唯一标准——数学上证明,似乎还需要很长一段路要走。

判断素数的5种方法(素数的魅力)(8)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页