Mở trình đơn chính

Trong toán học, phỏng đoán Collatz là một phỏng đoán đề cập đến một dãy số xác định như sau: bắt đầu bằng một số tự nhiên n bất kỳ. Mỗi số tiếp theo được xác định theo số trước đó bằng định nghĩa sau: nếu số trước đấy là một số chẵn, thì số tiếp theo bằng một nửa số trước. Nếu số trước là một số lẻ, thì số tiếp theo bằng ba lần số trước cộng với 1. Phỏng đoán cho rằng với bất kỳ giá trị nào của n, dãy số luôn luôn đạt tới 1.

Phỏng đoán mang tên nhà toán học người Đức Lothar Collatz, ông đã nêu ra nó vào năm 1937, hai năm sau khi nhận bằng tiến sĩ toán học.[1] Nó còn được biết đến là phỏng đoán 3n + 1, phỏng đoán Ulam (mang tên của Stanisław Ulam), bài toán Kakutani (mang tên Shizuo Kakutani), phỏng đoán Thwaites (mang tên Sir Bryan Thwaites), thuật toán Hasse (mang tên Helmut Hasse), hay bài toán Syracuse;[2][4] dãy các số tự nhiên này cũng còn được gọi là dãy số mưa đá (bởi vì giá trị của chúng thường trải qua những đợt tăng hoặc giảm giá trị giống như hạt mưa đá bay lên và rơi xuống trong đám mây),[5][6] hoặc các số ngạc nhiên.[7]

Paul Erdős từng nói về phỏng đoán Collatz: "Toán học có thể chưa sẵn sàng cho những vấn đề như thế này."[8] Ông cũng hứa giành tặng $500 cho ai đưa ra được lời giải.[9] Jeffrey Lagarias năm 2010 dựa trên những thông tin hiểu biết về tình trạng của vấn đề này đã nói, "đây là một bài toán cực kỳ khó, vượt hoàn toàn ra khỏi tầm với của toán học hiện nay."[10]

Phát biểu của phỏng đoánSửa đổi

 
Numbers from 1 to 9999 and their corresponding total stopping time
 
