expressing fractions in factorial base

Given a fraction $p/q$, one may re-express it in factorialbase as follows. For simplicity, we assume that thefraction 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 andthat , 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:

$$\frac{p}{q}=\frac{p\cdot d(q)!/q}{d(q)!}$$

Successively split off terms as follows: given afraction $m/n!$, write  $m=k\cdot n+r$  where and then write

$$\frac{m}{n!}:=\frac{k}{(n-1)!}+\frac{r}{n!}$$

Initially, we choose $m=p\cdot d(q)!/q$ and$n=d(q)$. At each successive repetition of theprocedure, set $m$ to be the value of $k$ fromthe previous step and decrease $n$ by 1.

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

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

Now, we split off terms. We have $21=5\cdot 4+1$, so

$$\frac{21}{4!}=\frac{5}{3!}+\frac{1}{4!}.$$

Next, $5=1\cdot 3+2$, so

${\displaystyle \frac{5}{3!}}$$=$${\displaystyle \frac{1}{2!}}+{\displaystyle \frac{2}{3!}}$

${\displaystyle \frac{21}{4!}}$$=$${\displaystyle \frac{1}{2!}}+{\displaystyle \frac{2}{3!}}+{\displaystyle \frac{1}{4!}}.$

Since , we are done. Thus, we see that thefactorial base representation of $7/8$ is$\mathrm{0\hspace{0.17em}.\hspace{0.17em}1\hspace{0.17em}2\hspace{0.17em}1}$ as in the table in theparent entry.

We can make the calculation more concise by notingthat the splitting off of terms can also be describedas follows: the factorial base representation of$m/n!$ is the factorial base representation of$k/(n-1)!$ followed by $r$, where  $m=k\cdot n+r$  as above. For example, let us compute thefactorial base representation of $7/9$ using thistrick. Looking at factorials, we see that $d(9)=6$.We express our fraction with a denominator of $6!=720$:

$$\frac{7}{9}=\frac{80\cdot 7}{80\cdot 9}=\frac{560}{720}=\frac{560}{6!}$$

We now split of digits like follows:

${\displaystyle \frac{560}{6!}}$$=$${\displaystyle \frac{93}{5!}}\mathrm{\hspace{0.17em}2}$

$=$${\displaystyle \frac{18}{4!}}\mathrm{\hspace{0.17em}3\hspace{0.17em}2}$

$=$${\displaystyle \frac{4}{3!}}\mathrm{\hspace{0.17em}2\hspace{0.17em}3\hspace{0.17em}2}$

$=$${\displaystyle \frac{1}{2!}}\mathrm{\hspace{0.17em}1\hspace{0.17em}2\hspace{0.17em}3\hspace{0.17em}2}$

Hence, we see that the factorial base representationof $7/9$ is $\mathrm{0\hspace{0.17em}.\hspace{0.17em}1\hspace{0.17em}1\hspace{0.17em}2\hspace{0.17em}3\hspace{0.17em}2}$.

The following LISP program computes factorial baserepresentations of rational numbers using this method.It was used to compute the table of factorial baserepresentations 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 familiarwith its notational conventions — all functions are written asprefixes 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 ‘$\ast$’ denote theconcatenaton of tuplets — given an $n$-tuplet $(x1,x_2,\mathrm{\dots },x_n)$and an $m$-tuplet $(y_1,y_2,\mathrm{\dots },y_m)$, we set$(x1,x_2,\mathrm{\dots },x_n)\ast (y_1,y_2,\mathrm{\dots },y_m)$ to be the$m+n$-tuplet $(x1,x_2,\mathrm{\dots },x_n,y_1,y_2,\mathrm{\dots }{y}_m)$.Let “$m÷n$” denote the integer part of $m/n$ and let“$m\mathrm{\%}n$ denote the remainder of dividing $m$ by $n$. Forinstance, $13÷5=2$ and $13\mathrm{\%}5=3$. With these notationalconventions, we may re-express our program as follows:

$$d(n):=\tilde{d}(n,1)$$

$$r(p,q):=s(p\cdot f(d(q))/q,d(q)$$