# 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, 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:

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

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

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

Initially, we choose $m=p\cdot d(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=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=$ $\displaystyle\frac{1}{2!}+\frac{2}{3!}$ $\displaystyle\frac{21}{4!}$ $\displaystyle=$ $\displaystyle\frac{1}{2!}+\frac{2}{3!}+\frac{1}{4!}.$

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=k\cdot n+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$:

 $\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=$ $\displaystyle\frac{93}{5!}\,2$ $\displaystyle=$ $\displaystyle\frac{18}{4!}\,3\,2$ $\displaystyle=$ $\displaystyle\frac{4}{3!}\,2\,3\,2$ $\displaystyle=$ $\displaystyle\frac{1}{2!}\,1\,2\,3\,2$

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

(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 translation   into more typical mathematical notation may be helpful. To do this, let us define a few symbols. Let ‘$\ast$’ denote the concatenaton of tuplets — given an $n$-tuplet $(x1,x_{2},\ldots,x_{n})$ and an $m$-tuplet $(y_{1},y_{2},\ldots,y_{m})$, we set $(x1,x_{2},\ldots,x_{n})\ast(y_{1},y_{2},\ldots,y_{m})$ to be the $m+n$-tuplet $(x1,x_{2},\ldots,x_{n},y_{1},y_{2},\ldots y_{m})$. Let “$m\div n$” denote the integer part of $m/n$ and let “$m\operatorname{\%}n$ denote the remainder of dividing $m$ by $n$. For instance, $13\div 5=2$ and $13\operatorname{\%}5=3$. With these notational conventions, we may re-express our program as follows:

 $n!:=\begin{cases}1&n=0\\ n\cdot(n-1)!&\textrm{otherwise}\end{cases}$
 ${\tilde{d}}(n,m):=\begin{cases}m&m!\operatorname{\%}n=0\\ {\tilde{d}}(n,m+1)&\textrm{otherwise}\end{cases}$
 $d(n):={\tilde{d}}(n,1)$
 $s(p,q):=\begin{cases}()&q=1\\ s(p\div q,q-1)\ast(p\operatorname{\%}q)&\mathrm{otherwise}\end{cases}$
 $r(p,q):=s(p\cdot f(d(q))/q,d(q)$
Title expressing fractions in factorial base ExpressingFractionsInFactorialBase 2013-03-22 16:46:04 2013-03-22 16:46:04 rspuzio (6075) rspuzio (6075) 13 rspuzio (6075) Algorithm msc 11A63