You are looking at historical revision 39576 of this page. It may differ significantly from its current revision.

math

Introduction

math is a chicken port of racket's math library.

The following documentation is largely taken directly from the racket documentation, but tweaked for the CHICKEN implementation.

math.number-theory
Congruences and modular arithmetic
[procedure] (divides? m n) -> boolean
m
integer
n
integer

Returns #t if m divides n, #f otherwise.

Examples:

> (divides? 2 9)
#f
> (divides? 2 8)
#t

Note that 0 cannot divide anything:

> (divides? 0 5)
#f
> (divides? 0 0)
#f

Practically, if (divides? m n) is #t, then (/ n m) will return an integer.

Wikipedia: Divisor

[procedure] (bezout a b c ...) -> (list-of integer)
a
integer
b
integer
c
integer

Given integers a b c ... returns a list of integers (list u v w ...) such that (gcd a b c ...) = (+ (* a u) (* b v) (* c w) ...).

Examples:

> (bezout 6 15)
(-2 1)
> (+ (* -2 6) (* 1 15))
3
> (gcd 6 15)
3

Wikipedia: Bézout's Identity

[procedure] (coprime? a b ...) -> boolean
a
integer
b
integer

Returns #t if the integers a b ... are coprime. Formally, a set of integers is considered coprime (also called relatively prime) if their greatest common divisor is 1.

Example:

> (coprime? 2 6 15)
#t

Wikipedia: Coprime

[procedure] (pairwise-coprime? a b ...) -> boolean
a
integer
b
integer

Returns #t if the integers a b ... are pairwise coprime, meaning that each pair of integers is coprime.

The numbers 2, 6 and 15 are coprime, but not pairwise coprime, because 6 and 15 share the factor 3:

> (pairwise-coprime? 2 6 15)
#f

Wikipedia:Pairwise Coprime

[procedure] (solve-chinese as ns) -> integer
as
(list-of integer)
ns
(list-of integer)

Given a length-k list of integers as and a length-k list of coprime moduli ns, (solve-chinese as ns) returns the least natural number x that is a solution to the equations

x = a₁ (mod n₁)
 ...
x = aₖ (mod nₖ)

The solution x is less than (* n1 ... nk).

The moduli ns must all be positive.

What is the least number x that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?

> (solve-chinese '(2 3 2) '(3 5 7))
23

Wikipedia: Chinese Remainder Theorem

[procedure] (quadratic-residue? a n) -> boolean
a
integer
n
integer

Returns #t if a is a quadratic residue modulo n, otherwise #f. The modulus n must be positive, and a must be nonnegative.

Formally, a is a quadratic residue modulo n if there exists a number x such that (* x x) = a (mod n). In other words, (quadratic-residue? a n) is #t when a is a perfect square modulo n.

Examples:

> (quadratic-residue? 0 4)
#f
> (quadratic-residue? 1 4)
#t
> (quadratic-residue? 2 4)
#f
> (quadratic-residue? 3 4)
#f

Wikipedia: Quadratic Residue

[procedure] (quadratic-character a p) -> integer
a
integer
b
integer

Returns the value of the quadratic character modulo the prime p. That is, for a non-zero a the number 1 is returned when a is a quadratic residue, and -1 is returned when a is a non-residue. If a is zero, then 0 is returned.

If a is negative or p is not positive, quadratic-character raises an error. If p is not prime, (quadratic-character a p) is indeterminate.

This function is also known as the Legendre symbol.

> (quadratic-character 0 5)
0
> (quadratic-character 1 5)
1
> (quadratic-character 2 5)
-1
> (quadratic-character 3 5)
-1

Wikipedia: Legendre Symbol

[procedure] (jacobi-symbol a n) -> integer
a
integer
n
integer

Computes the Jacobi symbol for any nonnegative integer a and any positive odd integer n.

If n is not an odd positive integer, (jacobi-symbol a n) throws an exception.

