投稿類別 : 數學類 篇名 : de Bruijn 圖與 collatz 問題的相關探討 作者 : 熊竑茗 陽明高中 高三 11 班 王宜婕 陽明高中 高三 11 班 指導老師 : 王聖淵老師 吳林建宏老師
壹 前言 一 研究動機 在 數字的秘密生命 (George G. Szpiro 著 ) 這本書裡面談到了一個 Collatz Sequence 數列問題, 其規則是 : 對於任意正整數 n, 偶數則除以 2, 奇數則乘以 3 後加 1, 計算到最後都會得到 1, 這樣的特性引起我們的好奇, 作者群在先前的 小論文作品 3N+1 問題之奇偶分析 模數理論建構冰雹數列路徑預測圖之相 關研究 與 冰雹數列轉換進位制的相關研究與探討 中, 我們已經探討了 Collatz Sequence 的一些基本性質, 利用模數理論與二進位進行分析與討論, 找到初步的路徑模型, 並達到預測效果 但是在之前作品探討的過程中, 其原始定義導致路徑太過複雜, 因此在這篇 研究中, 我們重新定義 Collatz Sequence, 以求簡化 Collatz Sequence 的計算方式, 更進而探討其與 de Bruijn 圖的關聯及轉換, 希望能將 Collatz Sequence 拓展, 使 其不再受限於正整數 二 研究目的 ( 一 ) 簡化 Collatz Sequence 的定義並進行觀察 ( 二 ) 探討 Collatz Sequence 與德布萊茵圖之關聯性 ( 三 ) 將 Collatz Sequence 拓展至分數與負數並進行觀察 貳 正文 一 介紹 Collatz Sequence 與定義定義 1 Collatz 數列 1 當 n 1 將 Tn ( ) 定義為 T ( n) 3n 1 當 n是奇數, 且 n 1, n 當 n 是偶數 2 c c, c, c,, c 且數列 1 2 3 n n n n n j 1
c n j c c n1 nj n T( cn 1) j j2 則數列 c n 稱為 Collatz Sequence 舉例說明 : n 3, C 3 3 10 5 16 8 4 2 1, 得知 n 3時在 7 步之 7 後會回到 1, 亦即 T T T T T T T T 定義 2 變換 (3) (3) 1 1. 奇變換 : 我們將上述 : 奇數乘 3 再加 1 這樣的變換過程定義為奇變換 2. 偶變換 : 我們將上述 : 偶數除以 2 這樣的變換過程定義為偶變換 3. 完全變換 : 我們把 奇數乘 3 再加 1 然後又除以 2 這樣的變換過程定義為完 全變換 經過先前作品的討論後, 我們認為這樣的定義太過複雜, 因此在這一篇研究 作品中, 我們重新定義數列 並將其簡化 由於在先前作品 3N+1 問題之奇偶 分析 已知所有數字在奇變換後都會進行偶變換, 因此我們直接將此步驟併入, 也就是將奇變換直接改為完全變換 重新定義 collatz 函數為 : 比較修改前後的 collatz 數列 : 1 當 n 1 3n 1 T( n) 當 n是奇數, 且 n 1 2 n 當 n 是偶數 2 T(7) : 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 T (7) : 7 1117 26 13 20 10 5 8 4 2 1 從上述比較可以發現後者的路徑明顯縮短許多, 此簡化有助於後續探討 2
二 德布萊茵圖的相關研究 ( 一 ) 德布萊茵圖的定義 一個有向圖 G,n 中, 圖中每個頂點為 a0a1... a n 1, ai S= 0,1,..., 1, 且 2,n 則為頂點的字串長度, 若每個相鄰頂點皆有 n 1 個數字重複, 則稱 G,n 為 de Bruijn 圖 以下圖以 G 2,3 為例 : 圖 1 圖 G 2,3 ( 二 ) 德布萊茵圖的相關應用 : 許多文獻中表示 de Bruijn 圖可以應用於許多層面, 以基因比對為例 : 定序物種的基因組序列是瞭解物種間差異的重要課題, 每種生物的基因密碼排列雖皆不相同, 但都是由 A T C G 四種含氮鹼基排列組成 然而, 基因組的序列非常長, 例如 : 人類基因組有 3 Giga 鹼基, 因此需要有效的方法來處理如此大量的資料並方便能快速比對,de Bruijn 圖就是其中之一 首先將每個短序拆成 個連續但只差一個鹼基的更短序列 ( 稱為 -mer), 每個 -mer 在圖中代表一個節點, 在序列中連續兩個 -mers 的關係則利用邊將其連接起來, 將每個點以 de Bruijn 的方式排列, 如此便可以建立所有短序使用的 -mers 和連接關係並方便比對, 舉例來說 : 輸入一段基因序 TTGTACGTAG, 則可以得到 : 3
圖 2 2-mer 圖 3 3-mer 經由這樣的表示方法後, 若其中出現了不同的基因, 則會產生不同的圖形與路 徑, 可以馬上辨認, 例如 : 正常為 TTGTACGTAG, 而實際得到為 TTGTAAGTAG, 即使只有一個基因不同, 在圖中也會產生明顯的路徑變化 圖 4 基因差異路徑比較 在 GTA 後原本該接的是 TAC( 下方路徑 ), 但因為 TAC 變成了 TAA, 引此產生了一條完全不同的路徑 ( 上方路徑 ), 如此便可以幫助快速判別基因差異在何處 ( 三 ) 德布萊茵圖與 collatz 模數圖關聯性研究 : 我們在和老師研究的過程中發現, 德布萊茵圖與 collatz 模數圖似乎有些微 妙的關係, 因此我們決定深入探討 首先我們將 T ( n) 取模數後, 和德布萊茵圖產生關聯性 仿先前投稿的作品 研究方式, 我們將 T ( n) 的結果重新繪製模數圖, 發現一些有趣的現象, 下圖為 T ( n) 取模數 4 與模數 8 的比較圖 : 4
圖 5 T ( n) 取模數 4( 左圖 ) 與模數 8( 右圖 ) 的圖 從上面兩個圖表, 能看出許多結構對稱的地方, 且每個節點都有兩個輸入與 輸出的邊, 兩圖為同構 在左圖的每個邊上標示相應於模數 8 的數, 例如 : 在取 模數 4 的情況下, 同餘 2 的數經過 T ( n) 的迭代後會同餘 3, 而所有取模數 8 之後, 會同餘 6 的數, 在取模數 4 的情況下, 也會得到相同結果, 因此在 2 往 3 的路徑 上標示 6 若將 collatz 圖取成 mod 2 i 之模數圖, 再將各頂點做函數 ( n) xi( n)2 調 整, 接著轉成二進位並調換數字順序, 便可以與 de Bruijn 圖做一對一映射, x 是將 collatz 數列取 mod2 後的結果, 下標的 i 則是代表第 i 步 舉例來說 T(5) 5 8 4 2 1, 則 X (5) 1 0 0 0 1, 就可以知 道 X (5) 1 X (5) 0 0 1 等, 代入即得到 mod 16 為例, 轉換結果如下圖 : 1 i0 0 1 2 3 4 (5)=1 2 +0 2 +0 2 +0 2 =1 i n, 以 圖 6 T (n) 經 4 的轉換 5
接著再將轉換後的圖形每個點轉成二進位並調換數字順序, 便可以與 de Bruijn 圖做一對一的映射, 下圖為由模數 2 的 4 次方所取成, 因此每個頂點長度皆為 4, 舉例來說 :11 取二進位, 會得到 1011, 若把數字由左至右表示, 則會得到 1101, 這樣表示法就可以讓模數圖上的所有數字對應至 de Bruijn 圖 ( 如圖 7) 圖 7 G 2,4 之 de Bruijn 圖 此外, 數字型態的 de Bruijn 圖, 我們有找到其計算規則 : 2, n n n 1 ( n 1) / 2,( n 1) / 2 2 if n is odd, 1 / 2, / 2 2 if is even. 經過上述運算可以幫助我們驗算 de Bruijn 的各頂點, 而計算的原理則是利 用二進位的計算 將圖 G 每個點看為二進位的數字, 則奇數減一再除以二, 算 出來的結果等於去掉第一個數字並在最後補 0, 若再加上 2 1 則等於在數字的後 面加一 舉 2,4 為例,13 經過 2,4 後可得 6, 而頂點的表示法則為 1011 0110 ; 若在 其後再加上 8 則得到 14, 也就是 0111, 如下圖 ( 左 ) 如此一來便符合 de Bruijn 的轉換規則, 而偶數除以 2 與除以 2 在加 1 2, 也會有相同結果, 同舉 2,4 為例, 6 經 2,4 為例,6 經 2,4 轉換後可得 3 或 11, 如下圖 ( 右 ) 6
圖 8 13 的 de Bruijn 變換 圖 9 6 的 de Bruijn 變換 如此便可以幫助我們快速驗算 de Bruijn 的各個頂點 ( 四 ) 利用函數 對 collatz 問題進行延伸探討 在上面的討論中, 我們透過定義函數, 可以轉換 collatz 問題的形式, 使 其產生一對一映射的新圖形, 然而在過程中又發現, 透過函數, 似乎可以對 collatz 問題做更全面的討論 : 1. 在先前的定義中,collatz 問題只適用於正整數, 但若將函數 取至無限, 也 就是 : ( n) x ( )2 i i n i0 則能將數字一對一映射至有理數, 使其從正整數拓展至有理數 以 (5) 舉例 : 已知 X (5) 1 0 0 0 1 0 1 0... 無限 1 0循環 0 1 2 3 4 5 6 則 (5)=1 2 +0 2 +0 2 +0 2 +1 2 +0 2 +1 2 +... 由於取至無限的關係, 根據 collatz 問題的定義, 數字到最後必會陷入循環, 在 (5) 4 的例子中, 從 1 2 後便陷入了循環, 其後面是以 4 為公比的發散等比級數, 在 a1 這裡我們利用冪級數的概念, 將等比的部分直接給定成 1 r, 因此 (5) 就變成了 : 4 0 1 2 3 1 2 13 (5)=1 2 +0 2 +0 2 +0 2 + 1 4 3 7
透過這樣的方式, 可以使 collatz 問題的所有數字做一對一的映射轉換, 並得知 1 3 \ 2. 在給定 後, 我們將 T ( n) 的路徑圖畫出來, 且不再只局限於正整數, 而是擴 充到分數與負數的部分, 得到下面的圖 : 圖 10 collatz 問題路徑圖 ( 部分 ) 接著將其帶入 進行計算, 由於分數的部分無法取模數, 因此在計算時分數 的部分我們令不論正負, 若分子為奇數則同餘 1(mod2), 若分子為偶數則同餘 0(mod2) 來計算 2 以 ( ) 為例 : 9 2 2 1 1 T( ) 1 2 1 2... 9 9 9 3 2 X ( ) 0 1 1 1 0 1 0... 9 3 2 0 1 2 1 2 10 ( ) 0 2 1 2 1 2 9 1 4 3 以這樣的計算規則, 我們將圖.32 做 的轉換來進行觀察得到下圖 : 8
圖 11 collatz 問題路徑圖 ( 部分 )( 左 ) collatz 問題路徑圖 ( 部分 ) 經 轉換 ( 右 ) 比較兩圖, 我們也找出一些性質, 並發現 : 定理 1: 一分數 a, x 2 若 a3, x 且 2 1, 則 ( ) 2 ( ) a a Proof. 若分數 2 a 之 a 與 滿足上述形式, 則 2 a 視為偶數進行偶變換得到 a, 2 則與 a a 帶入 T ( n) 之迭代步驟只會差一個除以二, 在 的計算裡則是每一項都差兩倍, 因此我們能將 2 從 內的 2 i 提出, 也就是 2 i i1 x( )2 2 x( )2, 故得證 i1 a i1 a 定理 2: 若一正整數 n2, x 帶入, 則得到的數必為 Proof. 2 3 之形式 若 n 2, 則 n 在 T ( n) 的計算會連續除以二直到陷入一與二之間循環, 這樣的動 0 1 1 2 作用 表示的時候, ( n) 0 2 0 2... 0 2, 故得證 1 4 叁 結論 一 經由定義的改變, 可以使 collatz 問題簡化, 並使其模數圖產生關連性 二 透過取模數與函數的轉換, 可以從 collatz 問題得到德布萊茵圖, 並得到一些計算規則 三 藉由函數 的擴充應用, 可以使 collatz 問題不再侷限於正整數, 可以拓展到 9
分數與負數的部分, 並得到 : 1. 一分數 a, x 2 若 a3, x 且 2 1, 則 ( ) 2 ( ) a a 2. 若一正整數 n2, x 帶入, 則得到的數必為 2 3 之形式 肆 引註資料 一 英文文獻 1. S. Andrei & C. Masalagiu. "Aout the Collatz Conjecture." Acta I nformatica 35 (1998):167-179. 2. R. E. Crandall. "On the f3x + r Prolem." Math. Comp. 32 (1978):1281-92. 3. J. C. Lagarias. "The 3x + l Prolem and Its Generalizations." Amer. Math. Monthly 92 (1985):3-21. 4. Jeffrey C. Lagarias (Ed.), The Ultimate Challenge: the 3x +1Prolem, American Mathematical Society, Providence, RI, 2010. 5. E. Ain, Why is the 3x + 1 prolem hard? Contemporary Mathematics 356 (2004) 1 20. 6. P.J. Andaloro, The 3x + 1 prolem and directed graphs, Fionacci Quarterly 40 (2002) 43 54. 二 參考書籍 1. George G. Szpiro 著, 數字的秘密生命 - 生命中最有趣的 50 個數學故事, 像數學家一樣思考, 臉譜出版社 10