Collatz 猜想也叫做 3 · n 1 问题。这可能是数学中最为世人所知的未解之谜。它是如此初等,连小学生都能听懂它的内容;但解决它却如此之难,以至于 Paul Erd?s 曾说:“或许现在的数学还没准备好去解决这样的问题。”这究竟是一个什么样的问题呢?让我们来看一下 Collatz 猜想的叙述: 任意取一个正整数 n 。如果 n 是奇数,则把 n 变为 3 · n 1 ;如果 n 是偶数,则把 n 变为 n/2 。不断重复操作,则最终一定会得到 1 。 举个例子,如果 n = 26 ,那么经过下面 10 步之后,它最终变为了 1 : 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 随便取一个其他的自然数,对它进行这一系列的变换,或迟或早,你总会掉到4→2→1这个循环中,或者说,你总会得到1。已经有人对所有小于100*2^50=112589990684262400的自然数进行验算,无一例外。Collatz 猜想说的就是,这个规律对于所有正整数 n 均是如此。 这个问题大约是在二十世纪五十年代被提出来的。在西方它常被称为西拉古斯(Syracuse)猜想,因为据说这个问题首先是在美国的西拉古斯大学被研究的;而在东方,这个问题由将它带到日本的日本数学家角谷静夫的名字命名,被称作角谷猜想。 这个问题看起来是如此简单,以至于无数的数学家都掉进了这个坑里。光从这个问题的众多别名,便能看出这个问题害人不浅: Collatz 猜想又叫做 Ulam 猜想、 Kakutani 问题、 Thwaites 猜想、 Hasse 算法、 Syracuse 问题……研究这个问题的人很多,解决这个问题的人却一个没有。后来,人们干脆把它叫做 3 · n 1 问题,让哪个数学家也不沾光。 角谷静夫在谈到这个猜想的历史时讲:'一个月里,耶鲁大学的所有人都着力于解决这个问题,毫无结果。同样的事情好象也在芝加哥大学发生了。有人猜想,这个问题是苏联克格勃的阴谋,目的是要阻碍美国数学的发展。'不过我对克格勃有如此远大的数学眼光表示怀疑。这种形式如此简单,解决起来却又如此困难的问题,实在是可遇而不可求。 数学家们已经发表了不少篇严肃的关于3 · n 1 问题的数论论文,对这个问题进行了各方面的探讨,可是这个问题的本身始终没有被解决,我们还是不知道,'到底是不是总会得到1?' 要是真的有这么一个自然数,对它反复作上面所说的变换,而我们永远也得不到1,那只可能有两种情况: 1)它掉到另一个有别于4→2→1的循环中去了。我们在后面可以看到,要是真存在这种情况,这样一个循环中的数字,和这个循环的长度,都会是非常巨大的; 2)不存在循环。也就是说,每次变换的结果都和以前所得到的所有结果不同。这样我们得到的结果就会越来越大(当然其中也有可能有暂时减小的现象,但是总趋势是所得的结果趋向无穷大)。 图片源自豆瓣 这个问题有多难呢?我们可以从下面的这个例子中略见一斑。虽然从 26 出发只消 10 步就能变成 1 ,但若换一个数,比如 27 ,情况就大不一样了: 27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 可见,当 n 的值不同时,从 n 变到 1 的路子是很没规律的。 有趣的是,如果我们把 Collatz 猜想中的乘以 3 改为乘以任意一个 3x (其中 x 的值可由你自由选择),那么 Collatz 猜想就是正确的了。下面我们就来证明这一点。
为什么对于任意的正整数 n ,我们总能找到一个 b ,使得 [n · 3b, (n 1) · 3b) 区间内包 含某个 2 的整数次幂呢? 在对数尺度下,这就化为了刚才讨论的问题。 [n × 30, n × 31), [n × 31, n × 32), [n × 32, n × 33), … 成为了一个个等长的区间,区间的长度都是 log(3) 。而 20, 21, 22, … 也就成了一系列的等距点,相邻两个点之间的距离是 log(2) 。如果把 log(3) 的长度看作 1 个单位,那么 log(2) 的长度就是 log(2) / log(3) = log32 个单位,这是一个无理数。这就完全相当于周长为 log32 的轮子沿着总长为 1 的圆形轨道滚动。根据刚才的结论,由此得到的标记将会稠密地分布在这些等长区间内的各种位置,当然也就会有不少标记落进了形如 [n · 3b, (n 1) · 3b) 的区间里。 via:Matrix67,百度百科 模型研究、文章投稿欢迎联系数模君: supermodeling@163.com |
|