考拉茲猜想

考拉茲猜想（英語：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，共有261個步驟； 數目少於10萬的，步驟中最高的數是77031，共有350個步驟； 數目少於100萬的，步驟中最高的數是837799，共有524個步驟； 數目少於1億的，步驟中最高的數是63728127，共有949個步驟； 數目少於10億的，步驟中最高的數是670617279，共有986個步驟。

研究歷史

在1930年代，德國漢堡大學的學生考拉茲，曾經研究過這個猜想。在1960年，日本人角谷靜夫也研究過這個猜想。但這猜想到目前，仍沒有任何進展。

保羅·艾狄胥就曾稱，數學上尚未為此類問題提供答案。他並稱會替找出答案的人獎賞500元。

目前已經有分布式計算在進行驗證。到2009年1月18日，已驗證正整數到 5 × 2⁶⁰ = 5,764,607,523,034,234,880，也仍未有找到例外的情況。但是這並不能夠證明對於任何大小的數，這猜想都能成立。

有的數學家認為，該猜想任何程度的解決都是現代數學的一大進步，將開闢全新的領域。目前也有部分數學家和數學愛好者，在進行關於「負數的3x＋1」、「5x＋1」、「7x＋1」等種種考拉茲猜想的變化形命題的研究。

2019年12月，陶哲軒證明只要$f(n)$是一個趨於正無窮的實數列，那麼幾乎對所有的正整數$n$ (在對數密度意義下) ，有$S(n)<f(n)$。

計算機驗證

Python

以下是這個猜想的Python版本代碼。它會在答案得到1時停下來，以避免作0→0這個無限循環。

def collatz(number):
    while number != 1:
        if number % 2 == 0:
            number = number // 2
        elif number % 2 == 1:
            number = number*3 + 1
        print(number)

collatz(int(input('輸入一個正整數')))

C語言

#include <stdio.h>

void collatz(unsigned int n){
  while(n > 1){
    printf("%u\t->\t", n);
    n = n & 1 ? n * 3 + 1 : n / 2;
  }
  printf("1");
}

Java

void collatz(int n){
  while(n > 1){
    System.out.print(n + "\t->\t");
    n = n % 2 == 0 ? n / 2 : n * 3 + 1;
  }
  System.out.print(1);
}

Visual Basic

Imports System
Imports System.Console

Public Sub Collatz(ByVal n As UInteger)
    System.Console.WriteLine(n)
    If n = 1 Then Exit Sub
    n = n * 3 + 1
    Do While(n Mod 2 = 0)       // remove all trailing '0's
      n /= 2
    Loop
    Call Collatz(n)
End Sub

JavaScript

function collatz(n) {
  while(n > 1)
    n = !(n % 2) ? n / 2 : n * 3 + 1;
}

golang

func collatz(num int) {
    for num != 1 {
        if (num % 2) == 1 {
            num = num*3 + 1
        } else {
            num = num / 2
        }
        println(num)
    }
}

shell

read -p "输入一个正整数：" num
function collatz()
{
    local n=$1
    while [ $n -ne 1 ]
    do
        [[ $(($n%2)) == 0 ]] && let n/=2 || let n=n*3+1 ; echo $n
    done
}
collatz $num

相關條目

• 3x + 1半群
• 模算數

外部連結

• 以電腦研究考拉茲猜想的網頁 頁面存檔備份，存於網際網路檔案館
• Collatz Conjecture的BOINC專案網頁 頁面存檔備份，存於網際網路檔案館