8.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 absolute value of 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.