63.7 Number Theoretic Functions

If GMP is available, some number theoretic functions are in effect. Most of which accept, unlike in number theory, all kinds of numbers. In that case coercion to the target range (mostly integer) takes place.

Function: primep number &optional certainty-threshold

Return nil if number is known to be composite, return t if number is definitely prime and return 'probably-prime if number seems to be prime but it is not certain.

If optional argument certainty-threshold is non-nil, it should be a natural number to indicate how many probabilistic primality tests must be passed in order to have certainty about the primality of number. The default is 8.

Function: next-prime number

Return the next prime number greater than number.

Function: gcd &rest numbers

Return the greatest common divisor of the arguments.

Function: xgcd &rest numbers

Function: lcm &rest numbers

Return the least common multiple of the arguments.

Function: factorial number

Return the factorial of number.

Function: binomial-coefficient n k

Return the binomial coefficient, n over k.

Function: fibonacci number

Return the numberth Fibonacci number. To compute both, the numberth and (number-1)th Fibonacci number use fibonacci2 instead.

Function: fibonacci2 number

Return a cons with the numberth and (number-1)th Fibonacci number. To compute a series of Fibonacci numbers starting at index number, use this function and recursively compute the rest.

Function: lucas number

Return the numberth Lucas number. To compute both, the numberth and (number-1)th Lucas number use lucas2 instead.

Function: lucas2 number

Return a cons with the numberth and (number-1)th Lucas number. To compute a series of Lucas numbers starting at index number, use this function and recursively compute the rest.

Function: divisiblep number d

Return t if number is divisible by d, nil otherwise.

Function: congruentp number c m

Return t if number is congruent to c modulo m, nil otherwise.

Function: perfect-power-p number

Return t if number is a perfect power, nil otherwise. An integer number is said to be a perfect power if there exist integers, a and b, such that ‘a^b = number’.

Function: perfect-square-p number

Return t if number is a perfect square, nil otherwise. An integer number is said to be a perfect square if there exists an integer b such that ‘b^2 = number’.

Function: integral-sqrt number

Return a cons with the integral square root of number in the car and the remainder in the cdr. An integral square root is a number b and a remainder c such that ‘b*b + c = number’.

Function: canonical-norm number

Return the canonical norm of number.

Function: conjugate number

Return the (canonical) conjugate of number. If number is a comparable, just return number.

Function: zero-divisor-p number

Return t if number is a zero-divisor, nil otherwise. number is said to be a zero-divisor, if there exists another non-zero number b, such that ‘number * b = 0’

Function: unitp number

Return t if number is a unit, nil otherwise. number is said to be a unit, if there exists another number b (the inverse of number), such that ‘number * b = 1’