4 Number Theory
(require math/number-theory) | package: math-lib |
4.1 Congruences and Modular Arithmetic
Wikipedia: Divisor
Formally, an integer m divides an integer n when there exists a unique integer k such that (* m k) = n.
Practically, if (divides? m n) is #t, then (/ n m) will return an integer and will not raise exn:fail:contract:divide-by-zero.
Wikipedia: Bezout’s Identity
Wikipedia: Coprime
> (coprime? 2 6 15) #t
Wikipedia: Pairwise Coprime
procedure
(pairwise-coprime? a b ...) → Boolean
a : Integer b : Integer
> (pairwise-coprime? 2 6 15) #f
Wikipedia: Chinese Remainder Theorem
x = a1 (mod n1) ... x = ak (mod nk)
The solution x is less than (* n1 ... nk).
The moduli ns must all be positive.
> (solve-chinese '(2 3 2) '(3 5 7)) 23
Wikipedia: Quadratic Residue
procedure
(quadratic-residue? a n) → Boolean
a : Integer n : Integer
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.
> (quadratic-residue? 0 4) #f
> (quadratic-residue? 1 4) #t
> (quadratic-residue? 2 4) #f
> (quadratic-residue? 3 4) #f
Wikipedia: Legendre Symbol
procedure
(quadratic-character a p) → (U -1 0 1)
a : Integer p : Integer
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: Jacobi Symbol
procedure
(jacobi-symbol a n) → (U -1 0 1)
a : Nonnegative-Integer n : Positive-Integer
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) jacobi: contract violation
expected: odd?
given: 8
argument position: 2nd
other arguments...:
32
Wikipedia: Multiplicative Inverse
procedure
(modular-inverse a n) → Natural
a : Integer n : Integer
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
procedure
(modular-expt a b n) → Natural
a : Integer b : Integer n : Integer
> (modulo (expt -6 523) 19) 13
> (modular-expt -6 523 19) 13
> (modular-expt 9 158235208 19) 4
> (modular-expt 2 -1 11) 6
> ; don't try this at home! (modulo (expt 9 158235208) 19) 4
4.1.1 Parameterized Modular Arithmetic
Wikipedia: Modular Arithmetic
The math/number-theory library supports modular arithmetic parameterized on a current modulus. For example, the code
(with-modulus n ((modexpt a b) . mod= . c))
corresponds with the mathematical statement ab = 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.)
syntax
(with-modulus n body ...)
n : 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) 1
> (with-modulus 5 (current-modulus)) 5
procedure
x : Exact-Rational
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.
> (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)) modular-inverse: expected argument that is coprime to
modulus 7; given 7
Note that (mod/ a b ...) is not equivalent to (modulo (/ a b ...) (current-modulus)); see mod= for a demonstration.
procedure
a : Integer b : Integer
procedure
a : Integer b : Integer
procedure
a : Integer b : Integer
procedure
a : Integer b : Integer
procedure
a : Integer b : Integer
> (with-modulus 15 (mod/ 17 4)) 8
> (/ 51 12) 17/4
> (with-modulus 15 (mod/ 51 12)) modular-inverse: expected argument that is coprime to
modulus 15; given 12
> (with-modulus 15 (for/list ([a (in-range 15)] #:when (mod= (mod* a 4) 17)) a)) '(8)
> (with-modulus 15 (for/list ([b (in-range 15)] #:when (mod= (mod* b 12) 51)) b)) '(3 8 13)
4.2 Primes
Wikipedia: Prime Number
Formally, an integer z is prime when the only positive divisors of z are 1 and (abs z).
procedure
(odd-prime? z) → Boolean
z : Integer
> (odd-prime? 2) #f
> (odd-prime? 3) #t
procedure
(random-prime n) → Natural
n : Integer
The function random-prime picks random numbers below n until a prime is found.
> (random-prime 10) 2
> (random-prime 10) 5
> (random-prime 10) 3
procedure
(next-prime z) → Integer
z : Integer
> (next-prime 4) 5
> (next-prime 5) 7
procedure
(prev-prime z) → Integer
z : Integer
> (prev-prime 4) 3
> (prev-prime 5) 3
procedure
(next-primes z n) → (Listof Integer)
z : Integer n : Integer
> (next-primes 2 4) '(3 5 7 11)
procedure
(prev-primes z n) → (Listof Integer)
z : Integer n : Integer
> (prev-primes 13 4) '(11 7 5 3)
Wikipedia: Integer Factorization
> (factorize 600) '((2 3) (3 1) (5 2))
> (defactorize '((2 3) (3 1) (5 2))) 600
> (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) → (Listof Natural)
z : Natural
> (prime-divisors 120) '(2 3 5)
procedure
(prime-exponents z) → (Listof Natural)
z : Natural
> (define z (* 2 2 2 3 5 5)) > (prime-divisors z) '(2 3 5)
> (prime-exponents z) '(3 1 2)
4.3 Roots
procedure
(integer-root n m) → Natural
n : Natural m : Natural
> (integer-root (expt 3 4) 4) 3
> (integer-root (+ (expt 3 4) 1) 4) 3
procedure
(integer-root/remainder n m) →
Natural Natural n : Natural m : Natural
> (integer-root/remainder (expt 3 4) 4)
3
0
> (integer-root/remainder (+ (expt 3 4) 1) 4)
3
1
4.4 Powers
procedure
(max-dividing-power a b) → Natural
a : Integer b : Integer
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
> (perfect-power (expt 3 4)) '(3 4)
> (perfect-power (+ (expt 3 4) 1)) #f
Wikipedia: Perfect Power
procedure
(perfect-power? m) → Boolean
m : Integer
> (perfect-power? (expt 3 4)) #t
> (perfect-power? (+ (expt 3 4) 1)) #f
> (prime-power (expt 3 4)) '(3 4)
> (prime-power (expt 6 4)) #f
procedure
(prime-power? m) → Boolean
m : Natural
> (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 : Natural
> (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) →
Natural Natural m : Positive-Integer
> (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
(perfect-square m) → (U Natural #f)
m : Natural
> (perfect-square 9) 3
> (perfect-square 10) #f
4.5 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.
Wikipedia: Euler’s Totient
This function is known as Eulers totient or phi function.
> (totient 9) 6
> (length (filter (curry coprime? 9) (range 10))) 6
Wikipedia: Moebius Function
procedure
(moebius-mu n) → (U -1 0 1)
n : Natural
1 if n is a square-free product of an even number of primes
-1 if n is a square-free product of an odd number of primes
0 if n has a multiple prime factor
> (moebius-mu (* 2 3 5)) -1
> (moebius-mu (* 2 3 5 7)) 1
> (moebius-mu (* 2 2 3 5 7)) 0
Wikipedia: Divisor Function
procedure
(divisor-sum n k) → Natural
n : Natural k : Natural
> (divisor-sum 12 2) 210
> (apply + (map sqr (divisors 12))) 210
OEIS: Big Omega
OEIS: Big Omega
procedure
(prime-omega n) → natural?
n : Natural
> (prime-omega (* 2 2 2 3 3 5)) 6
Wikipedia: Von Mangoldt Function
procedure
(mangoldt-lambda n) → Real
n : Natural
Note: The Von Mangoldt function is not multiplicative.
> (mangoldt-lambda (* 3 3)) 1.0986122886681098
> (log 3) 1.0986122886681098
4.6 Number Sequences
Wikipedia: Bernoulli Number
procedure
n : Integer
> (map bernoulli-number (range 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.
MathWorld: Eulerian Number
procedure
(eulerian-number n k) → Natural
n : Integer k : Integer
> (eulerian-number 5 2) 66
Wikipedia: Fibonacci Number
procedure
(make-fibonacci a b) → (Integer -> Integer)
a : Integer b : Integer
Wikipedia: Lucas Number
> (map (make-fibonacci 2 1) (range 10)) '(2 1 3 4 7 11 18 29 47 76)
procedure
(modular-fibonacci n m) → Natural
n : Integer m : Integer
> (map (λ (n) (modular-fibonacci n 5)) (range 10)) '(0 1 1 2 3 0 3 3 1 4)
Wikipedia: Farey Sequence
procedure
(farey-sequence n) → (Listof Exact-Rational)
n : Integer
> (farey-sequence 1) '(0 1)
> (farey-sequence 2) '(0 1/2 1)
> (farey-sequence 3) '(0 1/3 1/2 2/3 1)
MathWorld: Tangent Number
procedure
(tangent-number n) → Integer
n : Integer
> (tangent-number 1) 1
> (tangent-number 2) 0
> (tangent-number 3) 2
4.7 Combinatorics
Wikipedia: Factorial
Wikipedia: Binomial Coefficient
> (binomial 5 3) 10
Wikipedia: Permutations
procedure
(permutations n k) → Natural
n : Integer k : Integer
> (permutations 5 3) 60
Wikipedia: Multinomial Coeffecient
procedure
(multinomial n ks) → Natural
n : Integer ks : (Listof Integer)
> (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: Partition
procedure
(partitions n) → Natural
n : Integer
> (partitions 3) 3
> (partitions 4) 5
4.8 Special Numbers
4.8.1 Polygonal Numbers
Wikipedia: Polygonal Number
procedure
(triangle-number? n) → Boolean
n : Natural
procedure
(square-number? n) → Boolean
n : Natural
procedure
(pentagonal-number? n) → Boolean
n : Natural
procedure
(hexagonal-number? n) → Boolean
n : Natural
procedure
(heptagonal-number? n) → Boolean
n : Natural
procedure
(octagonal-number? n) → Boolean
n : Natural
procedure
(triangle-number n) → Natural
n : Natural
procedure
n : Natural
procedure
(pentagonal-number n) → Natural
n : Natural
procedure
(hexagonal-number n) → Natural
n : Natural
procedure
(heptagonal-number n) → Natural
n : Natural
procedure
(octagonal-number n) → Natural
n : Natural
Wikipedia: Mediant
4.9 Fractions
procedure
(mediant x y) → Exact-Rational
x : Exact-Rational y : Exact-Rational
> (mediant 1/2 5/6) 3/4
4.10 The Quadratic Equation
procedure
(quadratic-solutions a b c) → (Listof Real)
a : Real b : Real c : Real
> (quadratic-solutions 1 0 -1) '(-1 1)
> (quadratic-solutions 1 2 1) '(-1)
> (quadratic-solutions 1 0 1) '()
> (quadratic-solutions 1e+200 2e+200 1e+200) '(-1.0)
> (quadratic-solutions 1e-200 -2e-200 1e-200) '(1.0)
> (quadratic-solutions -1 2/3 1/3) '(1 -1/3)
procedure
(quadratic-integer-solutions a b c) → (Listof Integer)
a : Real b : Real c : Real
> (quadratic-integer-solutions 1 0 -1) '(-1 1)
> (quadratic-integer-solutions 1 0 -2) '()
procedure
(quadratic-natural-solutions a b c) → (Listof Natural)
a : Real b : Real c : Real
> (quadratic-natural-solutions 1 0 -1) '(1)
> (quadratic-natural-solutions 1 0 -2) '()
procedure
(complex-quadratic-solutions a b c) → (Listof Complex)
a : Complex b : Complex c : Complex
> (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)
Added in version 1.1 of package math-lib.
4.11 The group Zn and Primitive Roots
Wikipedia: The Group 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.
procedure
(unit-group n) → (Listof Positive-Integer)
n : Integer
> (unit-group 5) '(1 2 3 4)
> (unit-group 6) '(1 5)
procedure
(unit-group-order x n) → Positive-Integer
x : Integer n : Integer
> (unit-group-order 2 5) 4
> (unit-group-order 2 6) unit-group-order: expected coprime arguments; given 2 and 6
procedure
(unit-group-orders n) → (Listof Positive-Integer)
n : Integer
> (unit-group-orders 5) '(1 4 4 2)
> (map (curryr unit-group-order 5) (unit-group 5)) '(1 4 4 2)
procedure
(primitive-root? x n) → Boolean
x : Integer n : Integer
> (primitive-root? 1 5) #f
> (primitive-root? 2 5) #t
> (primitive-root? 5 5) primitive-root?: expected coprime arguments; given 5 and 5
procedure
n : Integer
> (exists-primitive-root? 5) #t
> (exists-primitive-root? 6) #t
> (exists-primitive-root? 12) #f
procedure
(primitive-root n) → (Union Natural #f)
n : Integer
> (primitive-root 5) 2
> (primitive-root 6) 5
procedure
(primitive-roots n) → (Listof Natural)
n : Integer
> (primitive-roots 3) '(2)
> (primitive-roots 5) '(2 3)
> (primitive-roots 6) '(5)