一千萬個為什麽

搜索

關於Collat​​z問題的一個想法

我正在使用該功能的T版:

$$ T(x)=\left\{\begin{array}{cl} \text{down}(x)=x/2,& \mbox{x even}\\ \quad\,\,\,\text{up}(x)=(3x+1)/2,& \mbox{x odd}\end{array}\right. $$ I will also make use of the iterating function $G(x,0)=x,G(x,1)=T(x),G(x,2)=T(T(x)),...$

目標是了解T何時增加或減少它的論點。讓我們暫時解決一些$ n \ in \ mathbf {N} $常量並定義

$$ \ mathbf {A} = \ {2 ^ N + K,K = 0,1,\點,2 ^ N-1 \} $$

即從$ 2 ^ n $到$ 2 ^ {n + 1} -1 $的所有整數的集合。 現在讓我們將一個單詞定義為一個零序列和一個長度為$ n $的序列。最後讓我們用$ \ mathbf {W} $來表示所有不同單詞的集合。每個$ x \ in \ mathbf {A} $在$ \ mathbf {W} $中有一個“地址”,我們用$ path(x)$來表示,由

$$ path(x)= \ {x,T(x),G(x,2),... G(x,n-1)\} \ pmod {2} $$

現在這裏是一個妙語:$ \ mathbf {A} $的數字集和路徑函數給出的單詞$ \ mathbf {W} $之間有一個$ 1-1 $的對應關系。一旦我們確定我們將不得不處理單詞而不是數字,這些數字可能會提供更多信息。

怎麽表明?首先要註意兩個集合都有$ 2 ^ n $個元素。因此,如果我們可以證明路徑函數是可逆的,那麽我們就完成了。同樣地,每個單詞$ w \ in \ mathbf {W} $都有一個唯一元素$ a \ in \ mathbf {A} $ with $ path(a)= w $。等價$ path(a)= path(b)\ Rightarrow a = b $。這是我需要幫助的地方,因為這些單詞不是按標準順序排列的,它們會亂成一團!看一看:

對於$ n = 1 $:

$ \ mathbf {A} = \ {2,3 \} $,$ path(\ mathbf {A})= \ {0,1 \} $

對於$ n = 2 $:

$ \ mathbf {A} = \ {4,5,6,7 \} $,$ path(\ mathbf {A})= \ {00,10,01,11 \} $

對於$ n = 3 $:

$ \ mathbf {A} = \ {8,9,10,11,12,13,14,15 \} $,$ path(\ mathbf {A})= \ {000,101,010,110,001,100,011,111 \} $

我已經檢查了它最高$ 2 ^ 8 $並且它持有。沒有重復的話,所以我確信這是真的。

對於任何$ x \ in \ mathbf {N} $現在我們找到相應的$ n $(基本上是$ [\ log {x}] $),$ \ mathbf {A} $ set然後我們找到路徑,所以路徑函數是在所有$ \ mathbf {N} $上定義的。

單詞表示的力量:$ 1101001 $意味著上升兩次,下降,上升,下降兩次然後上升。有許多有趣的問題要問:這可能是一個非平凡的循環嗎?相反,給出任何單詞$ w $,它是否屬於一個非平凡的循環?在一個非平凡的循環中,是否必須有多於零的?在零的數量上,是否有一個上限或下限?

我想你可以說我問了太多問題,但我真正需要的唯一答案就是這個$ 1-1 $的通信。我不能破解它,但我打賭那裏的一些小組理論家可以提供幫助。提前謝謝了。

最佳答案

你在這裏的工作看起來類似於埃弗雷特的“數理論功能的叠代”(1977); Terras還有一篇類似的論文 - “關於正整數的停止時間問題”(1976)。 Terras和Everett都證明了$ 1 $到$ 2 ^ n $之間的數字之間的$ 1 - 1 $對應關系,以及帶n位數字的二進制數字集合;從中可以得出你正在尋找的$ 1 - 1 $通信的必然結果。

Everett使用感應證明,這也適用於你正在尋找的東西。

轉載註明原文: 關於Collat​​z問題的一個想法