廣義 3n + 1 問題

所謂廣義「3n+1」猜想 (Generalized 3n + 1 Conjecture),即把式中的 3 和 +1 也取任意,變成 kn + m 。另外把整數的分組的方法也任意了,不一定按奇偶分組,也可按 3 的倍數或 5 的倍數等來分組。

以數式來表示便是:

找一數值 d > 1 使某數的變換為

T(x) = (mi- ri) / d 若 x = i (mod d),其中 ri= i * mi (mod d) 及 i = 0, 1, 2, ......, d-1

若取 d=2,及 m0 = 1, r0 = 0; m1 = 3, r1= -1:則是我們原本的「3n+1」猜想 (3n + 1 Conjecture) 了。

我們研究的便是當中會否出現不同的循環 (Cycle),和當中的最大循環長度 (Maximum Cycle Length) 是多少。

 

現在我們試取 d = 4 及 m0 = 0,m1 = 3,m2 = 5,m3 = 17,得

T(x) = x/4 若 x = 0 (mod 4)

T(x) = (3x - 3) / 4 若 x = 1 (mod 4)

T(x) = (5x - 2) / 4 若 x = 2 (mod 4)

T(x) = (17x - 3) / 4 若 x = 3 (mod 4)

 

 

讓我們以 2006 來看看這個廣義「3n+1」會為它指引一條什麼的路。

2006 => 2507 => 10654 => 13317 => 9987 => 42444 => 10611 => 45096 => 11274 => 14092 =>

3523 => 14972 => 3743 => 15907 => 67604 => 16901 => 12675 => 53868 => 13467 => 57234 =>

71542 => 89427 => 380064 => 95016 => 23754 => 29692 => 7423 => 31547 => 134074 => 167592 =>

41898 => 52372 => 13093 => 9819 => 41730 => 52162 => 65202 => 81502 => 101877 => 76407 =>

324729 => 243546 => 304432 => 76108 => 19027 => 80864 => 20216 => 5054 => 6317 => 4737 =>

3552 => 888 => 222 => 277 => 207 => 879 => 3735 => 15873 => 11904 => 2976 =>

744 => 186 => 232 => 58 => 72 => 18 => 22 => 27 => 114 => 142 =>

177 => 132 => 33 => 24 => 6 (經 75 步至 6)

 

原來 6 是一個循環中的最小數值,但依書所言,這是一個長 1747 步的循環,有興趣者不妨求證,把那 1747 個數找出來。除此以外,不同的數值當中共出現了 17 個不同的循環,分別起始自 0, -3, 2, 3, 6 (長度為 1747), -18, -46, -122, -330, -117, -137, -186, -513 (長度為 1426), -261, -333, 5127, -5025。

 

參考文獻及網址

Matthews, Keith "Generalized 3x+1 functions and Markov matrices." http://www.numbertheory.org/php/generalized_3x+1.html .

Matthews, Keith "The Generalized 3x+1 mapping." 2006