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

${\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 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:

${\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 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÷n$” denote the integer part of $m/n$ and let “$m\mathrm{\%}n$ denote the remainder of dividing $m$ by $n$. For instance, $13÷5=2$ and $13\mathrm{\%}5=3$. With these notational conventions, 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)$$

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