Go forward to Probability Distribution Functions. Go backward to Random Numbers. Go up to Scientific Functions.

Combinatorial Functions
=======================

Commands relating to combinatorics and number theory begin with the
`k' key prefix.

The `k g' (`calc-gcd') [`gcd'] command computes the Greatest Common
Divisor of two integers.  It also accepts fractions; the GCD of two
fractions is defined by taking the GCD of the numerators, and the LCM
of the denominators.  This definition is consistent with the idea that
`a / gcd(a,x)' should yield an integer for any `a' and `x'.  For other
types of arguments, the operation is left in symbolic form.

The `k l' (`calc-lcm') [`lcm'] command computes the Least Common
Multiple of two integers or fractions.  The product of the LCM and GCD
of two numbers is equal to the product of the numbers.

The `k E' (`calc-extended-gcd') [`egcd'] command computes the GCD of
two integers `x' and `y' and returns a vector `[g, a, b]' where `g =
gcd(x,y) = a x + b y'.

The `!' (`calc-factorial') [`fact'] command computes the factorial of
the number at the top of the stack.  If the number is an integer, the
result is an exact integer.  If the number is an integer-valued float,
the result is a floating-point approximation.  If the number is a
non-integral real number, the generalized factorial is used, as
defined by the Euler Gamma function.  Please note that computation of
large factorials can be slow; using floating-point format will help
since fewer digits must be maintained.  The same is true of many of
the commands in this section.

The `k d' (`calc-double-factorial') [`dfact'] command computes the
"double factorial" of an integer.  For an even integer, this is the
product of even integers from 2 to `N'.  For an odd integer, this is
the product of odd integers from 3 to `N'.  If the argument is an
integer-valued float, the result is a floating-point approximation.
This function is undefined for negative even integers.  The notation
`N!!' is also recognized for double factorials.

The `k c' (`calc-choose') [`choose'] command computes the binomial
coefficient `N'-choose-`M', where `M' is the number on the top of the
stack and `N' is second-to-top.  If both arguments are integers, the
result is an exact integer.  Otherwise, the result is a floating-point
approximation.  The binomial coefficient is defined for all real
numbers by `N! / M! (N-M)!'.

The `H k c' (`calc-perm') [`perm'] command computes the
number-of-permutations function `N! / (N-M)!'.

The `k b' (`calc-bernoulli-number') [`bern'] command computes a given
Bernoulli number.  The value at the top of the stack is a nonnegative
integer `n' that specifies which Bernoulli number is desired.  The `H
k b' command computes a Bernoulli polynomial, taking `n' from the
second-to-top position and `x' from the top of the stack.  If `x' is a
variable or formula the result is a polynomial in `x'; if `x' is a
number the result is a number.

The `k e' (`calc-euler-number') [`euler'] command similarly
computes an Euler number, and `H k e' computes an Euler polynomial.
Bernoulli and Euler numbers occur in the Taylor expansions of several
functions.

The `k s' (`calc-stirling-number') [`stir1'] command computes a
Stirling number of the first kind, given two integers `n' and `m' on
the stack.  The `H k s' [`stir2'] command computes a Stirling number
of the second kind.  These are the number of `m'-cycle permutations of
`n' objects, and the number of ways to partition `n' objects into `m'
non-empty sets, respectively.

The `k p' (`calc-prime-test') command checks if the integer on the top
of the stack is prime.  For integers less than eight million, the
answer is always exact and reasonably fast.  For larger integers, a
probabilistic method is used (see Knuth vol. II, section 4.5.4,
algorithm P).  The number is first checked against small prime factors
(up to 13).  Then, any number of iterations of the algorithm are
performed.  Each step either discovers that the number is non-prime,
or substantially increases the certainty that the number is prime.
After a few steps, the chance that a number was mistakenly described
as prime will be less than one percent.  (Indeed, this is a worst-case
estimate of the probability; in practice even a single iteration is
quite reliable.)  After the `k p' command, the number will be reported
as definitely prime or non-prime if possible, or otherwise "probably"
prime with a certain probability of error.

The normal `k p' command performs one iteration of the primality test.
Pressing `k p' repeatedly for the same integer will perform additional
iterations.  Also, `k p' with a numeric prefix performs the specified
number of iterations.  There is also an algebraic function `prime(n)'
or `prime(n,iters)' which returns 1 if `n' is (probably) prime and 0
if not.

The `k f' (`calc-prime-factors') [`prfac'] command attempts to
decompose an integer into its prime factors.  For numbers up to 25
million, the answer is exact although it may take some time.  The
result is a vector of the prime factors in increasing order.  For
larger inputs, prime factors above 5000 may not be found, in which
case the last number in the vector will be an unfactored integer
greater than 25 million (with a warning message).  For negative
integers, the first element of the list will be -1.  For inputs -1, 0,
and 1, the result is a list of the same number.

The `k n' (`calc-next-prime') [`nextprime'] command finds the next
prime above a given number.  Essentially, it searches by calling
`calc-prime-test' on successive integers until it finds one that
passes the test.  This is quite fast for integers less than eight
million, but once the probabilistic test comes into play the search
may be rather slow.  Ordinarily this command stops for any prime that
passes one iteration of the primality test.  With a numeric prefix
argument, a number must pass the specified number of iterations before
the search stops.  (This only matters when searching above eight
million.)  You can always use additional `k p' commands to increase
your certainty that the number is indeed prime.

The `I k n' (`calc-prev-prime') [`prevprime'] command analogously
finds the next prime less than a given number.

The `k t' (`calc-totient') [`totient'] command computes the Euler
"totient" function, the number of integers less than `n' which are
relatively prime to `n'.

The `k m' (`calc-moebius') [`moebius'] command computes the Moebius
"mu" function.  If the input number is a product of `k' distinct
factors, this is `(-1)^k'.  If the input number has any duplicate
factors (i.e., can be divided by the same prime more than once), the
result is zero.