Giả thuyết Collatz

Giả thuyết Collatz đề 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 đó 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. Nó còn được biết đến là phỏng đoán 3"n" + 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; 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), hoặc các số ngạc nhiên.
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." Ông cũng hứa giành tặng $500 cho ai đưa ra được lời giải. 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."
Tổng quan.
Xét một phép toán sau tác động lên một số nguyên dương bất kỳ:
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à: formula_3 là giá trị của formula_4 áp dụng với formula_5 bằng cách lặp đệ quy formula_6 lần; formula_7).
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 "a""i" = 1 được gọi là tổng thời gian dừng của "n". 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ụ.
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.
Những số với 1 tổng thời gian dừng dài hơn giá trị xuất phát nhỏ hơn bất kỳ tạo nên 1 chuỗi bắt đầu với : 
Những giá trị bắt đầu cái mà quỹ đạo cực đại là lớn hơn bất kỳ giá trị xuất phát nhỏ hơn được kể dưới :
Số bước để n tiến tới 1 là 
Tiến trình dài nhất cho bất kỳ số xuất phát ban đầu 
Chú ý: những số này là những số thấp nhất với số bước tính đã được chỉ ra, nhưng không cần chỉ ra những số duy nhất đằng sau giới hạn đã cho. Ví dụ, 9,780,657,631 có 1132 bước như thế.
Những luỹ thừa cúa 2 hội tụ tới 1 nhanh chóng bởi vì formula_8 được giảm đi 1 nửa n lần để đạt đến 1, và không bao giờ tăng tiến.