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$
7
  • $\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$
    – user65203
    Jul 16, 2014 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, 2014 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$
    – user65203
    Jul 16, 2014 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$
    – user65203
    Jul 16, 2014 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$
    – user65203
    Jul 16, 2014 at 13:42

1 Answer 1

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$
5
  • $\begingroup$ Can't be more explicit, this is the algorithm. $\endgroup$
    – user65203
    Jul 16, 2014 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$ Jul 16, 2014 at 10:07
  • $\begingroup$ @Karl Post your answer then. $\endgroup$
    – user65203
    Jul 16, 2014 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$ Jul 16, 2014 at 13:40
  • $\begingroup$ @kevin: $div$ denotes integer division and /= division-assignment (this is a Python program). $\endgroup$
    – user65203
    Jul 16, 2014 at 19:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .