Cây Collatz Đảo

Sinh cây ngược từ $1$ đi lên cho tới khi chạm số mục tiêu $m$

Về cây Collatz đảo

Thay vì đi xuôi từ một số $n$ về $1$ theo hàm $3n+1$, ta đi ngược: bắt đầu từ gốc là số $1$ rồi sinh dần lên trên. Gọi $S_k$ là tập các số (các đỉnh) sinh ra tại bước thứ $k$, khởi tạo với gốc:

$$S_1 = \{1\}, \qquad V_k = \bigcup_{i=1}^{k} S_i$$

Ở đây $V_k$ là tập tất cả các số đã từng sinh ra tính đến bước $k$ (dùng để phát hiện lặp lại). Tại bước $k+1$, mỗi số $n \in S_k$ sinh ra tối đa hai con — phép nghịch đảo của hàm Collatz:

Nhánh thứ nhất (luôn có): $c_1 = 2n$
Nhánh thứ hai (có điều kiện $n - 1 \equiv 0 \pmod 3$): $c_2 = \dfrac{n - 1}{3}$

Mỗi con $c$ vừa sinh sẽ dừng nhánh (không sinh tiếp) nếu $c = 1$, nếu $c \in V_k$ (đã từng xuất hiện), hoặc nếu $c = m$ (đã tìm thấy số mục tiêu). Cây này bao trùm tất cả số nguyên dương — đúng khi và chỉ khi phỏng đoán Collatz đúng.

Cây sinh từng bước (BFS)

💡 Kéo chuột để di chuyển 💡 Cuộn để phóng to / thu nhỏ

Đang hoạt động Đã dừng (lặp / n=1) Đường tới mục tiêu

Thông tin khoa học

Vì sao lại đi ngược?

Hàm Collatz xuôi $f(n)$ là hàm nhiều-một: nhiều số có thể cùng ánh xạ về một số. Đảo ngược nó biến bài toán thành một cây gốc tại $1$: mỗi số $n$ có thể đến từ $2n$ (luôn đúng, vì $2n$ chẵn nên $f(2n) = n$) và đôi khi từ $\frac{n-1}{3}$ (khi số đó là số lẻ hợp lệ). Phỏng đoán Collatz tương đương với khẳng định: cây ngược này chạm tới mọi số nguyên dương.

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

Tuy nhỏ, số $27$ nằm rất sâu trong cây: phải mất tới $111$ bước (chiều cao $k = 112$) để đi từ $1$ tới $27$, và đường đi leo lên tới đỉnh $9\,232$. Đường dẫn duy nhất tới nó bắt đầu như sau:

$$1 \to 2 \to 4 \to 8 \to 16 \to 5 \to 10 \to 20 \to 40 \to 80 \to 160 \to 53 \to \dots \to 9232 \to \dots \to 27$$

Trong cây ngược, số $27$ là con của $54$ (qua nhánh $c_1 = 2n$, vì $54 = 2 \cdot 27$). Vì số node tăng theo cấp số nhân, mô phỏng ở trên chỉ nên chạy với $m$ nhỏ để tránh treo trình duyệt.

Điều kiện dừng nhánh

$c = 1$: chạm lại gốc, khép chu trình $4 \to 2 \to 1$.
$c \in V_k$: số đã từng sinh ra — cắt tỉa để cây vẫn là cây (không có cạnh trùng).
$c = m$: đã tìm thấy mục tiêu, truy vết ngược lên gốc để bôi sáng đường đi.

Bùng nổ tổ hợp

Vì mỗi đỉnh sinh trung bình nhiều hơn một con, số node ở tầng $k$ tăng gần như theo cấp số nhân. Với $m = 27$ số node trước khi chạm mục tiêu lên tới hàng triệu — bất khả thi với BFS thuần trong trình duyệt. Đây là lý do các nghiên cứu thực nghiệm về Collatz thường giới hạn độ sâu hoặc dùng cấu trúc dữ liệu nén thay vì duyệt toàn cây.

Mẹo dùng: Hãy thử các giá trị $m$ nhỏ (ví dụ $5$, $6$, $7$, $10$) để thấy cây sinh mượt mà. Với $m$ lớn, cây phình rất nhanh và mô phỏng có thể chậm hoặc không hội tụ trong giới hạn hiển thị.

Nguồn: Wikipedia — Collatz conjecture.

Cây Collatz Đảo (Reverse Collatz Tree)

Sinh cây Collatz ngược từ số 1 đi lên bằng thuật toán BFS: mỗi đỉnh $n$ sinh nhánh $2n$ và (có điều kiện) $(n-1)/3$, dừng khi lặp lại, chạm 1 hoặc tìm thấy số mục tiêu $m$. Trực quan hóa bằng HTML5 Canvas với pan & zoom.