3
$\begingroup$

Imagine a number base where instead of writing the number of products for each power of your base (e.g. in decimal, $152 = 1 \times 10^2 + 5 \times 10^1 + 2 \times 10^0$), you had one where you write the exponents for the prime factorization for that number (in little endian). So $2$ would be $1$ (because it's the first prime), $5$ would be $100$ (because its the third prime), $15$ would be $110$ because its $3 \times 5$, and so on. Somewhat bizarrely, $1$ would be $0$ because it can be written as $2^0$ but there is no way to write zero.

Since every number (except $0$) can be uniquely factorized, then we can write any positive integer in this notation. If we include $-1$ as one of the primes, we can include negative numbers. If we allow the exponents to be negative, then we can write any rational number, $\frac{p}{q} = p(q^{-1})$. If we allow the exponents to be fractions, then we can write any surd, as well as complex numbers (having included $-1$, we can take its square root).

What I'm wondering is whether there is anything cool or surprising about writing numbers in this way. I've tried thinking of some interesting features and here's a list of pros and cons so far:

Cons:

  • No way to represent zero.
  • Can't do addition (probably for same reason as above because $1$ is the identity so it's a multiplicative group)
  • Inefficient to take a number from decimal to this base (because factoring is hard)
  • There's probably no sensible way to count. The additive order (1,2,3,4,5,6,7,8) gives a sequence 0,1,10,2,100,11,3 for which I'm struggling to find a pattern (it's tempting to translate into binary or something except the exponents grow arbitrarily large). Finding a natural way to multiplicatively order them is weird too. You start at $0$, then $1$, then you have two choices: $2$ or $10$. At each point, you have to decide whether to increment an exponent or include a new prime. This means you've got two decisions to make at each new point, each of which continues infinitely. Way out of my depth but perhaps this gives some intuition for the uncountability of irrationals?

Pros:

  • Multiplication is much easier (just addition of exponents)
  • Exponentiation is much easier (multiplication of exponents)
  • Easy to convert back to an additive number base (just iteratively multiply your primes)
  • It grows very fast: $111 = 30, 1111 = 210, 11111 = 2310$ (and that's with limiting exponents to at most $1$). I feel like this might be a pro because it gives a compact way of writing some very large numbers (in particular, n-smooth numbers from cryptography) and because it would quickly overwhelm someone who was reading these numbers in decimal. Perhaps there are some cryptographic applications here? Also, maybe some cool stuff happens when we reduce these numbers $\pmod y$, where $y$ is something fancy?

So anyways, thanks for reading this far. I'm putting this on here because I'm curious to hear what more knowledgeable people think about writing numbers in this way. Has this been done before? Are there any surprising patterns here? Is this just an inconvenient way of writing numbers which we already know plenty about or might it offer a different perspective? Are there any applications which could benefit from greatly speeding up multiplication at the expense of forgoing addition?

My final pitch: imagine a bunch of aliens landed on Earth. Wouldn't it be easier to describe this system to them (since primes are presumably universally studied) than decimal numbers which are based off the number of fingers we happen to have on our hands? So isn't this a more natural number base? Let me know!

$\endgroup$
3
  • 1
    $\begingroup$ Another con: the set of required digits is infinite, making it nontrivial to distinguish (say) $2^{10}$ from $3$. $\endgroup$ May 10, 2021 at 17:33
  • $\begingroup$ @GregMartin good point - I guess you could just use commas, or maybe we need to invent another number base for the exponents! $\endgroup$
    – johnbot
    May 10, 2021 at 18:28
  • $\begingroup$ It's got some cool properties, but alas, I've never been able to find any truly useful applications for it. See also primorial numeral system on OEIS and mixed radix systems on Wikipedia. $\endgroup$
    – Trevor
    Jun 12 at 19:26

1 Answer 1

1
$\begingroup$

Saw this recently and was curious about how these numbers grow, even with exponents reduced $\pmod{2}$.

Turns out plotting the sequence $\Pi_2 = \{1, 2, 3, 6, 5, 10, ...\}$ against the binary index $n_2 = \{0, 1, 10, 11, 100, 101, ...\}$ shows that although it doesn't grow monotonically, it has quite a simple self-similar structure. See enter image description here

When plotting up to larger values larger values and with different bases different bases, the pattern becomes clearer: in base $d$, we have $d$ peaks, each recursively made of up $d$ peaks.

Unfortunately, the explanation for this self-similarity is not particularly surprising. Imagine inducting on the exponents base $2$. Then if the first $n$ strings are $x_1, x_2, ..., x_n$, the next $n$ strings will simply be $x_1, x_2, ..., x_n$. This will look identical to the plot of the first $n$ numbers, except shifted up by some constant prime.

So in base $d$ we get $d$ peaks because we have $0x_1, 0x_2, ... 0x_n$, then $1x_1, 1x_2, ..., 1x_n$, all the way up to $(d-1)x_1, (d-1)x_2, ..., (d-1)x_n$. Once again, each level is just shifted up by $p, p^2, ..., p^{d-1}$ for some prime $p$. So the self-similarity of the graphs just reflect the self-similarity of counting.

Presumably there could be a more formal description of what's going on here. For anyone interested, a useful starting point might be that reducing the exponents mod $d$ (call it $\Pi_d$) gives a subgroup of $(\mathbb{Z}, \times)$. Moreover, $\Pi_{d_1}$ is a subgroup of $\Pi_{d_2}$, if $d_1 \leq d_2$.

$\endgroup$
3
  • 1
    $\begingroup$ Not really sure why you bothered with these graphs when all they demonstrate is the recursiveness of additive numbers. Bit counter-productive don't you think? The subgroup stuff seems more interesting though. I don't know much about them but I often hear people talk about normal subgroups - have we got any of those? $\endgroup$
    – johnbot
    Jan 28 at 4:19
  • $\begingroup$ @johnbot Not really sure why you'd dismiss the first response you get on here, but OK. In answer to your question - all subgroups are trivially normal here because multiplication is commutative. $\endgroup$ Feb 18 at 20:29
  • 2
    $\begingroup$ Also it won't let me add a comment above for some reason but @Greg Martin's point about how to write the exponents is a good one. As with Godel numbering (which these are a pale imitation of), it makes sense to write the exponents recursively, using the same system. For example, you could write 4 = 2^2 = [2] = [[1]] or 9 = 3^2 = [0, 2] = [0, [1]]. Setting 1 = [0, 0, .... ] =: [], you can write any number using just '[', ']', '0'. This makes multiplication much more difficult, but exponentiation very easy, for example 5^x = [0, 0, x]. $\endgroup$ Feb 18 at 20:35

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.