calc: Combinatorial Functions
9.6 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 Möbius μ
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.
Info Catalog
calc: Random Numbers
calc: Scientific Functions
calc: Probability Distribution Functions