本页使用了标题或全文手工转换

考拉兹猜想

维基百科,自由的百科全书
跳转至: 导航搜索

奇偶归一猜想英语Collatz conjecture),又称为3n+1猜想冰雹猜想角谷猜想哈塞猜想乌拉姆猜想叙拉古猜想,是指对于每一个正整数,如果它是奇数,则对它乘3再加1,如果它是偶数,则对它除以2,如此循环,最终都能够得到1。

 f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}.

例子[编辑]

取一个正整数:

  • 如n = 6,根据上述数式,得出序列6, 3, 10, 5, 16, 8, 4, 2, 1。(步驟中最高的數是16,共有8個步驟)
  • 如n = 11,根据上述数式,得出序列11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。(步驟中最高的數是52,共有14個步驟)
  • 如n = 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 }(步驟中最高的數是9232,共有111個步驟)

奇偶归一猜想称,任何正整数,经过上述计算步骤後,最终都会得到1。

n = 27时的序列分布(横轴-步数;纵轴-运算结果)

數目少於1萬的,步驟中最高的數是6171; 數目少於1億的,步驟中最高的數是63728127,共有949個步驟; 數目少於10億的,步驟中最高的數是670617279,共有986個步驟。

研究历史[编辑]

在1930年代,德国汉堡大学的学生考拉兹,曾经研究过这个猜想。在1960年,日本人角谷静夫也研究过这个猜想。但这猜想到目前,仍没有任何进展。

保羅·艾狄胥就曾称,数学上尚未为此类问题提供答案。他并称会替找出答案的人奖赏500元。

目前已经有分布式计算在进行验证。到2009年1月18日,已验证正整数到 5 × 260 = 5,764,607,523,034,234,880,也仍未有找到例外的情况。但是这并不能够证明对於任何大小的数,这猜想都能成立。

有的数学家认为,该猜想任何程度的解决都是现代数学的一大进步,将开辟全新的领域。目前也有部分数学家和数学爱好者,在进行关于“负数的3x+1”、“5x+1”、“7x+1”等種種考拉兹猜想的變化形命題的研究。

计算机验证[编辑]

以下是这个猜想的计算机代码。它会在答案得到1时停下来,以避免作4→2→1这个无限循环。

def collatz(n)
  print n
  if n.odd? and n > 1
    collatz(3n + 1)
  else if n.even?
    collatz(n / 2)

外部連結[编辑]