expressing fractions in factorial base
Given a fraction , one may re-express it in factorial base as follows. For simplicity, we assume that the fraction is already written in lowest terms, i.e. that and have no common factor. As in the parent (http://planetmath.org/FactorialBaseRepresentationOfFractions) entry, we assume the both and are positive and that , so our fraction is less than 1.
Rewrite the fraction with as denominator:
Successively split off terms as follows: given a fraction , write where and then write
Initially, we choose and . At each successive repetition of the procedure, set to be the value of from the previous step and decrease by 1.
Let us illustrate this with an example. We will rewrite in factorial base. Looking at factorials, we see that does not divide either or , but it does divide , so we have .
Next we rewrite the fraction with as denominator. Since and , we should multiply both numerator and denominator of our fraction by to obtain .
Now, we split off terms. We have , so
Next, , so
Since , we are done. Thus, we see that the factorial base representation of is as in the table in the parent entry.
We can make the calculation more concise by noting that the splitting off of terms can also be described as follows: the factorial base representation of is the factorial base representation of followed by , where as above. For example, let us compute the factorial base representation of using this trick. Looking at factorials, we see that . We express our fraction with a denominator of :
We now split of digits like follows:
Hence, we see that the factorial base representation of is .
The following LISP program computes factorial base representations of rational numbers using this method. It was used to compute the table of factorial base representations in the parent entry.
(defun factorial) (n)
(cond ((= n 0) 1)
(t (* n (factorial (- n 1))))))
(defun d-tilde (n m)
(cond ((= (% (factorial m) n) 0) m)
(t (d-tilde n (+ m 1)))))
(defun d (n) (d-tilde n 1))
(defun s (p q)
(cond ((= q 1) nil)
(s (/ p q) (- q 1))
(list (% p q))))))
(defun r (p q) (s
(* p (/ (f (d q)) q))
Since LISP can look rather confusing to someone who is not familiar with its notational conventions — all functions are written as prefixes and parentheses are used a bit differently than usually, a translation into more typical mathematical notation may be helpful. To do this, let us define a few symbols. Let ‘’ denote the concatenaton of tuplets — given an -tuplet and an -tuplet , we set to be the -tuplet . Let “” denote the integer part of and let “ denote the remainder of dividing by . For instance, and . With these notational conventions, we may re-express our program as follows:
|Title||expressing fractions in factorial base|
|Date of creation||2013-03-22 16:46:04|
|Last modified on||2013-03-22 16:46:04|
|Last modified by||rspuzio (6075)|