4
$\begingroup$

My friend thought of a system in which each number $n$ (I will first restrict my question to positive integers $n$) is represented by a digit string $(d_l,...,d_1)$ as follows $\forall n \in \mathbb{N}, \exists l \in \mathbb{N}: n = (d_l, d_{l-1}, ..., d_2, d_1) = \sum_{i=1}^l (d_i*(i!))$ where $\forall i \in \mathbb{N}, d_i \in \mathbb{N}: d_i \leq i$ and specifically $\forall i>l, d_i = 0$ ; note that each integer $d_i$ would be represented in decimal with at least 1 digit (in general, these factorial digits can be quite long in decimal representation)- but this is not an issue at the moment [because his system uses a finite alphabet via balanced quinary for each $d_i$].

[In this post, any number shown is in decimal.]

For example, $$1729=2*6! + 2*5! + 2*4! + 1=(2,2,2,0,0,1)$$ and $$1729^3 = (10*12!+9*11!+5*10!+3*9!+6*8!) + 1729 = (10, 9, 5, 3, 6, 0,2,2,2,0,0,1)$$.

My question is: how would this digit string $(d_l,...,d_1)$ be computed most efficiently for general positive integer n? I have mostly just been trying to guess at the largest $l \in \mathbb{N}: l*(l!) \leq n, (l+1)! > n$ and then (once I have found it), I just go through digit-by-digit, working my way down in values of candidate $d_i$ (mostly by squeeze theorem with the goal of finding out that $d_i + 1$ is too large first and then next testing $d_i$ and finding that it works). This process can be quite arduous. What would you recommend doing, algorithmically and efficiently? Bragging rights for Mathematica code that automates the process.

(Using Stirling's formula might be helpful, but it still requires a lot of playing around.)

What modifications would need to be made for general real numbers (including nonintegers)? After the radix point, it works similarly, but with $(i!)^{-1}$ (where, I think, $d_i<i \forall i \in \mathbb{N}$ and where the first such base is $\frac{1}{2!}$).

More generally and philosophically, are there any spiritual problems with this representation? It is meant to be rather compact and alien. What are some cool properties that it exhibits?

$\endgroup$
  • $\begingroup$ Not sure that you proposal for the fractional part is the right one. If you consider the natural extension of the factorial to negative numbers (Gamma function), the weights should be infinite :( Or maybe all numbers should be normalized to be fractional only, like in floating-points ? $\endgroup$ – Yves Daoust Jul 16 '14 at 9:29
  • $\begingroup$ Yeah, I think that is one of the reasons why the reciprocal is taken. Other bases work by taking reciprocals; this one just happens to vary the base rather than the exponent. I did realize that it seemed strange though... $\endgroup$ – kevin Jul 16 '14 at 9:29
  • $\begingroup$ The reciprocal works well in a constant base because $b^{-k}=\frac1{b^k}$. You don't have $(-n)!=\frac1{n!}$. $\endgroup$ – Yves Daoust Jul 16 '14 at 9:31
  • $\begingroup$ This factorial base representation does not look so attractive to implement multiplication, as you don't have the property $m!n!=(m+n)!$ that holds in a fixed base ($b^mb^n=b^{m+n}$). $\endgroup$ – Yves Daoust Jul 16 '14 at 13:38
  • $\begingroup$ Another issue is that you need an alphabet of infinite size to write down an arbitrarily large number, or use an alternate numeration to represent the digits. $\endgroup$ – Yves Daoust Jul 16 '14 at 13:42
7
$\begingroup$

Use the standard base conversion algorithm, using the fact that the digit weights are not powers of a base but factorials:

$$d_1=n \text{ mod }2, n_1= n \text{ div } 2,$$ $$d_2=n_1 \text{ mod }3, n_2= n_1 \text{ div } 3,$$ $$d_3=n_2 \text{ mod }4, n_3= n_2 \text{ div } 4$$ $$...$$

This is just an inversion of the "Horner" form $n = d_1 + 2(d_2+3(d_3+4(d_4...+ld_l)))$. In the standard case, the increasing integers would be replaced by the base.

w= 2
while N != 0:
    print N % w,
    N/= w
    w+= 1
$\endgroup$
  • $\begingroup$ Can't be more explicit, this is the algorithm. $\endgroup$ – Yves Daoust Jul 16 '14 at 9:21
  • $\begingroup$ While it is hard to be more explicit in your statement of the algorithm, a proof of it would be nice (I have proven it myself--I am just suggesting an improvement for your answer) $\endgroup$ – user714630 Jul 16 '14 at 10:07
  • $\begingroup$ @Karl Post your answer then. $\endgroup$ – Yves Daoust Jul 16 '14 at 10:25
  • $\begingroup$ very cool idea. It needed two times reading for me to understand that and why this is so easy. Wow. $\endgroup$ – Gottfried Helms Jul 16 '14 at 13:40
  • $\begingroup$ @kevin: $div$ denotes integer division and /= division-assignment (this is a Python program). $\endgroup$ – Yves Daoust Jul 16 '14 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.