expressing fractions in factorial base


Given a fraction p/q, 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 p and q have no common factor. As in the parent (http://planetmath.org/FactorialBaseRepresentationOfFractions) entry, we assume the both p and q are positive and that p<q, so our fraction is less than 1.

To begin, determine the smallest integer d(q) such that q divides (http://planetmath.org/Divisibility) d(q)!.

Rewrite the fraction with d(q)! as denominator:

pq=pd(q)!/qd(q)!

Successively split off terms as follows: given a fraction m/n!, write  m=kn+r  where r<n and then write

mn!:=k(n-1)!+rn!

Initially, we choose m=pd(q)!/q and n=d(q). At each successive repetition of the procedure, set m to be the value of k from the previous step and decrease n by 1.

Let us illustrate this with an example. We will rewrite 7/8 in factorial base. Looking at factorials, we see that 8 does not divide either 2! or 3!, but it does divide 4!, so we have d(8)=4.

Next we rewrite the fraction with 4! as denominator. Since 4!=24 and 24/8=3, we should multiply both numerator and denominator of our fraction by 3 to obtain 7/8=21/24=21/4!.

Now, we split off terms. We have 21=54+1, so

214!=53!+14!.

Next, 5=13+2, so

53! = 12!+23!
214! = 12!+23!+14!.

Since 1<2, we are done. Thus, we see that the factorial base representation of 7/8 is 0 . 1 2 1 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 m/n! is the factorial base representation of k/(n-1)! followed by r, where  m=kn+r  as above. For example, let us compute the factorial base representation of 7/9 using this trick. Looking at factorials, we see that d(9)=6. We express our fraction with a denominator of 6!=720:

79=807809=560720=5606!

We now split of digits like follows:

5606! = 935! 2
= 184! 3 2
= 43! 2 3 2
= 12! 1 2 3 2

Hence, we see that the factorial base representation of 7/9 is 0 . 1 1 2 3 2.

The following LISP program computes factorial base representations of rational numbersPlanetmathPlanetmathPlanetmath 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)

(t (append

(s (/ p q) (- q 1))

(list (% p q))))))

(defun r (p q)   (s

(* p (/ (f (d q)) q))

(d 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 translationMathworldPlanetmathPlanetmath 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 n-tuplet (x1,x2,,xn) and an m-tuplet (y1,y2,,ym), we set (x1,x2,,xn)(y1,y2,,ym) to be the m+n-tuplet (x1,x2,,xn,y1,y2,ym). Let “m÷n” denote the integer part of m/n and let “m%n denote the remainder of dividing m by n. For instance, 13÷5=2 and 13%5=3. With these notational conventions, we may re-express our program as follows:

n!:={1n=0n(n-1)!otherwise
d~(n,m):={mm!%n=0d~(n,m+1)otherwise
d(n):=d~(n,1)
s(p,q):={()q=1s(p÷q,q-1)(p%q)otherwise
r(p,q):=s(pf(d(q))/q,d(q)
Title expressing fractions in factorial base
Canonical name ExpressingFractionsInFactorialBase
Date of creation 2013-03-22 16:46:04
Last modified on 2013-03-22 16:46:04
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 13
Author rspuzio (6075)
Entry type Algorithm
Classification msc 11A63