如果把 3 · n + 1 问题改为 3^x · n + 1 问题

2016 年 5 月 2 日2016-05-03 / 53 条评论

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

Collatz 猜想说的就是，这个规律对于所有正整数 n 均是如此。这个问题看起来是如此简单，以至于无数的数学家都掉进了这个坑里。光从这个问题的众多别名，便能看出这个问题害人不浅： Collatz 猜想又叫做 Ulam 猜想、 Kakutani 问题、 Thwaites 猜想、 Hasse 算法、 Syracuse 问题……研究这个问题的人很多，解决这个问题的人却一个没有。后来，人们干脆把它叫做 3 · n + 1 问题，让哪个数学家也不沾光。

这个问题有多难呢？我们可以从下面的这个例子中略见一斑。虽然从 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 改为乘以任意一个 3^x （其中 x 的值可由你自由选择），那么 Collatz 猜想就是正确的了。下面我们就来证明这一点。

UyHiP 趣题：几乎所有数都能分解成若干个 3^x · 4^y 之和

2015 年 8 月 3 日2015-08-03 / 14 条评论

下面这个题目来自 2015 年 7 月的 Using your Head is Permitted 。假设集合 S 是由所有形如 3^x · 4^y 的数构成的，其中 x 和 y 都是非负整数。因而，集合 S 是一个无穷集合，其中最小的几个元素依次为 1, 3, 4, 9, 12, 16, 27, … 。如果某个正整数 n 能表示成集合 S 中的一个或多个不重复的数之和，我们就说 n 是集合 S 的一个子集和。例如， 23 就是 S 的一个子集和，因为 23 可以表示成 3 + 4 + 16 。然而， 6 就不是 S 的一个子集和。

求证：除了有限多个正整数以外，其他所有的正整数都是集合 S 的子集和。

Sierpiński 的初等数论问题

2015 年 5 月 30 日2016-07-29 / 26 条评论

波兰数学家 Wacław Sierpiński 对数论有很多研究。在他一生出版的 50 多本书里， 250 Problems of Elementary Number Theory 一书显得格外有趣。这里面不但有各种出人意料的数学事实，还有很多精妙的证明和大胆的构造，让人大呼过瘾。我从中选择了一些问题，在这里和大家一块儿分享。下面的文字没有完全照搬书中的内容，而是做了大量的改动和扩展；若有出错的地方，还请大家指正。个别题目会涉及一些初等数论中的著名定理，它们都可以在这篇文章里找到。