跳转到导航 跳转到搜索 数学中的猜想，从任何正整数 n 开始，如果将其减半（如果是偶数）或将其三倍并加上 1（如果是奇数）并无限重复，那么最终会得到 1 Collatz 猜想是数学中的一个关于序列的猜想，定义如下：从任何正整数 n 开始。那么每一项都是从前一项得到的，如下：如果前一项是偶数，那么下一项是前一项的一半。如果前一项是奇数，则下一项是前一项的 3 倍加 1。猜想是无论 n 的值是多少，序列总是会达到 1。该猜想以 Lothar Collatz 命名，他在1937 年，即获得博士学位两年后。 [1] 它也被称为 3 n + 1 问题、3 n + 1 猜想、乌拉姆猜想（根据 Stanisław Ulam）、角谷的问题（根据 Shizuo Kakutani）、思韦茨猜想（根据 Bryan Thwaites 爵士）、哈斯的猜想算法（在 Helmut Hasse 之后），或 Syracuse 问题。 [2] [4] 所涉及的数字序列有时被称为冰雹序列或冰雹数字（因为这些值通常会受到多次下降和上升的影响，就像云中的冰雹一样），[5] [6] 或称为奇妙数字。 [7] Paul Erdős 谈到 Collatz 猜想时说：“数学可能还没有为这些问题做好准备。” [8] 他还提供了 500 美元的解决方案。 [9] 杰弗里·拉加里亚斯 (Jeffrey Lagarias) 在 2010 年表示，科拉茨猜想“是一个非常困难的问题，完全超出了当今数学的范围。” [10] f ( n ) = { n 2 if n ≡ 0 ( mod 2 ) 3 n + 1 if n ≡ 1 ( mod 2 ) 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}}\\[4px]3n+ 1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}} 现在通过重复执行此操作形成一个序列，从任何正整数开始，并在每一步取结果作为下一个的输入。 ai = { n for i = 0 f ( ai − 1 ) for i > 0 {\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0\\f(a_{i -1})&{\text{for }}i>0\end{cases}}}
（即：ai 是 f 的值以递归方式应用于 n 次；ai = fi( n)）。 Collatz 猜想是：无论最初选择哪个正整数，这个过程最终都会达到数字 1。如果猜想是错误的，那只能是因为有某个起始数产生了一个不包含1的序列。这样的序列要么进入一个不包含1的重复循环，要么无限增加。没有发现这样的序列。使 ai < a 0 的最小 i 称为 n 的停止时间。类似地，使 k = 1 的最小 k 称为 n 的总停止时间。 [3] 如果索引 i 或 k 中的一个不存在，我们分别说停止时间或总停止时间是无限的。 Collatz 猜想断言每个 n 的总停止时间是有限的。也相当于说每一个n≥2都有一个有限的停止时间。由于 3 n + 1 在 n 为奇数时为偶数，因此可以改用 Collatz 函数的“捷径”形式： f ( n ) = { n 2 if n ≡ 0 ( mod 2 ) , 3 n + 1 2 if n ≡ 1 ( mod 2 ) 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{ \frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}} 这个定义产生了更小的停止时间和总停止值时间而不会改变过程的整体动态。
例如，从 n = 12 开始，可以得到序列 12, 6, 3, 10, 5, 16, 8, 4, 2, 1。数 n = 19 需要更长的时间才能达到 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. n = 27 的序列，在下面列出和绘制，需要 111步骤（41 步通过奇数，斜体），上升到 9232，然后下降到 1。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, 7, 3, 5, 9, 8 20 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 49, 81, 37, 95 8 18 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 4, 6, 3, 5, 6, 7, 3, 5, 30, 3, 5, 30 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (序列884 A OEIS) 总停止时间更长的数字比任何更小的起始值形成一个以下列开头的序列：1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703 , 871, 1161, 2223, 2463, 2919, 3711, 6171, ...（OEIS 中的序列 A006877）。最大轨迹点大于任何较小起始值的起始值如下：
1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 60975, 71761, 37, 65, 610, 717, 87 17, 87 17, 37, 87 17 ...（OEIS 中的序列 A006884）0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 1 16, 104, 11, 24, 24, ...（OEIS 中的序列 A006577）这些数字是指示步数的最低数字，但不一定是低于给定限制的唯一数字。例如，9 780 657 631 有 1132 个步骤，9 780 657 630 也是如此。 相对于其位数（以 2 为底）具有最小总停止时间的起始值是 2 的幂，因为 2 n 减半n 次达到 1，并且永远不会增加。 x 轴代表起始数，y 轴代表在链到 1 期间达到的最高数。该图显示了一个受限的 y 轴：一些 x 值产生高达 2.7 × 10 7 的中间值（对于 x = 9663） 尽管猜想尚未得到证实，大多数研究该问题的数学家认为该猜想是正确的，因为实验证据和启发式论证支持它。截至 2020 年，该猜想的所有起始值均已通过计算机验证，最高可达 2 68 ≈ 2.95×10 20。迄今为止测试的所有初始值最终都以第 3 期的重复循环 (4;2;1) 结束。 [13 ]
该计算机证据不足以证明该猜想对于所有起始值都成立。对于一些被推翻的猜想，如波利亚猜想，在考虑非常大的数字时可能会发现反例。但是，此类验证可能具有其他含义。例如，可以推导出对非平凡循环的周期和结构形式的额外约束。 [14] [15] [16] 如果只考虑由 Collatz 过程生成的序列中的奇数，那么每个奇数平均是前一个的 3 / 4。 [17]（更准确地说，结果比率的几何平均值是 3 / 4。）这产生了一个启发式论证，即从长远来看，每个冰雹序列都应该减少，尽管这不是反对其他周期的证据，只是反对分歧。该论点不是证明，因为它假设冰雹序列是由不相关的概率事件组装而成的。 （它确实严格地证明了 Collatz 过程的 2-adic 扩展对于几乎所有 2-adic 起始值的每个乘法步骤都有两个除法步骤。）正如 Terras 所证明的那样，几乎每个正整数 n 都有一个有限的停止时间。 [18] 换句话说，几乎每个 Collatz 序列都会达到一个严格低于其初始值的点。证明基于奇偶向量的分布并使用中心极限定理。在 2019 年，Terence Tao 通过使用对数密度显示几乎所有 Collatz 轨道都下降到起点的任何给定函数以下，从而大大改进了这一结果，前提是该函数发散到无穷大，无论多慢。在回应这项工作时，《量子》杂志写道，陶“得出了几十年来关于科拉茨猜想的最重要的结果之一”。 [19] [20] 在计算机辅助证明中，Krasikov 和 Lagarias 表明，对于所有足够大的 x，区间 [1, x] 中最终达到 1 的整数数量至少等于 x 0.84。 [21] f ( n ) = { n 2 if n ≡ 0 ( mod 2 ) , 3 n + 1 2 if n ≡ 1 ( mod 2 ) 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{ \frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}
循环是不同正整数的序列 ( a 0, a 1, ..., aq) 其中 f( a 0) = a 1, f( a 1) = a 2, ..., and f( aq) = a 0。已知非平凡循环的长度至少为 17 087 915。 [15] 事实上，Eliahou (1993) 证明了任何非平凡循环的周期 p 的形式如下： b 和 c 是非负整数，b ≥ 1 且 ac = 0。这个结果是基于 ln 3 / ln 2 的连分数展开。一个类似的推理解释了最近对 2 68 导致的猜想的验证到改进的下限 114 208 327 604（或没有“快捷方式”的 186 265 759 595）。这个下界与上面的结果是一致的，因为 114 208 327 604 = 17 087 915 × 361 + 85 137 581 × 1269。一个 k 循环是一个可以划分成 2 k 个连续子序列的循环： k 个奇数递增序列数字与 k 个递减的偶数序列交替。 [16] 例如，如果循环由单个递增的奇数序列和递减的偶数序列组成，则称为 1 循环。 Steiner (1977) 证明除了平凡的 (1;2) 之外没有 1 循环。 [22] Simons (2004) 使用 Steiner 的方法证明不存在 2-cycle。 [23] Simons & de Weger (2005) 将这个证明扩展到 68 个循环：没有 k 循环直到 k = 68。 [16] 对于每个超过 68 的 k，该方法给出了最小项的上限k-循环的：例如，如果有一个77-循环，那么循环的至少一个元素小于38137 × 2 50。 [16] 随着猜想的验证达到2 68，这意味着直到 k = 77 的非平凡 k 循环不存在。 [13] 随着详尽的计算机搜索继续进行，可能会排除更大的 k 值。为了更直观地陈述这个论点：我们不需要寻找最多有 77 个回路的周期，其中每个回路由连续的上升和连续的下降组成。还有另一种证明猜想的方法，它考虑了增长所谓的 Collatz 图的自下而上的方法。 Collatz 图是由逆关系定义的图
R ( n ) = { { 2 n } 如果 n ≡ 0 , 1 , 2 , 3 , 5 { 2 n , n − 1 3 } 如果 n ≡ 4 ( mod 6 ) 。 {\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n, {\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.} 所以，与其证明所有正整数最终导致 1，我们可以尝试证明 1 向后导致所有正整数。对于任何整数 n，n ≡ 1 (mod 2) 当且仅当 3 n + 1 ≡ 4 (mod 6)。等价地，n − 1 / 3 ≡ 1 (mod 2) 当且仅当 n ≡ 4 (mod 6)。推测地，这种逆关系形成了一棵树，除了 1-2-4 循环（本文问题陈述部分中定义的未改变函数 f 的 4-2-1 循环的逆）。当函数 f 的关系 3 n + 1 被常见的替代“捷径”关系 3 n + 1 / 2 代替时，Collatz 图由逆关系定义，R ( n ) = { { 2 n } if n ≡ 0 , 1 { 2 n , 2 n − 1 3 } 如果 n ≡ 2 ( mod 3 ) 。 {\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1\\[4px]\left\{2n,{\frac {2n- 1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.} 对于任何整数 n，n ≡ 1 (mod 2) 如果并且仅当 3 n + 1 / 2 ≡ 2 (mod 3) 时。等价地，2 n − 1 / 3 ≡ 1 (mod 2) 当且仅当 n ≡ 2 (mod 3)。推测，除了 1-2 循环（如上所述修改的函数 f(n) 的 1-2 循环的逆）之外，这种逆关系形成一棵树。或者，将 3 n + 1 替换为 n' / H( n')，其中 n' = 3 n + 1 并且 H( n') 是除 n' 的 2 的最高幂（没有余数）。结果函数 f 从奇数映射到奇数。现在假设对于某个奇数 n，应用此操作 k 次产生数字 1（即 fk(n) = 1）。然后在二进制中，数字 n 可以写成字符串 wkwk−1 … w 1 的串联，其中每个 wh 是从 1 / 3 h 的表示中提取的有限且连续的提取物。 [24] 因此，n 的表示包含 1 / 3 h 的重复次数，其中每个重复次数都可以选择旋转，然后复制到有限位数。只有在二进制中才会发生这种情况。 [25] 根据推测，每个以“1”结尾的二进制字符串 s 都可以通过这种形式的表示（我们可以在其中添加或删除前导“0”到 s）。 Collatz 函数的重复应用可以表示为处理位串的抽象机器。机器将对任意奇数执行以下三个步骤，直到只剩下一个“1”：
将 1 附加到二进制数的（右）端（给出 2 n + 1）；通过二进制加法将其与原始数字相加（给出 2 n + 1 + n = 3 n + 1）；起始数字 7 以 2 为底数写为 111。由此产生的 Collatz 序列是： f ( n ) = { n 2 if n ≡ 0 3 n + 1 2 if n ≡ 1 ( mod 2 ) 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{ 2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}.} 这是可以做到的，因为当 n 是奇数时，3 n + 1 总是偶数。如果 P(…) 是一个数的奇偶校验，即 P(2 n) = 0 和 P(2 n + 1) = 1，那么我们可以将数 n 的 Collatz 奇偶校验序列（或奇偶向量）定义为pi = P(ai)，其中 a 0 = n，a i+1 = f( ai)。执行哪种操作，3 n + 1 / 2 或 n / 2，取决于奇偶校验。奇偶校验序列与操作序列相同。
使用 f(n) 的这种形式，可以证明两个数 m 和 n 的奇偶校验序列在前 k 项中一致当且仅当 m 和 n 模 2 k 是等效的。这意味着每个数字都由其奇偶校验序列唯一标识，而且如果有多个冰雹周期，则它们对应的奇偶校验周期必须不同。 [3] [18] 将 f 函数应用于 n = 2 ka + b 将得到结果 3 ca + d，其中 d 是将 f 函数应用于 b 的结果，c 是多少在该序列中遇到了增加（例如，对于 2 5 a + 1，有 3 次增加，因为 1 迭代到 2、1、2、1，最后到 2，所以结果是 3 3 a + 2；对于 2 2 a + 1当 1 上升到 2 并下降到 1 时，只有 1 增加，所以结果是 3 a + 1）。当 b 为 2 k − 1 时，k 上升，结果为 2 × 3 ka − 1。3 乘以 a 的因数与 a 的值无关；它只取决于 b 的行为。这允许人们预测某些形式的数字在经过一定次数的迭代后总是会导致较小的数字，例如 4 a + 1 在两次应用 f 后变为 3 a + 1 并且 16 a + 3 在经过两次应用后变为 9 a + 2 f. 4 应用然而，这些较小的数字是否继续为 1 取决于 a 的值。 f ( n ) = { n 2 if n ≡ 0 3 n + 1 2 if n ≡ 1. ( mod 2 ) {\displaystyle f(n)={\begin{cases}{\frac {n}{2}} &{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1.\end{cases}}{\ pmod {2}}} 在这个系统中，正整数 n 由 a 的 n 个副本组成的字符串表示，标签操作的迭代在长度小于 2 的任何单词上停止。（改编自 De Mol。）Collatz猜想等效地指出，这个标签系统，以一个任意有限字符串 a 作为初始词，最终会停止（参见标签系统#Example: Computation of Collatz sequence for a work example）。 Collatz 猜想的一个扩展是包括所有整数，而不仅仅是正整数。撇开无法从外部进入的循环 0 → 0，共有 4 个已知循环，所有非零整数似乎最终都落入 f 的迭代中。此处列出了这些循环，从众所周知的正 n 循环开始：奇数值以大粗体列出。每个循环首先列出其绝对值最小的成员（总是奇数）。
−5 → −14 → −7 → −20 → −10 → −5 ... −17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ... 广义 Collatz 猜想是这样的断言，即每个整数在 f 的迭代下，最终落入上面的四个循环或循环 0 → 0。0 → 0 循环通常被论证认为是“微不足道的”，因为它只是为了完整性而被包含在内。 Collatz 映射可以扩展到（正或负）有理数，这些有理数在以最低术语书写时具有奇数分母。根据其分子是奇数还是偶数，该数字被视为“奇数”或“偶数”。那么映射的公式与域为整数时的公式完全相同：一个“偶数”这样的有理数除以 2；一个“奇数”这样的有理数乘以 3，然后加 1。一个密切相关的事实是 Collatz 映射扩展到 2-adic 整数环，其中包含具有奇分母的有理数环作为子环。当使用 Collatz 映射的“快捷方式”定义时，众所周知，任何周期性奇偶校验序列都是由恰好一个有理数生成的。 [26] 相反，可以推测每个具有奇分母的有理数都有一个最终循环的奇偶校验序列（周期猜想 [3]）。如果一个奇偶循环的长度为 n 并且在索引 k 0 < ⋯ < km−1 处包含恰好 m 次的奇数，那么立即和周期性地生成这个奇偶循环的唯一有理数是 3 m − 1 2 k 0 +⋯ + 3 0 2 km − 1 2 n − 3 m 。 {\displaystyle {\frac {3^{m-1}2^{k_{0}}+\cdots +3^{0}2^{k_{m-1}}}{2^{n}-3 ^{m}}}。}
例如，奇偶校验周期 (1 0 1 1 0 0 1) 的长度为 7，在索引 0、2、3 和 6 处有四个奇数项。它由分数 3 3 2 0 + 3 2 2 2 + 重复生成3 1 2 3 + 3 0 2 6 2 7 − 3 4 = 151 47 {\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1 }2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}} 151 47 → 250 47 . .....