Histogram of total stopping times for the numbers 1 to 100 million. Total stopping time is on the x axis, frequency on the y axis. Note that for all positive integers the histogram would be a completely different, exponentially-growing sequence (see #In reverse)
 
Iteration time for inputs of 2 to 10,000,000

Xét một phép toán sau tác động lên một số nguyên dương bất kỳ:

  • Nếu nó là số chẵn, chia số đó cho 2.
  • Nếu nó là số lẻ, nhân số đó với 3 và cộng 1.

Theo ký hiệu của số học mô đun, hàm số f được xác định như sau:

 

Sau đó một dãy số được hình thành từ các phép tính lặp lại này, bắt đầu bằng một số tự nhiên bất kỳ, mỗi số sau được xác định từ số trước đó.

Viết bằng ký hiệu:

 

(nghĩa là:   là giá trị của   áp dụng với   bằng cách lặp đệ quy   lần;  ).

Phỏng đoán Collatz cho rằng: Quá trình cuối cùng sẽ tiến tới 1, bất kể giá trị ban đầu được chọn bằng bao nhiêu.

Giá trị i nhỏ nhất sao cho ai = 1 được gọi là tổng thời gian dừng của n.[3] Phỏng đoán Collatz cho rằng n có tổng thời gian dừng hữu hạn. Nếu, ví dụ có một số n nào đó, mà không tồn tại i, chúng ta nói rằng n có tổng thời gian dừng vô hạn và phỏng đoán bị bác bỏ.

Nếu phỏng đoán bị sai, khi ấy bởi vì với một số ban đầu nào đó sẽ cho các số tiếp theo mà không chứa 1. Dãy số này sẽ phải đi vào một vòng lặp mà không có 1, hoặc tăng tiến mà không bị chặn. Vẫn chưa có dãy nào như vậy được tìm thấy.

Ví dụSửa đổi

Lấy ví dụ, bắt đầu bằng n = 12, ta có những dãy số sau 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

n = 19, mất lâu hơn để đạt tới 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Dãy đối với n = 27, như được liệt kê và vẽ trên đồ thị ở dưới, cần 111 bước lặp (41 bước qua số lẻ, được in đậm), tăng tiến đến giá trị cao nhất là 9232 trước khi thu giảm về 1.

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (dãy số A008884 trong bảng OEIS)

Numbers with a total stopping time longer than that of any smaller starting value form a sequence beginning with:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, … (dãy số A006877 trong bảng OEIS).

The starting values whose maximum trajectory point is greater than that of any smaller starting value are as follows:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511,... (dãy số A006884 trong bảng OEIS)

Number of steps for n to reach 1 are

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24,... (dãy số A006577 trong bảng OEIS)

The longest progression for any initial starting number

nhỏ hơn 10 là 9, với 19 bước lặp,
nhỏ hơn 100 là 97, với 118 bước lặp,
nhỏ hơn 1.000 là 871, với 178 bước lặp,
nhỏ hơn 10.000 là 6.171, với 261 bước lặp,
nhỏ hơn 100.000 là 77.031, với 350 bước lặp,
nhỏ hơn 1 triệu là 837.799, với 524 bước lặp,
nhỏ hơn 10 triệu là 8.400.511, với 685 bước lặp,
nhỏ hơn 100 triệu là 63.728.127, với 949 bước lặp,
nhỏ hơn 1 tỷ là 670.617.279, với 986 bước lặp,
nhỏ hơn 10 tỷ là 9.780.657.630, với 1132 bước lặp,[11]
nhỏ hơn 100 tỷ là 75.128.138.247, với 1228 bước lặp,
nhỏ hơn 1 nghìn tỷ là 989.345.275.647, với 1348 bước lặp,
nhỏ hơn 10 nghìn tỷ là 7.887.663.552.367, với 1563 bước lặp,
nhỏ hơn 100 nghìn tỷ là 80.867.137.596.217, với 1662 bước lặp,
nhỏ hơn 1 triệu tỷ là 942.488.749.153.153, với 1862 bước lặp,
nhỏ hơn 10 triệu tỷ là 7.579.309.213.675.935, với 1958 bước lặp, và
nhỏ hơn 100 triệu tỷ là 93.571.393.692.802.302, với 2091 bước lặp.[12]

Note: these numbers are the lowest ones with the indicated step count, but not necessarily the only ones below the given limit. For instance, 9,780,657,631 has 1132 steps as well.

The powers of two converge to one quickly because   is halved   times to reach one, and is never increased.

Đọc thêmSửa đổi

  • The Ultimate Challenge: the 3x+1 problem:
This volume,[13] edited by Jeffrey Lagarias and published by the American Mathematical Society, is a compendium of information on the Collatz conjecture, methods of approaching it and generalizations. It includes two survey papers by the editor and five by other authors, concerning the history of the problem, generalizations, statistical approaches and results from the theory of computation. It also includes reprints of early papers on the subject (including an entry by Lothar Collatz).

Tham khảoSửa đổi

  1. ^ O'Connor, J.J.; Robertson, E.F. (2006). “Lothar Collatz”. St Andrews University School of Mathematics and Statistics, Scotland. 
  2. ^ Maddux, Cleborne D.; Johnson, D. Lamont (1997). Logo: A Retrospective. New York: Haworth Press. tr. 160. ISBN 0-7890-0374-0. The problem is also known by several other names, including: Ulam's conjecture, the Hailstone problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and the Collatz problem. 
  3. ^ a ă Lagarias, Jeffrey C. (1985). “The 3x + 1 problem and its generalizations”. The American Mathematical Monthly 92 (1): 3–23. JSTOR 2322189. 
  4. ^ According to Lagarias (1985)[3] p. 4, the name "Syracuse problem" was proposed by Hasse in the 1950s, during a visit to Syracuse University.
  5. ^ Pickover, Clifford A. (2001). Wonders of Numbers. Oxford: Oxford University Press. tr. 116–118. ISBN 0-19-513342-0. 
  6. ^ “Hailstone Number”. MathWorld. Wolfram Research. 
  7. ^ Hofstadter, Douglas R. (1979). Gödel, Escher, Bach. New York: Basic Books. tr. 400–2. ISBN 0-465-02685-0. 
  8. ^ Guy, Richard K. (2004). “"E17: Permutation Sequences"”. Unsolved problems in number theory (ấn bản 3). Springer-Verlag. tr. 336–7. ISBN 0-387-20860-7. Zbl 1058.11001. 
  9. ^ Guy, R. K. (1983). “Don't try to solve these problems”. Amer. Math. Monthly 90: 35–41. JSTOR 2975688. doi:10.2307/2975688.  By this Erdos means that there aren't powerful tools for manipulating such objects.
  10. ^ Lagarias, Jeffrey C. biên tập (2010). The ultimate challenge: the 3x+1 problem. Providence, R.I.: American Mathematical Society. tr. 4. ISBN 0821849409. 
  11. ^ Leavens, Gary T.; Vermeulen, Mike (tháng 12 năm 1992). “3x+1 Search Programs”. Computers & Mathematics with Applications 24 (11): 79–99. doi:10.1016/0898-1221(92)90034-F. 
  12. ^ Roosendaal, Eric. “3x+1 Delay Records”. Truy cập ngày 30 tháng 6 năm 2017.  (Note: "Delay records" are total stopping time records.)
  13. ^ Lagarias, Jeffrey C. biên tập (2010). The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. ISBN 978-0-8218-4940-8. Zbl 1253.11003. 

Liên kết ngoàiSửa đổi