diff options
| -rw-r--r-- | std/Math.bruijn | 9 | ||||
| -rw-r--r-- | std/Number/Unary.bruijn | 22 |
2 files changed, 28 insertions, 3 deletions
diff --git a/std/Math.bruijn b/std/Math.bruijn index 84cfae2..534afae 100644 --- a/std/Math.bruijn +++ b/std/Math.bruijn @@ -223,8 +223,7 @@ pascal L.iterate [L.zip-with …+… (L.{}(+0) ++ 0) (0 ; (+0))] (L.{}(+1)) # characteristic prime sequence by Tromp characteristic-primes ki : (ki : (sieve s0)) ⧗ (List Bool) - sieve y [[k : ([(2 0) (y' 0)] (ssucc 0))]] - y' [[0 0] [1 (0 0)]] + sieve y [[k : ([(2 0) (y 0)] (ssucc 0))]] ssucc [[[[1 : (0 (3 2))]]]] s0 [[[ki : (0 2)]]] @@ -237,6 +236,12 @@ primes* L.nub ((…≠?… (+1)) ∘∘ gcd) (L.iterate ++‣ (+2)) ⧗ (List Nu # primality test prime? L.index characteristic-primes ⧗ Number → Boolean +:test (prime? (+2)) ([[1]]) +:test (prime? (+3)) ([[1]]) +:test (prime? (+4)) ([[0]]) +:test (prime? (+5)) ([[1]]) +:test (prime? (+6)) ([[0]]) + # prime factors factors \divs primes ⧗ Number → (List Number) divs y [[&[[&[[3 ⋅ 3 >? 4 case-1 (=?0 case-2 case-3)]] (quot-rem 2 1)]]]] 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]]) |