From 78e6b29cb7d95c2ef5984a98a4028406b0977f57 Mon Sep 17 00:00:00 2001
From: Marvin Borner
Date: Wed, 5 Mar 2025 20:47:24 +0100
Subject: Better primality test

---
 std/Number/Unary.bruijn | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

(limited to 'std/Number/Unary.bruijn')

diff --git a/std/Number/Unary.bruijn b/std/Number/Unary.bruijn
index c372983..cd4d642 100644
--- a/std/Number/Unary.bruijn
+++ b/std/Number/Unary.bruijn
@@ -17,6 +17,14 @@ uid [[[extract (2 inc init)]]] ⧗ Unary → Unary
 :test (uid (+1u)) ((+1u))
 :test (uid (+5u)) ((+5u))
 
+# folds unary number left
+foldl [[1 [0 1]]] ⧗ Unary → a
+
+:test (foldl [[1 (1 (1 0))]]) ([[0 1 1 1]])
+
+# unary infinity
+∞ [[[0 0] [2 (0 0)]]]
+
 # returns true if a unary number is zero
 zero? [0 [false] true] ⧗ Unary → Boolean
 
@@ -166,4 +174,16 @@ hyperfac [[1 [[(0 0) (1 [[2 1 (1 0)]])]] [1] i]] ⧗ Unary → Unary
 
 # Wilson's theorem
 # very inefficient but very golfable
-prime? [=?(++(fac --0) % 0)] ⧗ Unary → Boolean
+prime?* [=?(++(fac --0) % 0)] ⧗ Unary → Boolean
+
+# more efficient primality test, based on Tromp's characteristic sequence
+# golfed to 208 bit
+prime? [0 [0 ki] [0 ki [0 ki (sieve y s0)]] k] ⧗ Unary → Boolean
+	sieve [0 [[[0 k ([3 0 (4 0)] [[[[0 2 (1 (5 3))]]]])]]]]
+	s0 [[[[0 ki (1 3)]]]]
+
+:test (prime? (+2u)) ([[1]])
+:test (prime? (+3u)) ([[1]])
+:test (prime? (+4u)) ([[0]])
+:test (prime? (+5u)) ([[1]])
+:test (prime? (+6u)) ([[0]])
-- 
cgit v1.2.3