Bí mật của một thuật toán
La Trí Dũng
Chúng ta sẽ làm quen với một bài toán, hay nói đúng hơn là một thuật toán rất đơn giản.
Thuật toán này đơn giản đến nỗi chắc các bạn sau khi xem qua sẽ đều “tặc lưỡi”: Có thể
mà ông ta (tức tôi) cũng làm ra vẻ quan trọng, cũng đồi viết về những “bí mật” của nó cơ
chứ. Các bạn suy nghĩ như vậy cũng không sai nhiều đâu. Nhưng các bạn chớ vội bỏ đi
nhé, hãy cùng tôi, chúng ta cùng nhau tìm hiểu và khám phá. Tôi tin rằng những khám phá
mà các bạn sẽ thấy, chỉ một chút nữa thôi sẽ vô cùng thú vị. Còn ngay bây giờ, mỗi bạn
đều nên (dù chỉ một lần trong đời) ngồi bên máy tính, viết và chạy thử bài toán này. Thuật
toán này vô cùng đơn giản, đầu vào là một số tự nhiên, đầu ra là … một dãy số.
Chúng ta hãy định nghĩa một cách chính xác thuật giải này.
Thuật toán 3N+1
Input: số tự nhiên k
1.Nếu k=1 thì dừng chương trình.
2.Nếu k chẵn thì đặt k=1/2; nếu k lẻ thì đặt k=3k+1.
3.Quay lại bước
Ví dụ: Nếu bắt đầu với k=34 thì thuật toán trên sẽ sinh ra dãy:
34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Như vậy thuật toán sẽ sinh ra một dãy số, nó chỉ dừng lại khi gặp số 1. Khảo sát, tìm hiểu
thuật toán chính là việc khảo sát, khám phá những bí mật của dãy số này.
Câu hỏi thứ nhất: Dãy số của thuật toán trên có phải bao giờ cũng hữu hạn?
Câu hỏi này được đặt ra một cách rất tự nhiên. Hay nói một cách khác, thuật toán 3N+1
trên có phải là một thuật toán đúng đắn hay không
Ta định nghĩa hàm S như sau:
S(k)=số bước phải thực hiện của thuật toán cho giá trị ban đầu k, hay nói cách khác S(k) là
độ dài của dãy số sinh bởi thuật toán 3N+1. Bằng cách định nghĩa hàm S như vậy, ta đưa
toán của ta thành câu hỏi: Liệu hàm S có xác định với mọi số tự nhiên k hay không?
Rất tiếc và cũng rất kỳ lạ rằng câu hỏi tưởng chừng đơn giản đó cho đến tận ngày hôm nay
vẫn chưa có câu trả lời: bài toán về tính đúng đắn của thuật toán 3N+1 vẫn còn bỏ ngỏ và
như vậy tất cả chúng ta hãy còn có điều kiện để khám phá những bó ẩn còn tiềm tàng của
thuật toán này. Chỉ biết rằng với những tính toán của tất cả các máy tính hiện đại nhất mà

trong tất cả các trường hợp còn lại S(k)<35.
5. Ta nhận xét rằng có tồn tại một số dãy các số k liên tiếp có S(k) giống nhau, chẳng hạn
S(14)=S(15)=17, S(28)=S(29)=S(30)=18, S(98)=S(99)=S(100)=S(101)=S(102)=25. Phải
chăng đó lạo là một qui luật nữa?
Để minh họa ta xét 2 dãy với cặp k=14 và 15:
Để ý đến tính lặp lại của các số có cùng vị trí trong 2 dãy. Hiện tượng này gợi ý cho ta một
cách tiếp cận mới với bài toán, đó là tìm qui luật của các lớp số có cùng độ dài s của dãy.
7. Kí hiệu C(s) là tập các số mà thuật toán kết thúc sau s bước. Như vậy, số k thuộc C(s)
khi và chỉ khi S(k)=s. Ví dụ, C(0)= {1}, C(2)= {2}, …, C(5)= {32,5}. Như vậy ta lại có
thêm một bài toán nữa: cần tính C(s).
Việc tính C(s) tốt nhất nên tiến hành theo phương pháp truy hồi như sau:
C(0)= {1}.
Giả sử C(s) = {k1, k2,…,kM}. Khi đó C(s+1) chứa:
1) số 2ki với mỗi ki thuộc C(s),
2) số (ki-1)/3 với mỗi ki thuộc C(s) có dạng 6n+4.
Kết quả của việc thực hiện thuật toán cho ta một cây mà một phần của nó thể hiện trên
hình sau:
Mỗi mức của cây là một lớp C(s), s=0,1,2,.., còn đường đi từ mỗi đỉnh tới gốc chính là dãy
số sinh bởi thuật toán
1.Hình vẽ này giải thích vì sao trong bảng trên số 64 lại ít gặp như vậy. Để số 64 là lũy
thừa của 2 đầu tiên trong dãy thì k phải là một trong các số nằm trên nhánh cây trên 21, mà
21 chia hết cho 3 nên tất nhiên các số trên nhánh này không thể có dạng 6n+4 được. Do đó,
từ công thức truy hồi trên ta suy ra số 64 là lũy thừa của 2 đầu tiên từng dãy khi và chỉ khi
k có dạng 21.2m với m bất kì.
2.Gọi n(s) là số các phần tử của tập hợp C(s). Thuật toán truy hồi để tính các lớp C(s) dẫn
tới công thức tuy hồi tính n(s).
Giả sử e(s) và o(s) tương ứng là số các phần tử chẵn và lẻ của C(s) thì n(s)=e(s)+o(s). Hơn
nữa với mỗi số s ta có e(s)=n(s-1) và mỗi số lẻ trong C(s) thu được từ số dạng 6n+4 trong
C(s-1).
Giả sử ràng khoảng một phần ba các số chẵn trong mỗi tập C(s) có dạng 6n+4 (điều này