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.