> (jacobi-symbol 1 1)
1
> (jacobi-symbol 8 11)
-1
> (jacobi-symbol 39 27)
0
> (jacobi-symbol 22 59)
1
> (jacobi-symbol 32 8)
Error: (jacobi-symbol) bad argument type - not an odd integer: 8

Wikipedia: Jacobi Symbol

[procedure] (modular-inverse a n) -> integer
a
integer
b
integer

Returns the inverse of a modulo n if a and n are coprime, otherwise raises an error. The modulus n must be positive, and a must be nonzero.

Formally, if a and n are coprime, b = (modular-inverse a n) is the unique natural number less than n such that (* a b) = 1 (mod n).

> (modular-inverse 2 5)
3
> (modulo (* 2 3) 5)
1

Wikipedia: Multiplicative Inverse

[procedure] (modular-expt a b n) -> integer
a
integer
b
integer
n
integer

Computes (modulo (expt a b) n), but much more efficiently. The modulus n must be positive, and the exponent b must be nonnegative.

> (modulo (expt -6 523) 19)
13
> (modular-expt -6 523 19)
13
> (modular-expt 9 158235208 19)
4
> ; don't try this at home!
  (modulo (expt 9 158235208) 19)
4
Parameterized Modular Arithmetic

The math.number-theory library supports modular arithmetic parameterized on a current modulus. For example, the code

(with-modulus n
  (mod= (modexpt a b) c))

corresponds with the mathematical statement a^b = c (mod n).

