Bài Toán 3n + 1 (Collatz)

Nhập một số nguyên dương để xem chuỗi biến đổi về 1

Về bài toán Collatz

Bài toán Collatz, hay còn gọi là phỏng đoán $3n + 1$, là một trong những bài toán chưa có lời giải nổi tiếng nhất trong toán học. Quy luật của nó rất đơn giản. Bắt đầu với một số nguyên dương $n$ bất kỳ, ta áp dụng hàm:

$$f(n) = \begin{cases} n/2 & \text{nếu } n \equiv 0 \pmod 2 \\ 3n + 1 & \text{nếu } n \equiv 1 \pmod 2 \end{cases}$$

Nếu $n$ là số chẵn, chia nó cho 2: $n \rightarrow n/2$
Nếu $n$ là số lẻ, nhân nó với 3 và cộng thêm 1: $n \rightarrow 3n + 1$

Phỏng đoán cho rằng, dù bạn bắt đầu với bất kỳ số nguyên dương nào, quá trình này cuối cùng cũng sẽ luôn đạt tới chu trình lặp $4 \rightarrow 2 \rightarrow 1$ và quay về số $1$.

Biểu đồ đường đi của n

Đỉnh cao nhất

0

Thông tin khoa học

Lịch sử & tên gọi

Bài toán do nhà toán học Lothar Collatz nêu ra năm 1937. Do được nhiều người phát hiện lại độc lập, nó mang rất nhiều tên: bài toán $3n+1$, phỏng đoán Ulam, bài toán Kakutani, phỏng đoán Thwaites, thuật toán Hasse, hay bài toán Syracuse.

Thời gian dừng (stopping time)

Với quỹ đạo $\;n,\, f(n),\, f^2(n),\, \dots$, người ta định nghĩa hai đại lượng: thời gian dừng là chỉ số nhỏ nhất mà dãy tụt xuống dưới giá trị ban đầu; thời gian dừng toàn phần là chỉ số nhỏ nhất mà dãy đạt tới $1$.

$$\sigma(n) = \min\{\, k \ge 1 : f^k(n) < n \,\}$$ $$\sigma_\infty(n) = \min\{\, k \ge 0 : f^k(n) = 1 \,\}$$

Ví dụ kinh điển: $n = 27$

Tuy nhỏ, số $27$ lại có quỹ đạo rất dài: dãy leo lên tới đỉnh $9\,232$ trước khi tụt về $1$, tổng cộng $111$ bước (trong đó có $41$ bước qua số lẻ). Đây là lý do $27$ được chọn làm giá trị mặc định của mô phỏng phía trên.

Kiểm chứng bằng máy tính

Phỏng đoán đã được kiểm chứng đúng cho mọi số nguyên dương tới khoảng $2^{71} \approx 2{,}36 \times 10^{21}$ — tất cả đều hội tụ về $1$. Tuy vậy, việc kiểm chứng bằng máy không thay thế được một chứng minh tổng quát.

Tiến triển toán học

Riho Terras (1976): chứng minh hầu hết số nguyên dương có thời gian dừng hữu hạn.
John Conway (1972): chứng minh các dạng tổng quát tự nhiên của bài toán là không quyết định được (thuật toán), liên hệ với hệ FRACTRAN.
Terence Tao (2019): chứng minh "hầu hết quỹ đạo Collatz đạt tới giá trị gần như bị chặn" — một trong những kết quả quan trọng nhất về bài toán trong nhiều thập kỷ.

Độ khó: Paul Erdős từng nhận xét "Toán học có lẽ chưa sẵn sàng cho những bài toán như thế này" và treo giải thưởng $\$500$. Năm 2010, Jeffrey Lagarias gọi đây là "một bài toán cực kỳ khó, hoàn toàn nằm ngoài tầm với của toán học hiện nay".

Nguồn: Wikipedia — Collatz conjecture.

Bài Toán Collatz 3n + 1

Nhập một số nguyên dương và xem trực quan chuỗi biến đổi Collatz về 1 qua biểu đồ HTML5 Canvas: số bước nhảy, số lần chia đôi, số lần 3n+1 và đỉnh cao nhất của quỹ đạo.