sourcelibs/Numbers/src/Numbers.xtl
1⍝# Numbers: number theory -- gcd and lcm, primes, factors, divisors,
2⍝# digits, integer square roots, Fibonacci numbers.
3⍝# Import it with an alias of your choice: "n:" u_se< "Numbers".
4⍝# Put libs/Numbers/src on XETAL_PATH ("just path"); the reference is libs/Numbers/docs.
5⍝# Names with l: are exported; those under h: are private to this file.
6⍝#
7⍝# Whole numbers are X_eTaL's 64-bit Ints: a result past about 9.2e18
8⍝# is an overflow error (big numbers are an ask, X6).
9
10⍝## Divisors
11
12⍝# Euclid on two whole numbers.
13ʰe̲uclid ← { a b → b = 0 ? a̲bs a◆ b ʰe̲uclid a m̲od b }
14
15⍝# a g_cd b: the greatest common divisor, item by item.
16ˡg̲cd ← { a b → a 'ʰe̲uclid e̲ach b }
17
18⍝# a l_cm b: the least common multiple, item by item (0 with a 0).
19ˡl̲cm ← { a b →
20 g ← a ˡg̲cd b
21 (a̲bs a × b) d̲iv g + g = 0
22}
23
24⍝# i_sqrt n: the whole square root, the largest s with s * s <= n.
25ˡi̲sqrt ← { n →
26 s ← f̲loor (f̲loat n) ^ 0.5
27 s ← s − (s × s) > n
28 s + ((s + 1) × s + 1) ≤ n
29}
30
31⍝## Primes
32
33⍝# The sieve: the first candidate is prime; strike its multiples and go
34⍝# on, until the first is past the square root of the last.
35ʰs̲ieve ← { c →
36 0 = t̲ally c ? c
37 p ← f̲irst c
38 (p × p) > f̲irst -1 t̲ake c ? c
39 p c̲at ʰs̲ieve (0 ≠ c m̲od p) r̲eplicate c
40}
41
42⍝# p_rimes n: the primes up to n (Eratosthenes).
43ˡp̲rimes ← { n → n < 2 ? 0 r̲eshape 0◆ ʰs̲ieve 1 d̲rop r̲ange n }
44
45⍝# One whole number: prime or not.
46ʰp̲rime1 ← { n → n < 2 ? 0 = 1◆ n < 4 ? 1 = 1◆ '∧ r̲/ 0 ≠ n m̲od 1 d̲rop r̲ange ˡi̲sqrt n }
47
48⍝# p_rime? v: whether each item is prime.
49ˡp̲rime? ← { v → 'ʰp̲rime1 e̲ach v }
50
51⍝# f_actors n: the prime factors of a whole number, smallest first,
52⍝# with repeats (12 is 2 2 3).
53ˡf̲actors ← { n →
54 n < 2 ? 0 r̲eshape 0
55 c ← (1 d̲rop r̲ange ˡi̲sqrt n) c̲at n ⍝ candidates, n itself last
56 d ← f̲irst (0 = n m̲od c) r̲eplicate c ⍝ the smallest divisor
57 d c̲at ˡf̲actors n d̲iv d
58}
59
60⍝# d_ivisors n: every divisor of a whole number, in order.
61ˡd̲ivisors ← { n → r ← r̲ange n◆ (0 = n m̲od r) r̲eplicate r }
62
63⍝## Digits
64
65⍝# b b_ase n: the digits of a whole number n >= 0 in base b, most
66⍝# significant first.
67ˡb̲ase ← { b n →
68 b < 2 ? @ p̲anic< "a base is 2 or more, not {b}"
69 n < 0 ? @ p̲anic< "b_ase writes whole numbers 0 or more, not {n}"
70 n = 0 ? 1 r̲eshape 0
71 d ← (64 r̲eshape b) e̲ncode n
72 (n̲ot '∧ s̲\ d = 0) r̲eplicate d
73}
74
75⍝# d_igits n: the decimal digits of a whole number.
76ˡd̲igits ← { n → 10 ˡb̲ase n }
77
78⍝## Sequences
79
80⍝# f_ib n: the first n Fibonacci numbers, 1 1 2 3 5 ...
81ˡf̲ib ← { n →
82 n ≤ 2 ? n t̲ake 1 1
83 (n − 2) '{ v → v c̲at '+ r̲/ -2 t̲ake v } p̲ower 1 1
84}