# 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 $$, 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 a fraction $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 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

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

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

Since $$, we are done. Thus, we see that the factorial 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 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:

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

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

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

$=$ | $\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 representation of $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 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)

(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},\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\xf7n$” denote the integer part of $m/n$ and let
“$m\mathrm{\%}n$ denote the remainder of dividing $m$ by $n$. For
instance, $13\xf75=2$ and $13\mathrm{\%}5=3$. With these notational
conventions, we may re-express our program as follows:

$$n!:=\{\begin{array}{cc}1\hfill & n=0\hfill \\ n\cdot (n-1)!\hfill & \text{otherwise}\hfill \end{array}$$ |

$$\stackrel{~}{d}(n,m):=\{\begin{array}{cc}m\hfill & m!\mathrm{\%}n=0\hfill \\ \stackrel{~}{d}(n,m+1)\hfill & \text{otherwise}\hfill \end{array}$$ |

$$d(n):=\stackrel{~}{d}(n,1)$$ |

$$s(p,q):=\{\begin{array}{cc}()\hfill & q=1\hfill \\ s(p\xf7q,q-1)\ast (p\mathrm{\%}q)\hfill & \mathrm{otherwise}\hfill \end{array}$$ |

$$r(p,q):=s(p\cdot f(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 |