数学家解决了42的丢番图难题,顺便回答了生命的意义[转]

在道格拉斯·亚当斯的科幻系列小说《银河系漫游指南》中,程序员向这台银河系最大的超级计算机提出了一个终极问题:生命、宇宙和一切的意义。经过750万年的处理,计算机得出了一个答案:42。

2019年,两位数学家使用了一个由50万台计算机组成的全球网络来解决一个百年前的数学难题,这个难题恰好包含了最关键的数字:42。

这个问题至少可以追溯到1955年,并且可能早在公元三世纪希腊思想家就开始思考这个问题了。这个问题是:你怎么把1到100之间的每一个数字表示为三个整数的立方的总和?或者用代数的方法表示,如何解x^3+y^3+z^3=k,其中k等于1到100之间的任何整数?

这个看似简单的难题被称为丢番图方程,以亚历山大的古代数学家丢番图命名,他在1800年前提出了一组类似的问题。

20世纪50年代重温这一难题的现代数学家很快找到了答案,当时k等于许多较小的数,但很快就出现了一些特别顽固的整数。最棘手的两个数字,分别是33和42。

今年4月,英国布里斯托尔大学数学家安德鲁·布克(Andrew Booker)解决了33难题。布克用一种计算机算法寻找x、y和z值在正负99万亿之间的丢番图方程的解,经过数周的计算后,找到了33的解。如你所见,答案是超长的。

8866128975287528^3-8778405442862239^3-2736111468807040^3=33

尽管如此,这一详尽的搜索仍然没有找到42的解。这表明如果解存在,一些整数必须大于99万亿。计算这么大的数值需要极大的计算能力,因此在他的下一次尝试中,布克请求麻省理工学院数学家安德鲁·萨瑟兰(Andrew Sutherland)的帮助,他帮助布克在一个名为慈善引擎(Charity Engine)的全球计算机网络上预定了一段时间。

根据布里斯托尔大学的一份声明,这个网络是一个“世界性的计算机”,它借用了全球50多万台家用电脑的闲置计算能力。利用这台众包的超级计算机和100万小时的处理时间,布克和萨瑟兰最终找到了k = 42的丢番图方程的答案。

所以,直截了当地说,生命、宇宙和一切事物的意义的问题和答案是:(-80538738812075974)^3+(80435758145817515)^3+ (12602123297335631)^3 = 42。

Rust 内置 trait:PartialEq 和 Eq

如果我们想比较某个类型的两个值 x 和 y 是否相等(不等),例如:x == y (x != y),那么我们就必须为类型实现 PartialEq Trait

PartialEq 可使用 #[derive] 来交由编译器实现,当一个 struct 在进行相等比较时,会对其中每一个字段进行比较;如果遇到枚举时,还会对枚举所拥有的数据进行比较。

我们也可以自己实现 PartialEq,实现时只需要实现判断是否相等的函数 
fn eq(&self, other: &Self) -> bool ,Rust 会自动提供 fn ne(&self, other: &Self) -> bool

实现 Eq 的前提是已经实现了 PartialEq,因为实现 Eq 不需要额外的代码,只需要在实现了PartialEq 的基础上告诉编译器它的比较满足自反性就可以了。对于上面的例子只需要:#[derive(Eq)] 或 impl Eq for Book {}

PartialEq 和 Eq

这两个 Traits 的名称实际上来自于抽象代数中的等价关系和局部等价关系。

等价关系(equivalence relation)即设 R 是某个集合 A 上的一个二元关系。若 R 满足以下条件:

  1. 自反性:∀xA,  xRx
  2. 对称性:∀x,yA,  xRy  ⟹  yRx
  3. 传递性:xRz∀x,y,zA,   (xRy  ∧  yRz)  ⟹  xRz

则称 R 是一个定义在 A 上的等价关系

并非所有的二元关系都是等价关系, Eq 和 PartialEq 的区别在于是否在相等比较中是否满足自反性,即 x == x

例如对于浮点类型,Rust 只实现了 PartialEq 而没有实现 Eq,原因在于 NaN != Nan,不满足自反性。

Eq 相比 PartialEq 需要额外满足自反性,即 a == a,对于浮点类型,Rust 只实现了 PartialEq 而不是 Eq,原因就是 NaN != NaN

Eq 和 Hash

当一个类型同时实现了 Eq 和 Hash 时,该类型满足下列特性:

k1 == k2 -> hash(k1) == hash(k2)

即,当两个 key 相等时,它们的哈希值必然相等。Rust 里的 HashMap 和 HashSet 都依赖该特性。