2
$\begingroup$

If $p$ is a positive prime number, put $p! = \textrm{lcm}(2, 3, 5, \dots, p) = p\cdots3\cdot2$. Then every non-negative integer can be written uniquely as:

$x_1 + 2\cdot x_2 + 3\cdot 2 x_3 + \dots + p! \cdot x_p$, where each $x_p$ is indexed over the primes $p$ such that $p! \leq x$ and $0\leq x_i \lt \sigma(i)!, \ \forall i$ where $\sigma(i)$ is the next prime after $i$.

Divide up the numbers into divisions of $2$ integers, then divisions of $2\cdot 3$ integers, and so on, $x_p$ addresses what $p!$ block to be on and within that block, $x_{p-1}$ addresses what sub-$x_{p-1}$ block to be in and so on... to add up to the number $x$.

It is unique since each $x$ is in one and only one box on each level.

$\endgroup$
  • $\begingroup$ It's a particular kind of mixed radix number representation. $\endgroup$ – hardmath Feb 23 '15 at 21:54
3
$\begingroup$

As @hardmath commented, this is a mixed radix representation. In particular, your numbers $p!$ are called primorials (they are often notated $p_i\#$), and the system is called a primorial number system.

$\endgroup$
3
$\begingroup$

If you had taken the $\operatorname{lcm}$ operation more seriously, and used $\operatorname{lcm}(1..n)=\operatorname{lcm}(1,2,3,4, \dots, n)$ as the place values (for $\operatorname{lcm}(1..(n-1)) \neq \operatorname{lcm}(1..n)$, i.e. for prime powers $n=p^r$) in your mixed radix number representation, then you would have got the LCM numeral system.

It is closer in its properties to the factorial number system than to the primorial number system. It seems to feel like a slightly optimized version of the factorial number system (and fixes the drawbacks of the primorial number system compared to the factorial number system):

This may be the "smallest" product-based numbering system that has a unique finite representation for every rational number. In this base 1/2 = .1 (1*1/2), 1/3 = .02 (0*1/2 + 2*1/6), 1/5 = .0102 (0*1/2 + 1*1/6 + 0*1/12 + 2*1/60). — Russell Easterly, Oct 03 2001

However, the factorial number system might still have slightly better properties. For example, if an arbitrarily huge number is divided by a fixed number $k$ (assumed to be small), then the factorial number system only needs to know the lowest $i+2k$ digits of the huge input number for being able to write out the lowest $i$ digits of the result. The LCM number system also only need to look ahead a finite number of digits for writing out the lowest $i$ digits of the result. The exact look ahead is harder to determine, it should be more or less the lowest $i+ik$ lowest digits of the huge input number.

However, the LCM number system also has advantages over the factorial number system. Just like the primorial number system, it allows a simple and relatively fast multiplication algorithm. The numbers can be quickly converted into an optimal chinese remainder representation and back:

$x_2 + 2 x_3 + 6 x_4 + 12 x_5 + 60 x_7 + \dots + \operatorname{lcm}(1..(p^r-1)) x_{p^r} \ = \ x \ $ with $\ 0\leq x_{p_i^{r_i}} < p_i$.

$x_2 = x \mod 2$
$x_2 + 2 x_3 = x \mod 3$
$x_2 + 2 x_3 + 2 x_4 = x \mod 4$
$x_2 + 2 x_3 + x_4 + 2 x_5 = x \mod 5$
$x_2 + 2 x_3 + 6 x_4 + 5 x_5 + 4 x_7 = x \mod 7$
$\dots$
$x_2 + 2 x_3 + 6 x_4 + \dots + \operatorname{lcm}(1..(p_i^{r_i}-1)) x_{p_i^{r_i}} = x \mod p_i^{r_i}$

So to multiply $x$ and $y$, one determines an upper bound for the number of places of $z = x\cdot y$, then computes value of $x$ and $y$ modulo all those places, multiplies them separately for each place (modulo $p_i^{r_i}$), and then converts the result back to the LCM representation. The conversion back is easy, since one can first determine $z_2$, then $z_3$ by subtracting $z_2$ from the known value $z \mod 3$ before converting it to $z_3$, then $z_4$ by subtracting $z_2+2z_3$ from the known value $z \mod 4$ before converting it to $z_4$, and so on.

This chinese remainder representation is optimal in the sense that the individual moduli are as small as possible for being able to represent a number of a given magnitude. The LCM number system may be even more optimal than the primorial number system in this respect. (It should be possible to do the computations modulo $p_i^{r_i}$ only for the biggest $r_i$, due to the structure of the LCM number system.)

$\endgroup$

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.