Collatz猜想的一個等價轉(zhuǎn)化及若干相關(guān)結(jié)論證明

洛塔爾·科拉茨（LotharCollatz）在1937年提出“Collatz猜想”（又常被稱為“ 3x+1 ”猜想，但具體的出處和原始文獻并沒有被廣泛確認或保存下來）．這個猜想的內(nèi)容是：給定任何一個正整數(shù)，若它是偶數(shù)則除以2，若它是奇數(shù)，則讓它乘以3再加上1，按照這種規(guī)則不斷的重復計算下去，最終會得到1.

例如從13開始，經(jīng)過10步迭代后得到了數(shù)字1．具體如下：

1340（3^*13+1=40）20（40/2=20）10（20/2=10）5（10/2=5）16（3^*5+1=16） 8（16/2=8）4（8/2=4）2（4/2=2）1（2/2=1）

因為猜想的內(nèi)容表述起來很簡單，所以早期主要通過口頭交流或者非正式的方式開始傳播，到1970年代，隨著計算機技術(shù)的發(fā)展，有人開始用計算機驗算該問題，發(fā)現(xiàn)猜想從1一直到很大的整數(shù)都成立，該問題在數(shù)學界也變得廣為人知．1985年數(shù)學家LagariasJC在文獻［1］提到了Collatz的工作，并且較為全面討論了直到1985年為止關(guān)于這一問題的研究進展．文獻[1」也是當前許多研究4 3x+1 ”猜想的論文在介紹此猜想時常引用的最早期文獻.

若 n 是奇數(shù)；對任意正整數(shù) n ，定義若 n 是偶數(shù).則上述猜想常可借助f表述如下，

Collatz猜想：對于任意正整數(shù) n ，存在正整數(shù) m ，使得

目前，數(shù)學家已利用計算機驗算猜想對所有小于 2⁶⁸ 的正整數(shù)都成立，但卻仍未完全證明它．雖然直接攻克它很難，但是長期以來，學者們還是圍繞它做了不少相關(guān)研究，這些研究大致可分三種類型．第一種類型就是給出接近的證明，例如文獻［2］證明Collatz猜想對幾乎所有的正整數(shù)都成立，這是陶哲軒于2019年在ArXiv上發(fā)表的結(jié)果，但他自己也承認把“幾乎所有”變成“所有”還有巨大的鴻溝要跨越．第二種類型的工作是針對猜想的一些算法研究，如文獻［3］就給出這方面的結(jié)果.第三種類型的工作就是對Collatz猜想進行各種轉(zhuǎn)化，獲得與猜想密切相關(guān)的一些概念，然后對這些相關(guān)內(nèi)容做進一步的研究，以期獲得解決猜想的契機．例如文獻［4］定義了Collatz猜想的等價集，并以此給出Collatz猜想的一個等價命題．文獻［5］對Collatz猜想給出一個用矩陣（Collatz矩陣）描述的等價命題，文獻［6］則進一步對文獻［5］中與Colatz猜想密切相關(guān)的一些代數(shù)概念進行深入研究．文獻［7」將Collatz猜想等價轉(zhuǎn)化為一個拓撲學命題，并研究相關(guān)拓撲空間的拓撲性質(zhì)．文獻［8」著重研究了Collatz迭代數(shù)列的性質(zhì)．本文的研究也屬于第三種類型，為此，先介紹相關(guān)的一些概念.

定義1若 n 是大于1的正整數(shù)，且存在 k∈Z₊ 使得 f^k（n）+|f^k（n）m（n） 為 n 的第一縮減數(shù).

例題1 n=3 ， f（3）=10 ， f²（3）=5 ， f³（3）=16 ， f⁴（3）=8 ， f⁵（3）=4 ， f⁶（3）=2 ，故 第一縮減數(shù)是2.

下文將研究 str（n） 的一些性質(zhì)，并利用 str（n） 給出Collatz猜想的一個等價命題.

根據(jù)定義1，顯然下面定理成立.

定理1當 n 是正偶數(shù)時， str（n）=1 證明因為 n 是正偶數(shù)，所以 f（n）=n/2

對于大于1的奇數(shù) n ，利用Matlab 編程可以快速得到 str（n） ，以及 代碼如下：

Matlab相關(guān)代碼

iction collatz_sequence（n）if＼～isnumeric（n） ||Σ_nlt;=0|| mod（n，1） ～=0 （204號error（'Input must be a positive integer.'）;end% 檢查輸入是否為正整數(shù)results ； % 用于存儲序列中的所有結(jié)果current Ψ=Ψ_n . % 當前處理的數(shù)字初始化為ncount=0 % 用于計數(shù)除了最初的 n 外的結(jié)果數(shù)量while 將當前值添加到結(jié)果列表中results （ % 根據(jù)當前數(shù)字是奇數(shù)還是偶數(shù)執(zhí)行相應的操作if mod（current，2） ==0 （204next_valu e=c urrent 12 ; % 如果是偶數(shù)，則除以2else S % 如果是奇數(shù)，則乘以3加1endcurrent Σ=Σ next_value； % 更新當前值為next_value% 如果下一個值小于初始的 Π_n ，則結(jié)束循環(huán)，并將這個值也加入結(jié)果中if current 5 % 添加最后一個小于n的值break;endcount=count+ 1

end % 增加計數(shù)器（這里我們計算的是除了最開始的 η_n 之外的所有步驟）

count ； % 最后增加計數(shù)器來包含最后一個小于n的數(shù)

fprintf（'迭代序列（包含最初的數(shù)）： ）；for i= 1：length（results）fprintf （%）%d^′ ，results （i））;if ilt; length（results）fprintf （χ^′，χ^′） ：end

endfprintf ；fprintf（'Collatz縮減步長： %du^′ ，count）； % 顯示步長

end

在Matlab保存代碼后在命令行窗口輸人collatz_sequence（39）并運行，結(jié)果如圖1.

借助Matlab計算得到一些Collatz縮減步長結(jié)果，如表1所示.

從表1數(shù)據(jù)中，猜測并證明下面幾個定理.

定理2當 n 是大于1的整數(shù)且 ，則 str（n）=3

證明設(shè) n=4k+1

故 str（n）=3 ．證畢.

定理3當 n 是正整數(shù)且 n≡3（mod16） ，則 str（n）=6

證明設(shè) n=16k+3 ， f（n）=3（16k+3）+1=48k+10.

f²（n）=24k+5.

f³（n）=3（24k+5）+1=72k+16，

f⁶（n）=9k+2lt;16k+3=n，

又顯然當 1?j?5 ，有 f^j（n）gt;n ，所以 str（n）=6 證畢.

定理4當 n 是正整數(shù)且 n≡11 或23（ ，則 str（n）=8 ：

證明 （1）當 n=16k+11 ， k 是非負整數(shù)，則

f（n）=3（16k+11）+1=48k+34，

f²（n）=24k+17，

f³（n）=3（24k+17）+1=72k+52，

f⁵（n）=18k+13，

f⁶（n）=3（18k+13）+1=54k+40，

f⁷（n）=27k+20.

若 k 是偶數(shù)，則 f⁸（n）=13 ： 5k+10lt;16k+11=n 即 n 是正整數(shù)且 時， str（n）=8

（2）當 n=16k+7 ， k 是非負整數(shù)，則

f（n）=3（16k+7）+1=48k+22，

f²（n）=24k+11，

f³（n）=3（24k+11）+1=72k+34，

f⁴（n）=36k+17，

f⁵（n）=3（36k+17）+1=108k+52，

f⁷（n）=27k+13.

若 k 是奇數(shù)，

f⁸（n）=13.5k+6.5lt;16k+7=n.

即 n 是正整數(shù)且 時， str（n）=8 ．證畢.

定理5當 n 是正整數(shù)且 n≡7 或15或59（mod128），則 str（n）=11

證明（1）當 n=128k+7 ， k 是非負整數(shù)，即 n=2⁷k+2³-1 ，則

f（n）=3（2⁷k+2³）-2，

f²（n）=3（2⁶k+2²）-1，

f³（n）=3²（2⁶k+2²）-2.

f⁴（n）=3²（2⁵k+2）-1，

f⁵（n）=3³（2⁵k+2）-2，

f⁶（n）=3³（2⁴k+1）-1=3³2⁴k+26，

f⁷（n）=3³2³k+13，

f⁸（n）=3⁴2³k+40，

又顯然當 1?j?10 時，有 f^j（n）gt;n ，所以 str（n）=11

（2）當 n=128k+15 ， k 是非負整數(shù)，即 n=2⁷k+2⁴-1 ，則

f⁷（n）=3⁴（24k+2）-2，

f⁸（n）=3⁴（23k+1）-1=3⁴?23k+80，

f¹¹（n）=3⁴k+10=81k+10lt;128k+15=n，

又顯然當 1?j?10 時，有 f^j（n）gt;n ，所以 str（n）=11

（3）當 n=128k+59 ， k 是非負整數(shù)，則

f²（n）=3?2⁶k+89，

f³（n）=3（3?2⁶k+89）+1=3²?2⁶k+268，

f⁴（n）=3²?2⁵k+134，

f⁵（n）=3²?2⁴k+67.

f⁶（n）=3（3²?2⁴k+67）+1=3³?2⁴k+202，

f⁷（n）=3³?2³k+101，

f⁸（n）=3（3³?2³k+101）+1=3⁴?2³k+304，

f¹¹（n）=3⁴k+38=81k+38lt;128k+59=n，

又顯然當 1?j?10 時，有 f^j（n）gt;n ，所以 str（n）=11 ．證畢.

設(shè) S={k∈Z₊|1?k?128} ，若 n 是大于1的整數(shù)且 ， k∈S ，則由定理1可知當 k 是 s 里面64個偶數(shù)中的任意一個時， n 是Collatz可縮減的，同理由定理2，當 k 是 s 中的其中32個特定奇數(shù)時， n 是Collatz可縮減的，再結(jié)合定理3、定理4、定理5，可知當 k 是 s 中 64+32+8+4×2+3= 115個特定的數(shù)時， n 是Collatz可縮減的．對定理1到定理5進行排查，易得下面的推論.

推論1設(shè) M={k∈Z₊|1?k?128 且 k 非27、31、39、47、63、71、79、91、95、103、111、123、127這13個數(shù)中任意一個}，對任意 k∈M ，若 n 是大于1的整數(shù)且 ，則 n 是Collatz可縮減的.

定理6當 n 是正整數(shù)且 n≡39 或79或95或 123（mod256 ，則 str（n）=13 證明當 n=256k+39 ， k 是非負整數(shù)，則

f²（n）=3?2⁷k+59.

f³（n）=3（3?2⁷k+59）+1=3²?2⁷k+178，

f⁴（n）=3²?2⁶k+89，

f⁵（n）=3（3²?2⁶k+89）+1=3²?2⁶k+268，

f⁶（n）=3³?2⁵k+134，

f⁷（n）=3³?2⁴k+67，

f⁸（n）=3（3³?2⁴k+67）+1=3⁴?2⁴k+202，

f⁹（n）=3⁴?2³k+101，

f¹⁰（n）=3（3⁴?2³k+101）+1=3⁵?2³k+304，

f¹³（n）=3⁵k+38=243k+38lt;256k+39=n，

又顯然當 1?j?12 時，有 f^j（n）gt;n ，所以 str（n）=13 當 n≡79 或95或 123（mod256 時，同理可證．證畢.

推論2存在一個大于1的整數(shù) n 使得 n 的第一縮減數(shù)是 n-1 ：

證明由定理6的證明可知，當 n=39 時，它的第一縮減數(shù)是 38=n-1 ．證畢.

注1除了39這個例子外，還有別的例子，如由定理3證明，可知3的第一縮減數(shù)是2.

定理7Collatz猜想成立的充分必要條件是每個大于1的整數(shù)都是Collatz可縮減的，

證明必要性，若Collatz猜想成立，對于任意大于1的整數(shù) n ，存在正整數(shù) k 使得 f^k（n）=1 ，因為1

充分性，對每個大于1的整數(shù) n ，因 n 是Collatz可縮減的，設(shè) str（n）=k ，則 f^k（n）k（n） 仍是正整數(shù)，若 f^k（n）=1 ，則結(jié)論已成立，若 f^k（n）gt;1 ，則由已知條件， f^k（n） 也是Collatz可縮減的，故可以繼續(xù)迭代到嚴格變小，即存在 k₁ 使得 f^k1（f^k（n））=f^k+k1（n）k（n） 因 n 是有限數(shù)，故有限次迭代縮小后，必然迭代成為1，即存在不超過 n 個的正整數(shù) k₁ ， k₂，…. ， k_l 使得

ngt;f^k（n）gt;f^k+k1（n）gt;f^k+k1+k2（n）gt;…gt;f^{k+k1+k2+…+kl}（n）=1.

故Collatz猜想成立，證畢.

引理1對任意大于1的整數(shù) p ，當 k 是不超過 2p 的正整數(shù)時，有

證明 當 k=1 時，

滿足公式.

當 k=2 時，

f^k（2^p-1）=f（3¹2^p-2）=3¹2^p-1-1.

滿足公式.

假設(shè)公式對 klt;2p 成立，下證公式對 k+1 也成立.

若 k 是奇數(shù)，則 ，因 klt;2p ，故 是正整數(shù)，因而 f^k（2^p-1） 是一個偶數(shù)，故 ，又 k+1 是偶數(shù)，即公式對 k+1 也成立.

若k是偶數(shù)，則f（2°-1）=322-1，因klt;2p，故p-是 是正整數(shù)， f^k（2^p-1） 是一個奇數(shù)，故

又 k+1 是奇數(shù)，即公式對 k+1 也成立.

綜上，當 k 是不超過 2p 的正整數(shù)時上述公式都成立，證畢.

定理8對任意大于1的整數(shù) p ，當 k 是不超過 2p 的正整數(shù)時，有 f^k（2^p-1）gt;2^p-1

證明對任意大于1的整數(shù) p ，設(shè) k 是不超過 2p 的正整數(shù)．若 k 是偶數(shù)，由引理1，

若 k=1 ，則

f^k（2^p-1）=f（2^p-1）=3?2^p-2gt;2?2^p-2=2（2^p-1）gt;2^p-1.

若 k 是大于1的奇數(shù)，則 k-1 是不超過 2p 的正偶數(shù)，由引理1和上面關(guān)于 k 是偶數(shù)時的證明，可得

f^k（2^p-1）=2f^k-1（2^p-1）gt;f^k-1（2^p-1）gt;2^p-1.

證畢.

推論3若Collatz猜想成立，則對任意大于1的整數(shù) p ，有 str（2^p-1）gt;2p

證明若Collatz猜想成立，由定理7，每個大于1的整數(shù)都是Collatz可縮減的，從而對任意大于1的整數(shù) p ， str（2^p-1） 存在，根據(jù)Collatz縮減步長的定義和定理8，有 str（2^p-1）gt;2p ：

定理9若Collatz猜想成立，則對任意 N∈Z₊ ，存在 n∈Z₊ 使得 str（n）gt;N

證明對任意 N∈Z₊ ，取 p 充分大使得 2pgt;N ，由推論3有 str（2^p-1）gt;2p ，故取 n=2^p-1 ，則 str（n）gt;2pgt;N 證畢.

注2由定理9可知，若Collatz猜想成立，則 {sin（n）|n∈Z₊ 且 .ngt;1} 是無上界的集合，從而大于1的整數(shù)中不存在最大的Collatz縮減步長.

結(jié)束語：本文定義了一個大于1的整數(shù)是否是Collatz可縮減的以及它的Collatz縮減步長的概念，證明Colltz猜想成立等價于每一個大于1的正整數(shù)都是Collatz可縮減的．我們已經(jīng)找到不少類型的正整數(shù)是Collatz可縮減的，并算出它們的Collatz縮減步長．最后證明若Collatz猜想成立，則存在一列Collatz縮減步長不斷增加的數(shù)列，從而不存在最大的Collatz縮減步長．當然，還有一些大于1的整數(shù)我們尚未證明它們是Collatz可縮減的，這是待進一步研究之處.

參考文獻：

[1]LagariasJC.The3x+1problemanditsgeneralizations[J].AmericanMathematical Monthly，1985，92（1）：3-23.

[2]Tao T.Almostallorbitsof the Colltz mapattinalmost bounded values[EB/OL].（2019-09-08）[2021-08-21].https：//arxiv.org/pdf/1909.03562.pdf.

[3]Ichikawa S，Kobayash N.Preliminarystudyof customcomputing hardware for the3X+1 problem[C].2004 IEEERegion 10 Conference TENCON 2004．New York：IEEE Press，2004，4：387-390.

[4]楊照華．3x+1猜想的等價集[J]．華南師范大學學報：自然科學版，1998（2）：66-68.

[5]Alves JF，Graga MM，Sousa Dias ME，etal.A linear algebra appoach to the conjecture of Collatz[J].Lin-ear Algebra and its Applications．2005，394：277-289.

[6]KauffmanLH，LopesP.OntheorbitsassociatedwiththeColltz conjecture[J].LinearAlgebraanditsApplica-tions．2021，615（1）：143-154.

[7]Vielma J，GualeA.Atopologicalapproach totheUlam-Kakutani-Colatzconjecture[J].TopologyanditsAppli-cations.2019，256（1）：1-6.

[8]吳拿達．3X+1迭代數(shù)列的幾個性質(zhì)[J]．韓山師范學院學報，2022，43（3）：1-4.

The Equivalent Transformation of the Collatz Conjecture andProofs ofSeveral Related Results

WU Na-da （College of Mathematics and Statistics，Hanshan Normal University， Chaozhou， Guangdong，521041）

Abstract：For any integer n greater than 1，if after k iterations of the Collatz process it becomes smallerthan itself for the first time，then n is called Collatz-reducible，and k isreferred to as the Collatz reduction step of n .It is proven in this paper that a necessary and sufficient condition forthe Collatz conjecture to hold isthat every integer greater than1is Colatz-reducible.Several classesof positive integersthat are Collatz-reducible areidentified，and their respective Colatz reduction steps are calculated.Additionally，several conclusions about Collatz reduction steps are proved.Finally，it is proven that if the Colltz conjecture holds true，then there does not exist a maximum Collatz reduction step among the integers greater than 1.

Key Words：Collatz conjecture；Colatz reduction step；Collatz reducible；equivalent proposition

責任編輯 朱本華