Add Goldbach's conjecture Catskill code example

Signed-off-by: Mel <mel@rnrd.eu>

1 files changed, 82 insertions, 0 deletions

diff --git a/examples/goldbach.csk b/examples/goldbach.csk
new file mode 100644
index 0000000..080b8c1
--- /dev/null
+++ b/examples/goldbach.csk
@@ -0,0 +1,82 @@
+# 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 goldbach < 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!")
+}