CRT Clustering

F41: AWS/Google ML. CC0.

Every number in Z/214,414,200 belongs to a coupling class: which prime divides it. gcd(n, N) reveals it in O(1). No iteration. No hyperparameters. No training data. The ring decides.

How It Works

Coupling Class (PROVED)
For any n in Z/214,414,200, gcd(n, N) reveals which primes divide n. This defines 10 clusters: zero (gcd=N), unit (gcd=1), 7 pure classes (exactly one prime divides), and mixed (multiple primes divide). Assignment is O(1): one GCD + one factorization test. No iteration. Deterministic.
10 clusters
Algebraically forced
zero, unit, 2-class, 3-class, 5-class, 7-class, 11-class, 13-class, 17-class, mixed. Not chosen -- discovered.
O(1)
One GCD operation
K-means: O(NKI) for N points, K clusters, I iterations. CRT: O(N).
No hyperparameters
K emerges from the ring
K-means: choose K. DBSCAN: choose epsilon, minPts. CRT: the ring decides.
Deterministic
Same input = same cluster
K-means depends on initialization. CRT: unique, deterministic, algebraic.

Try It

Number of points (10-1000):

Generates random data points in Z/214,414,200 and classifies each by coupling class. Shows distribution + first 20 assignments.

CRT Clustering vs K-Means

ComplexityK-means: O(NKI), typically 20+ iterationsCRT class: O(N). One pass. Done.Cluster countK-means: choose K (hyperparameter)CRT: 10 classes emerge from ring structureInitializationK-means: random centroids (non-deterministic)CRT: deterministic. GCD is unique.StabilityK-means: different runs = different clustersCRT: same input = same class. Always.InterpretabilityK-means: centroid vectors (opaque)CRT: classes = prime divisibility (algebraic meaning)Patent statusAWS SageMaker, Google AutoMLCC0. Public domain. Forever.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.