Six Ways to Implement Divisibility by Three in miniKanren

on YouTube ↗16m

" summary

Compares six concrete miniKanren implementations that decide n ≡ 0 (mod 3) over Oleg numerals, including multiplication-by-3, recursive plus-by-3, digit-sum modular tricks, and a relational DFA built from binary-state transitions. Benchmarks show multiplication relations are slow, DFA approaches run near zero ms, and a freshness-preserving variant (keeping bits uninstantiated) yields orders-of-magnitude more compact answers; introduces the reach metric to quantify how many ground numbers each relation implicitly represents.

AI-written summary · about

" chapters (13)

1. 0:00Divisibility by three intro
2. 1:02Oleg numerals in miniKanren
3. 3:52Divisibility by two via bit shift
4. 4:36Divisibility by three with math
5. 5:42Local vs global divisibility
6. 7:07Modular arithmetic for three
7. 8:54Binary DFA for three
8. 10:39DFA relation in code
9. 11:20Optimizing two-bit transitions
10. 12:05Benchmarking relations
11. 12:45Reach metric for solutions
12. 13:49Canonical summary
13. 14:11Q&A other divisibility