// ============================================================================
// 019 — Number Algorithms
// ============================================================================
// Classic number theory: GCD, primality test, collatz sequence.
//
// Run:   soma run 019_number_algorithms.cell run
// Expect:
//   GCD of 48 and 18: 6
//   Is 17 prime? yes
//   Is 15 prime? no
//   Collatz(6): 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (8 steps)

cell NumberAlgorithms {

    on run() {
        // GCD using Euclidean algorithm
        let g = gcd(48, 18)
        print("GCD of 48 and 18: {g}")

        // Primality testing
        let p1 = is_prime(17)
        print("Is 17 prime? {p1}")
        let p2 = is_prime(15)
        print("Is 15 prime? {p2}")

        // Collatz conjecture: if even n/2, if odd 3n+1
        let steps = collatz(6)
        print("{steps}")

        return "done"
    }

    // Euclidean GCD algorithm
    on gcd(a: Int, b: Int) {
        let x = a
        let y = b
        while y != 0 {
            let temp = y
            y = x % y
            x = temp
        }
        return x
    }

    // Trial division primality test
    on is_prime(n: Int) {
        if n < 2 {
            return "no"
        }
        let i = 2
        while i * i <= n {
            if n % i == 0 {
                return "no"
            }
            i = i + 1
        }
        return "yes"
    }

    // Collatz sequence — returns description string
    on collatz(n: Int) {
        let current = n
        let result = to_string(n)
        let steps = 0
        while current != 1 {
            if current % 2 == 0 {
                current = current / 2
            } else {
                current = 3 * current + 1
            }
            result += " -> "
            result += to_string(current)
            steps = steps + 1
        }
        result = "Collatz({n}): " + result
        result += " ({steps} steps)"
        return result
    }
}