# goldbach.csk
#
# verify a slice of goldbach's conjecture, the claim
# that every even integer greater than two is the sum of two primes.
# we cross-check our prime sieve against a known prime ranking, then
# walk the even numbers in [4, ceiling] looking for a counter-example.
#
# see: https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
#
# Copyright (c) 2026, Mel G. <mel@rnrd.eu>
#
# SPDX-License-Identifier: MPL-2.0

# trial-division primality test
# also known as, the dumbest way to check a number's primality,
# made dumber by us not having the list of primes to check against,
# thus having to resort to uneven numbers instead.
is_prime = fun (n int) bool {
    if n < 2 {
        return false
    }
    if n == 2 {
        return true
    }
    if n % 2 == 0 {
        return false
    }
    # all uneven numbers less than or equal to sqrt(n)
    for d int = 3, d * d <= n, d = d + 2 {
        if n % d == 0 {
            return false
        }
    }
    return true
}

# the n-th prime (1-indexed): 2, 3, 5, 7, 11, ...
nth_prime = fun (n int) int {
    var found int = 0
    var current int = 1
    while found < n {
        current++
        if is_prime(current) {
            found++
        }
    }
    return current
}

# goldbach decomposition
# returns smaller of the two primes p, q with p + q == n.
# returns -1 if none exists in [2, n / 2].
goldbach = fun (n int) int {
    for p int = 2, p <= n / 2, p++ {
        if is_prime(p) {
            if is_prime(n - p) {
                return p
            }
        }
    }
    return -1 # counter-example!
}

main = fun () {
    var ceiling int = 200

    println("proving goldbach up to 200...")
    for n int = 4, n <= ceiling, n = n + 2 {
        var p int = goldbach(n)

        if p < 0 {
            printf("counter-example found at %ld!\n", n)
            println("goldbach conjecture disproven!")
            exit(1)
        }

        var q int = n - p
        printf("%ld = %ld + %ld\n", n, p, q)
    }

    println("no counter-example, conjecture holds!")
}