Research shelf / Mathematics / Prime meta-pattern
Written Updated
What a neural network learns about primes, and why it still loses
Train a network to tell primes from composites, then refuse to look at the feature-generating code and work out what it learned from the weights alone. The answer is the small-prime trial-division sieve on 6k±1 candidates, in that order, with strikingly stable feature importances across five orders of magnitude. The follow-up paper then benchmarks the network against the thing it rediscovered, and reports the loss.
Experiments were run and the numbers are reported here.
Six MLPs trained to classify primes across five orders of magnitude, interpreted from weights alone — they rediscover trial division on the 6k±1 lattice, and then lose to it by 30–80×.
Six multilayer perceptrons are trained at scales s = log₁₀ n ∈ {3,…,8} on a deliberately rich, redundant 105-dimensional feature set. Interpretation uses two independent routes: black-box weight analysis (singular-value spectra, Hill exponents, effective rank, integrated-gradient attribution by feature group) and knowledge distillation into decision trees and sparse L1 logistic regressions.
Both routes converge on the same function. The top features, in order and at every scale, are is_6k_pm1, then n mod 5, 7, 11, 13, 17, 19 — the small-prime trial-division sieve, restricted to the 6k±1 lattice on which all primes above 3 live. Two clean exponential scaling laws fall out: the residue-feature attribution share decays as 0.543·exp(−0.041·s) while the binary-bit share grows as 2.23·exp(0.219·s), with Hill α ≈ 3.19 constant throughout.
The second paper operationalises the finding into three generators and benchmarks them head-to-head. The conventional baseline (6k±1 enumeration, small-prime pre-filter, Sorenson–Webster deterministic Miller–Rabin) is exactly correct and fastest. The NN-augmented variant is also exactly correct — the verifier guarantees it — and 30–80× slower. The pure-NN variant is not a primality test at all. The conclusion the paper draws is that the network’s value here is interpretive, not generative.
Every number, and what stands behind it
A claim is only worth the evidence attached to it. Each row below carries its basis: measured on the author’s own hardware, derived from the construction, measured on synthetic data, projected from literature, or simply cited.
| Claim | Figure | Basis | Context |
|---|---|---|---|
| Function recovered by distillation | small-prime sieve on 6k±1 | Measured | Same feature ordering at every scale s = 3…8 |
| Residue-attribution scaling law | 0.543 · exp(−0.041 · s) | Measured | Integrated-gradient attribution by feature group |
| Binary-bit attribution scaling law | 2.23 · exp(0.219 · s) | Measured | Same analysis, opposite direction |
| Hill tail exponent | α ≈ 3.19 | Measured | Constant across all six scales |
| NN-augmented generator speed | 30–80× slower | Measured | 50 random starts × 5 consecutive primes per scale |
| Pure-NN primality recall | 0.21–0.68 | Measured | At τ = 0.5; skip rate 2–22% |
| Verifier exactness bound | exact for n < 3.317 × 10²⁴ | Cited | Sorenson–Webster deterministic Miller–Rabin |
| Probabilistic error above that bound | ≈9.1 × 10⁻¹³ per call | Derived | k = 20 rounds, 4⁻²⁰ |
| Cross-study agreement | every cross-checkable claim | Measured | Against an independent non-NN baseline study |
Measured — author-run experiment on the stated setup. Synthetic — measured, but on synthetic rather than real data. Derived — follows from the stated construction or proof. Projected — paper-stated projection, not an author-run benchmark. Cited — taken from external literature.
Run the sieve the network rediscovered
Three generators scan the same window of consecutive integers. The conventional one walks the 6k±1 lattice, trial-divides by small primes, and verifies with Miller–Rabin. The augmented one swaps the trial division for the distilled scorer and keeps the verifier. The third uses the scorer alone. Move the scale up and watch which one stops working.
6k±1 sieve — live in your browser
| Conventional | NN-augmented | Pure NN | |
|---|---|---|---|
| Primes found | — | — | — |
| Miller–Rabin calls | — | — | 0 |
| Primes skipped | — | — | — |
| Filter cost per candidate | — | — | — |
| False positives | None | None | Recall — |
How it works
- Weights-only interpretation. The feature-generating source is deliberately not consulted; only trained weights and gradients are used.
- Two independent extraction routes. Spectral weight analysis and distillation into trees and sparse logistic models, cross-checked against each other.
- Head-to-head generator benchmark. Three generators at six scales, 50 random starts × 5 consecutive primes each.
- Deterministic verification. Sorenson–Webster Miller–Rabin, exact below 3.317 × 10²⁴, with k = 20 probabilistic rounds above.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- The network does not discover a prime formula. No such formula is known and the prime-counting function is provably non-elementary — the paper says so in its own setup.
- The pure-NN generator has recall between 0.21 and 0.68. It is not a primality test and is not presented as one.
- The NN-augmented generator is slower than the classical one it was built to improve, by 30–80×.
- Distillation recovers what the features made available. A different feature set would recover a different function.
- Scales stop at s = 8. Behaviour at cryptographic sizes is untested and not claimed.
Free under AGPL-3.0+ for almost everyone
Personal use, charities, education and organisations under AUD 50,000 a year pay nothing. A tiered commercial licence covers everyone else.