The current modulus is stored in a parameter that, for performance reasons, can only be set using with-modulus. (The basic modular operators cache parameter reads, and this restriction guarantees that the cached values are current. NOTE: I'm not entirely sure this is true for the chicken port, as a slightly more complicated racket syntax-case has been turned into a simple syntax-rule for (parameterize ...))

Wikipedia: Modular Arithmetic

[syntax] (with-modulus n body ...)
n
integer

Alters the current modulus within the dynamic extent of body. The expression n must evaluate to a positive integer.

By default, the current modulus is 1, meaning that every modular arithmetic expression that does not raise an error returns 0.

[procedure] (current-modulus) -> integer

Returns the current modulus.

Examples:

> (current-modulus)
1
> (with-modulus 5 (current-modulus))
5
[procedure] (mod x) -> integer
x
exact rational

Converts a rational number x to a natural number less than the current modulus.

If x is an integer, this is equivalent to (modulo x n). If x is a fraction, an integer input is generated by multiplying its numerator by its denominator’s modular inverse.

Examples:

> (with-modulus 7 (mod (* 218 7)))
0
> (with-modulus 7 (mod 3/2))
5
> (with-modulus 7 (mod/ 3 2))
5
> (with-modulus 7 (mod 3/7))
Error: (modular-inverse) bad argument type - not coprime to modulus 7: 7
[procedure] (mod+ a ...) -> integer
[procedure] (mod* a ...) -> integer
a
integer

Equivalent to (modulo (+ a ...) (current-modulus)) and (modulo (* a ...) (current-modulus)), respectively, but generate smaller intermediate values.

[procedure] (modsqr a) -> integer
[procedure] (modexpt a b) -> integer
a
integer
b
integer

Equivalent to (mod* a a) and (modular-expt a b (current-modulus)), respectively.

[procedure] (mod- a b ...) -> integer
a
integer
b
integer

Equivalent to (modulo (- a b ...) (current-modulus)), but generates smaller intermediate values. Note that (mod- a) = (mod (- a)).

[procedure] (mod/ a b ...) -> integer
a
integer
b
integer

Divides a by (* b ...), by multiplying a by the multiplicative inverse of (* b ...). The one-argument variant returns the modular inverse of a.

Note that (mod/ a b ...) is not equivalent to (modulo (/ a b ...) (current-modulus)); see mod= for a demonstration.

[procedure] (mod= a b ...) -> boolean
[procedure] (mod< a b ...) -> boolean
[procedure] (mod<= a b ...) -> boolean
[procedure] (mod> a b ...) -> boolean
[procedure] (mod>= a b ...) -> boolean
a
integer
b
integer

Each of these is equivalent to (op (mod a) (mod b) ...), where op is the corresponding numeric comparison function. Additionally, when given one argument, the inequality tests always return #t.

Suppose we wanted to know why 17/4 = 8 (mod 15), but 51/12 (mod 15) is undefined, even though normally 51/12 = 17/4. In code,

> (with-modulus 15 (mod/ 17 4))
8
> (/ 51 12)
17/4
> (with-modulus 15 (mod/ 51 12))
Error: (modular-inverse) bad argument type - not coprime to modulus 15: 12

We could try to divide by brute force: find, modulo 15, all the numbers a for which (mod* a 4) is 17, then find all the numbers b for which (mod* a 12) is 51.

(import srfi-42)
> (with-modulus 15
    (list-ec (:range a 15)
             (if (mod= (mod* a 4) 17))
      a))
(8)
> (with-modulus 15
    (list-ec (:range a 15)
             (if (mod= (mod* a 12) 51))
      a))
(3 8 13)

So the problem isn't that b doesn't exist, it's that b isn't unique.

Primes
[procedure] (prime? z) -> boolean
z
integer

Returns #t if z is a prime, #f otherwise.

Formally, an integer z is prime when the only positive divisors of z are 1 and (abs z).

The positive primes below 20 are:

> (filter prime? (iota 20 1))
(2 3 5 7 11 13 17 19)

The corresponding negative primes are:

> (filter prime? (iota 20 0 -1))
(-2 -3 -5 -7 -11 -13 -17 -19)

Wikipedia: Prime Number

[procedure] (odd-prime? z) -> boolean
z
integer

Returns #t if z is a odd prime, #f otherwise.

> (odd-prime? 2)
#f
> (odd-prime? 3)
#t
[procedure] (nth-prime n) -> integer
n
integer

Returns the nth positive prime; n must be nonnegative.

> (nth-prime 0)
2
> (nth-prime 1)
3
> (nth-prime 2)
5
[procedure] (random-prime n) -> integer
n
integer

Returns a random prime smaller than n, which must be greater than 2.

The function random-prime picks random numbers below n until a prime is found.

> (random-prime 10)
3
> (random-prime 10)
2
> (random-prime 10)
5
[procedure] (next-prime z) -> integer
z
integer

Returns the first prime larger than z.

> (next-prime 4)
5
> (next-prime 5)
7
[procedure] (prev-prime z) -> integer

Returns the first prime smaller than z.

> (prev-prime 4)
3
> (prev-prime 5)
3
[procedure] (next-primes z n) -> (list-of integer)
z
integer
n
integer

Returns list of the next n primes larger than z; n must be nonnegative.

> (next-primes 2 4)
(3 5 7 11)
[procedure] (prev-primes z n) -> (list-of integer)
z
integer
n
integer

Returns list of the next n primes smaller than z; n must be nonnegative.

> (prev-primes 13 4)
(11 7 5 3)
[procedure] (factorize n) -> (list-of (list integer integer))
n
integer

Returns the factorization of a natural number n. The factorization consists of a list of corresponding primes and exponents. The primes will be in ascending order.

The prime factorization of 600 = 2^3 * 3^1 * 5^2:

> (factorize 600)
((2 3) (3 1) (5 2))
[procedure] (defactorize f) -> integer
f
(list-of (list integer integer))

Returns the natural number, whose factorization is given by f. The factorization f is represented as described in factorize.

> (defactorize '((2 3) (3 1) (5 2)))
600

Wikipedia: Integer Factorization

[procedure] (divisors z) -> (list-of integer)
z
integer

Returns a list of all positive divisors of the integer z. The divisors appear in ascending order.

> (divisors 120)
(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
> (divisors -120)
(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
[procedure] (prime-divisors z) -> (list-of integer)
z
integer

Returns a list of all positive prime divisors of the integer z. The divisors appear in ascending order.

> (prime-divisors 120)
'(2 3 5)
[procedure] (prime-exponents z) -> (list-of integer)
z
integer

Returns a list of the exponents of in a factorization of the integer z.

> (define z (* 2 2 2 3 5 5))
> (prime-divisors z)
(2 3 5)
> (prime-exponents z)
(3 1 2)
Roots
[procedure] (integer-root n m) -> integer
n
integer
m
integer

Returns the mth integer root of n. This is the largest integer r such that (expt r m) <= n.

> (integer-root (expt 3 4) 4)
3
> (integer-root (+ (expt 3 4) 1) 4)
3
[procedure] (integer-root/remainder n m) -> integer integer
n
integer
m
integer

Returns two values. The first, r, is the mth integer root of n. The second is n-r^m.

> (integer-root/remainder (expt 3 4) 4)
3
0
> (integer-root/remainder (+ (expt 3 4) 1) 4)
3
1
Powers
[procedure] (max-dividing-power a b) -> integer
a
integer
b
integre

Returns the largest exponent, n, of a power with base a that divides b.

That is, (expt a n) divides b but (expt a (+ n 1)) does not divide b.

> (max-dividing-power 3 (expt 3 4))
4
> (max-dividing-power 3 5)
0
[procedure] (perfect-power m) -> (or (list integer integer) #f)
m
integer

If m is a perfect power, a list with two elements b and n such that (expt b n) = m is returned, otherwise #f is returned.

> (perfect-power (expt 3 4))
(3 4)
> (perfect-power (+ (expt 3 4) 1))
#f
[procedure] (perfect-power? m) -> boolean
m
integer

Returns #t if m is a perfect power, otherwise #f.

> (perfect-power? (expt 3 4))
#t
> (perfect-power? (+ (expt 3 4) 1))
#f

Wikipedia: Perfect Power

[procedure] (prime-power m) -> (or (list integer integer) #f)
m
integer

If M is a power of the form (expt p n) where p is prime, then a list with the prime and the exponent is returned, otherwise #f is returned.

> (prime-power (expt 3 4))
(3 4)
> (prime-power (expt 6 4))
#f
[procedure] (prime-power? m) -> boolean
m
integer

Returns #t if m is a prime power, otherwise #f.

> (prime-power? (expt 3 4))
#t
> (prime-power? (expt 6 4))
#f
> (prime-power? 1)
#f
> (prime-power? 0)
#f
[procedure] (odd-prime-power? m) -> boolean
m
integer

Returns #t if m is a power of an odd prime, otherwise #f.

> (odd-prime-power? (expt 2 4))
#f
> (odd-prime-power? (expt 3 4))
#t
> (odd-prime-power? (expt 15 4))
#f
[procedure] (as-power m) -> integer integer
m
integer

Returns two values b and n such that m = (expt b n) and n is maximal.

> (as-power (* (expt 2 4) (expt 3 4)))
6
4
> (expt 6 4)
1296
> (* (expt 2 4) (expt 3 4))
1296
> (as-power (* (expt 2 4) (expt 3 5)))
3888
1
[procedure] (prefect-square m) -> (or integer #f)

Returns (sqrt m) if m is perfect square, otherwise #f.

> (perfect-square 9)
3
> (perfect-square 10)
#f
Multiplicative and Arithmetic Functions

The functions in this section are multiplicative (with exception of the Von Mangoldt function). In number theory, a multiplicative function is a function f such that (f (* a b)) = (* (f a) (f b)) for all coprime natural numbers a and b.

[procedure] (totient n) -> integer
n
integer

Returns the number of integers from 1 to n that are coprime with n.

This function is known as Euler's totient or phi function.

> (totient 9)
6
> (length (filter (curry coprime? 9) (range 10)))
6

Wikipedia: Euler's Totient

[procedure] (moebius-mu n) -> integer
n
integer

Returns:

> (moebius-mu (* 2 3 5))
-1
> (moebius-mu (* 2 3 5 7))
1
> (moebius-mu (* 2 2 3 5 7))
0

Wikipedia: Moebius Function

[procedure] (divisor-sum n k) -> integer
n
integer
k
integer

Returns sum of the kth powers of all divisors of n.

> (divisor-sum 12 2)
210
> (apply + (map sqr (divisors 12)))
210

Wikipedia: Divisor Function

[procedure] (prime-omega n) -> integer
n
integer

Counting multiplicities the number of prime factors of n is returned.

> (prime-omega (* 2 2 2 3 3 5))
6

OEIS: Big Omega, Big Omega

[procedure] (mangoldt-lambda n) -> number
n
integer

The von Mangoldt function. If n=p^k for a prime p and an integer k>=1 then (log n) is returned. Otherwise 0 is returned.

Note: The Von Mangoldt function is not multiplicative.

> (mangoldt-lambda (* 3 3))
1.0986122886681098
> (log 3)
1.0986122886681098

Wikipedia: Von Mangoldt Function

Number Sequences
[procedure] (bernoulli-number n) -> ratnum
n
integer

Returns the nth Bernoulli number; n must be nonnegative.

> (map bernoulli-number (iota 9))
(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30)

Note that these are the first Bernoulli numbers, since (bernoulli-number 1) = -1/2.

Wikipedia: Bernoulli Number

[procedure] (eulerian-number n k) -> integer
n
integer
k
integer

Returns the Eulerian number <n,k>; both arguments must be nonnegative.

> (eulerian-number 5 2)
66

Wikipedia: Eulerian Number

[procedure] (fibonacci n) -> integer
n
integer

Returns the nth Fibonacci number; n must be nonnegative.

The ten first Fibonacci numbers:

> (map fibonacci (iota 10))
'(0 1 1 2 3 5 8 13 21 34)

Wikipedia: Fibonacci Number

[procedure] (make-fibonaci a b) -> (integer -> integer)
a
integer
b
integer

Returns a function representing a Fibonacci sequence with the first two numbers a and b. The fibonacci function is defined as (make-fibonacci 0 1).

The Lucas numbers are defined as a Fibonacci sequence starting with 2 and 1:

> (map (make-fibonacci 2 1) (iota 10))
(2 1 3 4 7 11 18 29 47 76)

Wikipedia: Lucas Number

[procedure] (modular-fibonacci n m) -> integer
n
integer
m
integer

Returns the nth Fibonacci number modulo m; n must be nonnegative and m must be positive.

The ten first Fibonacci numbers modulo 5:

> (map (lambda (n) (modular-fibonacci n 5)) (range 10))
(0 1 1 2 3 0 3 3 1 4)
[procedure] (make-modular-fibonacci a b) -> (integer integer -> integer)
a
integer
b
integer

Like make-fibonacci, but makes a modular fibonacci sequence.

[procedure] (farey-sequence n) -> (list-of ratnum)
n
integer

Returns a list of the numbers in the nth Farey sequence; n must be positive.

The nth Farey sequence is the sequence of all completely reduced rational numbers from 0 to 1 which denominators are less than or equal to n.

> (farey-sequence 1)
(0 1)
> (farey-sequence 2)
(0 1/2 1)
> (farey-sequence 3)
(0 1/3 1/2 2/3 1)

Wikipedia: Farey Sequence

[procedure] (tangent-number n) -> integer
n
integer

Returns the nth tangent number; n must be nonnegative.

> (tangent-number 1)
1
> (tangent-number 2)
0
> (tangent-number 3)
2

MathWorld: Tangent Number

Combinatorics
[procedure] (factorial n) -> integer
n
integer

Returns the factorial of n, which must be nonnegative. The factorial of n is the number (* n (- n 1) (- n 2) ... 1).

> (factorial 3)
6
> (factorial 0)
1

Wikipedia: Factorial

[procedure] (binomial n k) -> integer
n
integer
k
integer

Returns the number of ways to choose a set of k items from a set of n items; i.e. the order of the k items is not significant. Both arguments must be nonnegative.

When k > n, (binomial n k) = 0. Otherwise, (binomial n k) is equivalent to (/ (factorial n) (factorial k) (factorial (- n k))), but computed more quickly.

> (binomial 5 3)
10

Wikipedia: Binomial Coefficient

[procedure] (permutations n k) -> integer
n
integer
k
integer

Returns the number of ways to choose a sequence of k items from a set of n items; i.e. the order of the k items is significant. Both arguments must be nonnegative.

When k > n, (permutations n k) = 0. Otherwise, (permutations n k) is equivalent to (/ (factorial n) (factorial (- n k))).

> (permutations 5 3)
60

Wikipedia: Permutations

[procedure] (multinomial n ks) -> integer
n
integer
ks
(list-of integer)

A generalization of binomial to multiple sets of choices; e.g. (multinomial n (list k0 k1 k2)) is the number of ways to choose a set of k0 items, a set of k1 items, and a set of k2 items from a set of n items. All arguments must be nonnegative.

When (apply + ks) = n, this is equivalent to (apply / (factorial n) (map factorial ks)). Otherwise, multinomial returns 0.

> (multinomial 5 '(3 2))
10
> (= (multinomial 8 '(5 3))
     (binomial 8 5)
     (binomial 8 3))
#t
> (multinomial 10 '(5 3 2))
2520
> (multinomial 0 '())
1
> (multinomial 4 '(1 1))
0

Wikipedia: Multinomial Coefficient

[procedure] (partitions n) -> integer
n
integer

Returns the number of partitions of n, which must be nonnegative. A partition of a positive integer n is a way of writing n as a sum of positive integers. The number 3 has the partitions (+ 1 1 1), (+ 1 2) and (+ 3).

> (partitions 3)
3
> (partitions 4)
5

Wikipedia: Partition

Polygonal numbers
[procedure] (triangle-number? n) -> boolean
[procedure] (square-number? n) -> boolean
[procedure] (pentagonal-number? n) -> boolean
[procedure] (hexagonal-number? n) -> boolean
[procedure] (heptagonal-number? n) -> boolean
[procedure] (octagonal-number? n) -> boolean
n
integer

These functions check whether the input is a polygonal number of the types triangle, square, pentagonal, hexagonal, heptagonal and octogonal respectively.

Wikipedia: Polygonal Number

[procedure] (triangle-number n) -> boolean
[procedure] (sqr n) -> boolean
[procedure] (pentagonal-number n) -> boolean
[procedure] (hexagonal-number n) -> boolean
[procedure] (heptagonal-number n) -> boolean
[procedure] (octagonal-number n) -> boolean
n
integer

These functions return the nth polygonal number of the corresponding type of polygonal number.

Fractions
[procedure] (mediant x y) -> ratnum
x
ratnum
y
ratnum

Computes the mediant of the numbers x and y. The mediant of two fractions p/q and r/s in their lowest term is the number (p+r)/(q+s).

> (mediant 1/2 5/6)
3/4

Wikipedia: Mediant

The Quadratic Equation
[procedure] (quadratic-solutions a b c) -> (list-of number) 
 a : number
 b : number
 c : number

Returns a list of all real solutions to the equation a x^2 + bx + c = 0 with real coefficients.

> (quadratic-solutions 1 0 -1)
'(-1 1)
> (quadratic-solutions 1 2 1)
'(-1)
> (quadratic-solutions 1 0 1)
'()
[procedure] (quadratic-integer-solutions a b c) -> (list-of integer)
a
number
b
number
c
number

Returns a list of all integer solutions to the equation a x^2 + bx + c = 0 with real coefficients.

> (quadratic-integer-solutions 1 0 -1)
'(-1 1)
> (quadratic-integer-solutions 1 0 -2)
'()
[procedure] (quadratic-natural-solutions a b c) -> (list-of integer)
a
number
b
number
c
number

Returns a list of all natural solutions to the equation a x^2 + bx + c = 0 with real coefficients.

> (quadratic-natural-solutions 1 0 -1)
'(1)
> (quadratic-natural-solutions 1 0 -2)
'()
[procedure] (complex-quadratic-solutions a b c) -> (list-of number)
a
number
b
number
c
number

Returns a list of all complex solutions to the equation a x^2 + bx + c = 0. This function allows complex coeffecients.

> (complex-quadratic-solutions 1 0 1)
(0-1i 0+1i)
> (complex-quadratic-solutions 1 0 (sqrt -1))
(-0.7071067811865476+0.7071067811865475i 0.7071067811865476-0.7071067811865475i)
> (complex-quadratic-solutions 1 0 1)
(0-1i 0+1i)
The group Zn and Primitive Roots

The numbers 0, 1, ..., n-1 with addition and multiplication modulo n is a ring called Zn.

The group of units in Zn with respect to multiplication modulo n is called Un.

The order of an element x in Un is the least k>0 such that x^k=1 mod n.

A generator the group Un is called a primitive root modulo n. Note that g is a primitive root if and only if order(g)=totient(n). A group with a generator is called cyclic.

Wikipedia: The Group Zn

[procedure] (unit-group n) -> (list-of integer)
n
integer

Returns a list of all elements of Un, the unit group modulo n. The modulus n must be positive.

> (unit-group 5)
(1 2 3 4)
> (unit-group 6)
(1 5)
[procedure] (unit-group-order x n) -> integer
x
integer
n
integer

Returns the order of x in the group Un; both arguments must be positive. If x and n are not coprime, (unit-group-order x n) raises an error.

> (unit-group-order 2 5)
4
> (unit-group-order 2 6)
Error: (unit-group-order) expected coprime arguments; given 2 and 6
[procedure] (unit-group-orders n) -> (list-of positive-integer)
n
integer

Returns a list (list (unit-group-order x0 n) (unit-group-order x1 n) ...) where x0, x1, ... are the elements of Un. The modulus n must be positive.

> (unit-group-orders 5)
(1 4 4 2)
> (map (cut unit-group-order <> 5) (unit-group 5))
(1 4 4 2)
[procedure] (primitive-root? x n) -> boolean
x
integer
n
integer

Returns #t if the element x in Un is a primitive root modulo n, otherwise #f is returned. An error is signaled if x is not a member of Un. Both arguments must be positive.

> (primitive-root? 1 5)
#f
> (primitive-root? 2 5)
#t
> (primitive-root? 5 5)
Error: (primitive-root?) expected coprime arguments; given 5 and 5
[procedure] (exists-primitive-root? n) -> boolean
n
integer

Returns #t if the group Un has a primitive root (i.e. it is cyclic), otherwise #f is returned. In other words, #t is returned if n is one of 1, 2, 4, p^e, 2*p^e where p is an odd prime, and #f otherwise. The modulus n must be positive.

> (exists-primitive-root? 5)
#t
> (exists-primitive-root? 6)
#t
> (exists-primitive-root? 12)
#f
[procedure] (primitive-root n) -> (or integer false)

Returns a primitive root of Un if one exists, otherwise #f is returned. The modulus n must be positive.

> (primitive-root 5)
2
> (primitive-root 6)
5
[procedure] (primitive-roots n) -> (list-of integer)
n
integer

Returns a list of all primitive roots of {Un}. The modulus n must be positive.

> (primitive-roots 3)
(2)
> (primitive-roots 5)
(2 3)
> (primitive-roots 6)
(5)

Original documentation

https://docs.racket-lang.org/math/

Development status

This egg is still largely under active development, with the exception of the math.number-theory module, which is finished and ready for use.

Implementation caveats

Author

Neil Toronto and Jens Axel Søgaard for Racket

Maintainer

Diego A. Mundo

Repository

https://github.com/dieggsy/chicken-math

License

GPL-3.0

Version History