投稿類別：數學類

Size: px

Start display at page:

Download "投稿類別：數學類"

培胥
6 years ago
Views:

1 投稿類別 : 數學類篇名 : de Bruijn 圖與 collatz 問題的相關探討作者 : 熊竑茗陽明高中高三 11 班王宜婕陽明高中高三 11 班指導老師 : 王聖淵老師吳林建宏老師

2 壹前言一研究動機在數字的秘密生命 (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 且數列 n n n n n j 1

3 c n j c c n1 nj n T( cn 1) j j2 則數列 c n 稱為 Collatz Sequence 舉例說明 : n 3, C , 得知 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) : T (7) : 從上述比較可以發現後者的路徑明顯縮短許多, 此簡化有助於後續探討 2

4 二德布萊茵圖的相關研究 ( 一 ) 德布萊茵圖的定義一個有向圖 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 經由這樣的表示方法後, 若其中出現了不同的基因, 則會產生不同的圖形與路徑, 可以馬上辨認, 例如 :

基因差異路徑比較在 GTA 後原本該接的是 TAC( 下方路徑 ), 但因為 TAC 變成了 TAA, 引此產生了一條完全不同的路徑 (

我們在和老師研究的過程中發現, 德布萊茵圖與 collatz 模數圖似乎有些微妙的關係, 因此我們決定深入探討首先我們將 T ( n)

5 圖 2 2-mer 圖 3 3-mer 經由這樣的表示方法後, 若其中出現了不同的基因, 則會產生不同的圖形與路徑, 可以馬上辨認, 例如 : 正常為 TTGTACGTAG, 而實際得到為 TTGTAAGTAG, 即使只有一個基因不同, 在圖中也會產生明顯的路徑變化圖 4 基因差異路徑比較在 GTA 後原本該接的是 TAC( 下方路徑 ), 但因為 TAC 變成了 TAA, 引此產生了一條完全不同的路徑 ( 上方路徑 ), 如此便可以幫助快速判別基因差異在何處 ( 三 ) 德布萊茵圖與 collatz 模數圖關聯性研究 : 我們在和老師研究的過程中發現, 德布萊茵圖與 collatz 模數圖似乎有些微妙的關係, 因此我們決定深入探討首先我們將 T ( n) 取模數後, 和德布萊茵圖產生關聯性仿先前投稿的作品研究方式, 我們將 T ( n) 的結果重新繪製模數圖, 發現一些有趣的現象, 下圖為 T ( n) 取模數 4 與模數 8 的比較圖 : 4

xi( n)2 調整, 接著轉成二進位並調換數字順序, 便可以與 de Bruijn 圖做一對一映射, x 是將 collatz 數列取 mod2 後的結果, 下標的 i 則是代表第 i 步舉例來說 T(5) 5 8 4 2 1, 則 X (5) 1 0 0

6 圖 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) , 則 X (5) , 就可以知道 X (5) 1 X (5) 等, 代入即得到 mod 16 為例, 轉換結果如下圖 : 1 i (5)= =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 圖

7 接著再將轉換後的圖形每個點轉成二進位並調換數字順序, 便可以與 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, 而頂點的表示法則為 ; 若在其後再加上 8 則得到 14, 也就是 0111, 如下圖 ( 左 ) 如此一來便符合 de Bruijn 的轉換規則, 而偶數除以 2 與除以 2 在加 1 2, 也會有相同結果, 同舉 2,4 為例, 6 經 2,4 為例,6 經 2,4 轉換後可得 3 或 11, 如下圖 ( 右 ) 6

在先前的定義中,collatz 問題只適用於正整數, 但若將函數取至無限, 也就是 : ( n) x ( )2 i i n i0 則能將數字一對一映射至有理數, 使其從正整數拓展至有理數以 (5) 舉例 : 已知 X (5) 1 0 0 0 1 0 1 0.

8 圖 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循環則 (5)= 由於取至無限的關係, 根據 collatz 問題的定義, 數字到最後必會陷入循環, 在 (5) 4 的例子中, 從 1 2 後便陷入了循環, 其後面是以 4 為公比的發散等比級數, 在 a1 這裡我們利用冪級數的概念, 將等比的部分直接給定成 1 r, 因此 (5) 就變成了 : (5)=

$透過這樣的方式, 可以使 collatz 問題的所有數字做一對一的映射轉換, 並得知 1 3 \ 2.$

9 透過這樣的方式, 可以使 collatz 問題的所有數字做一對一的映射轉換, 並得知 1 3 \ 2. 在給定後, 我們將 T ( n) 的路徑圖畫出來, 且不再只局限於正整數, 而是擴充到分數與負數的部分, 得到下面的圖 : 圖 10 collatz 問題路徑圖 ( 部分 ) 接著將其帶入進行計算, 由於分數的部分無法取模數, 因此在計算時分數的部分我們令不論正負, 若分子為奇數則同餘 1(mod2), 若分子為偶數則同餘 0(mod2) 來計算 2 以 ( ) 為例 : T( ) X ( ) ( ) 以這樣的計算規則, 我們將圖.32 做的轉換來進行觀察得到下圖 : 8

故得證 i1 a i1 a 定理 2: 若一正整數 n2, x 帶入, 則得到的數必為 Proof. 2 3 之形式若 n 2, 則 n 在 T ( n) 的計算會連續除以二直到陷入一與二之間循環, 這樣的動 0 1 1 2 作用表示的時候, ( n) 0 2 0 2.

10 圖 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) 的計算會連續除以二直到陷入一與二之間循環, 這樣的動作用表示的時候, ( n) , 故得證 1 4 叁結論一經由定義的改變, 可以使 collatz 問題簡化, 並使其模數圖產生關連性二透過取模數與函數的轉換, 可以從 collatz 問題得到德布萊茵圖, 並得到一些計算規則三藉由函數的擴充應用, 可以使 collatz 問題不再侷限於正整數, 可以拓展到 9

11 分數與負數的部分, 並得到 : 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): R. E. Crandall. "On the f3x + r Prolem." Math. Comp. 32 (1978): J. C. Lagarias. "The 3x + l Prolem and Its Generalizations." Amer. Math. Monthly 92 (1985): Jeffrey C. Lagarias (Ed.), The Ultimate Challenge: the 3x +1Prolem, American Mathematical Society, Providence, RI, E. Ain, Why is the 3x + 1 prolem hard? Contemporary Mathematics 356 (2004) P.J. Andaloro, The 3x + 1 prolem and directed graphs, Fionacci Quarterly 40 (2002) 二參考書籍 1. George G. Szpiro 著, 數字的秘密生命 - 生命中最有趣的 50 個數學故事, 像數學家一樣思考, 臉譜出版社 10

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0