librarylibs/Numbers/src/Numbers.xtl

Numbers: number theory -- gcd and lcm, primes, factors, divisors, digits, integer square roots, Fibonacci numbers. Import it with an alias of your choice: "n:" u_se< "Numbers". Put libs/Numbers/src on XETAL_PATH ("just path"); the reference is libs/Numbers/docs. Names with l: are exported; those under h: are private to this file.

Whole numbers are X_eTaL's 64-bit Ints: a result past about 9.2e18 is an overflow error (big numbers are an ask, X6).

source

Divisors

ʰe̲uclid : Int -> Int -> Int

function (private) · line 13

Euclid on two whole numbers.

ʰe̲uclid ← { a b → b = 0 ? a̲bs a◆ b ʰe̲uclid a m̲od b }

Used in: ʰe̲uclid, ˡg̲cd

ˡg̲cd : Int -> Int -> Int

function · line 16

a g_cd b: the greatest common divisor, item by item.

ˡg̲cd ← { a b → a 'ʰe̲uclid e̲ach b }

Used in: ˡl̲cm

ˡl̲cm : Int -> Int -> Int

function · line 19

a l_cm b: the least common multiple, item by item (0 with a 0).

ˡl̲cm ← { a b →
  g ← a ˡg̲cd b
  (a̲bs a × b) d̲iv g + g = 0
}

ˡi̲sqrt : Int -> Int

function · line 25

i_sqrt n: the whole square root, the largest s with s * s <= n.

ˡi̲sqrt ← { n →
  s ← f̲loor (f̲loat n) ^ 0.5
  s ← s − (s × s) > n
  s + ((s + 1) × s + 1) ≤ n
}

Used in: ʰp̲rime1, ˡf̲actors

Primes

ʰs̲ieve : Int -> Int

function (private) · line 35

The sieve: the first candidate is prime; strike its multiples and go on, until the first is past the square root of the last.

ʰs̲ieve ← { c →
  0 = t̲ally c ? c
  p ← f̲irst c
  (p × p) > f̲irst -1 t̲ake c ? c
  p c̲at ʰs̲ieve (0 ≠ c m̲od p) r̲eplicate c
}

Used in: ʰs̲ieve, ˡp̲rimes

ˡp̲rimes : Int -> Int

function · line 43

p_rimes n: the primes up to n (Eratosthenes).

ˡp̲rimes ← { n → n < 2 ? 0 r̲eshape 0◆ ʰs̲ieve 1 d̲rop r̲ange n }

Used in: p

ʰp̲rime1 : Truthy a => Int -> a

function (private) · line 46

One whole number: prime or not.

ʰp̲rime1 ← { n → n < 2 ? 0 = 1◆ n < 4 ? 1 = 1◆ '∧ r̲/ 0 ≠ n m̲od 1 d̲rop r̲ange ˡi̲sqrt n }

Used in: ˡp̲rime?

ˡp̲rime? : Truthy a => Int -> a

function · line 49

p_rime? v: whether each item is prime.

ˡp̲rime? ← { v → 'ʰp̲rime1 e̲ach v }

Used in: ᵘg̲oldbach

ˡf̲actors : Int -> Int

function · line 53

f_actors n: the prime factors of a whole number, smallest first, with repeats (12 is 2 2 3).

ˡf̲actors ← { n →
  n < 2 ? 0 r̲eshape 0
  c ← (1 d̲rop r̲ange ˡi̲sqrt n) c̲at n         ⍝ candidates, n itself last
  d ← f̲irst (0 = n m̲od c) r̲eplicate c       ⍝ the smallest divisor
  d c̲at ˡf̲actors n d̲iv d
}

Used in: ˡf̲actors

ˡd̲ivisors : Int -> Int

function · line 61

d_ivisors n: every divisor of a whole number, in order.

ˡd̲ivisors ← { n → r ← r̲ange n◆ (0 = n m̲od r) r̲eplicate r }

Used in: s

Digits

ˡb̲ase : Int -> Int -> Int

function · line 67

b b_ase n: the digits of a whole number n >= 0 in base b, most significant first.

ˡb̲ase ← { b n →
  b < 2 ? @ p̲anic< "a base is 2 or more, not {b}"
  n < 0 ? @ p̲anic< "b_ase writes whole numbers 0 or more, not {n}"
  n = 0 ? 1 r̲eshape 0
  d ← (64 r̲eshape b) e̲ncode n
  (n̲ot '∧ s̲\ d = 0) r̲eplicate d
}

p̲anic< expands to

(⎕P̲ANIC ("a base is 2 or more, not " c̲at (f̲ormat (b))))

p̲anic< expands to

(⎕P̲ANIC ("b_ase writes whole numbers 0 or more, not " c̲at (f̲ormat (n))))

Used in: ˡd̲igits

ˡd̲igits : Int -> Int

function · line 76

d_igits n: the decimal digits of a whole number.

ˡd̲igits ← { n → 10 ˡb̲ase n }

Sequences

ˡf̲ib : Num a => Int -> a

function · line 81

f_ib n: the first n Fibonacci numbers, 1 1 2 3 5 ...

ˡf̲ib ← { n →
  n ≤ 2 ? n t̲ake 1 1
  (n − 2) '{ v → v c̲at '+ r̲/ -2 t̲ake v } p̲ower 1 1
}