C++ Program: Collatz Conjecture (3n+1 Problem)

Collatz Conjecture: เริ่มจาก n ใดๆ ทำซ้ำ: คู่→n/2, คี่→3n+1 สุดท้ายจะถึง 1 เสมอ (ยังไม่พบ Counterexample)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

bool reaches_one(int n, unordered_set& visited) {
    if (n == 1) return true;
    if (visited.count(n)) return false; // Loop detected
    visited.insert(n);
    return (n % 2) ? reaches_one(3*n + 1, visited)
                   : reaches_one(n/2, visited);
}

bool check_collatz(int n) {
    unordered_set visited;
    return reaches_one(n, visited);
}

int main() {
    int n = 234;
    cout << (check_collatz(n) ? "Yes" : "No");
    return 0;
}

ผลลัพธ์

Yes

ลำดับสำหรับ n=234

234 → 117 → 352 → 176 → 88 → 44 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Iterative Version (ไม่ใช้ Recursion)

bool collatz_iterative(long long n) {
    unordered_set seen;
    while (n != 1) {
        if (seen.count(n)) return false;
        seen.insert(n);
        n = (n % 2) ? 3*n + 1 : n/2;
    }
    return true;
}

ข้อสังเกต

• Conjecture นี้ยังไม่ได้พิสูจน์ทางคณิตศาสตร์ (Unsolved Problem)
• ตรวจสอบแล้วถึง 2⁶⁸ ยังไม่พบ Counterexample
• ใช้ long long ป้องกัน Overflow (3n+1 อาจใหญ่เกิน int)
• ใช้ unordered_set ตรวจจับ Loop (Cycle Detection)