## An interesting numeral system

**Moderators:** gmalivuk, Moderators General, Prelates

### An interesting numeral system

The other day I discovered a neat notation for uniquely representing numbers (I'm not sure what numbers... at least all rational numbers). I have searched, but have not come across such a notation--if something at least similar exists, please point it out.

Its basis is the fundamental theorem of arithmetic, which states that every integer greater than one is a unique product of primes.

In other words, every integer greater than one can be written as[math]2^{n_1} \times 3^{n_2} \times 5^{n_3} \times 7^{n_4} \times \dots[/math]where [imath]n_1[/imath], [imath]n_2[/imath], [imath]n_3[/imath], ... are non-negative integers. We can write this shortly as[math]{n_1}\:{n_2}\:{n_3}\:{n_4} \dots[/math]For instance, we write the number 1400 as 3021, because [imath]1400 = 2^3 \times 3^0 \times 5^2 \times 7^1[/imath].

This has some problems. First, we have no way of expressing zero or one. To accomplish this, we simply prepend our numbers with the number one (3021 -> 13021) and write zero and one as 0 and 1, respectively. Remember that the first "digit" is merely a "flag". 13021 does NOT mean [imath]1^1 \times 2^3 \times 3^0 \times 5^2 \times 7^1[/imath]. Also note that if 0 is the first digit, it must be the only digit; strings such as 011 have no meaning (at this point).

Second, this notation breaks down when you consider numbers such as [imath]3072 = 2^{10} \times 3[/imath]. We cannot simply write 1101, as this is exactly how we write [imath]10 = 2 \times 5[/imath]. We can borrow symbols from other alphabets to represent the numbers eleven and above, but we ultimately must use brackets: 1[10]1 clearly is not the same as 1101.

However, there is an even better solution--we simply write the individual digits in this form as well (surrounded by brackets, if necessary). So the number 1400, previously written as 13021, we can now write as 1[101]0[11]1, since 3 is written as 101, and two is written as 11. We repeat this process until all digits are either 0 or 1.

So every natural number can be represented by a unique tree of ones and zeroes.

Here are some common integer sequences written in this notation. Notice how recursively and simply they are expressed.

The natural numbers:

0 = 0

1 = 1

2 = 11

3 = 101

4 = 1[11]

5 = 1001

6 = 111

7 = 10001

8 = 1[101]

9 = 10[11]

10 = 1101

...

The powers of two:

1, 11, 1[101], 1[1[11]], 1[1001], 1[111], 1[10001], ...

The primes:

11, 101, 1001, 10001, 100001, 1000001, ...

The perfect squares:

1, 1[11], 10[11], 1[1[11]], 100[11], 1[11][11], 1000[11], 1[1[1[11]]], ...

Now, let's add one rule: by substituting the first digit '1' with '-1' (remember that the first digit is just a flag), we negate the number. This allows us to write negative numbers:

-1, -11, -101, -1[11], -1001, -111, -10001, -1[1[11]], ...

Fractions:

1/2 = 1[-1]

1/3 = 10[-1]

1/4 = 1[-11]

...

2/3 = 11[-1]

3/2 = 1[-1]1

2/5 = 110[-1]

3/5 = 101[-1]

5/2 = 1[-1]01

...

Fractional powers:

[imath]\sqrt 2[/imath] = 1[1[-1]]

[imath]\sqrt 3[/imath] = 10[1[-1]]

[imath]\sqrt 5[/imath] = 100[1[-1]]

...

[imath]2^{\frac{1}{3}}[/imath] = 1[10[-1]]

[imath]3^{\frac{5}{2}}[/imath] = 10[1[-1]01]

...

This process can be continued forever. For example, [imath]2^{\sqrt 2}[/imath] is written as 1[1[1[-1]]], [imath]2^{2^{\sqrt 2}}[/imath] is 1[1[1[1[-1]]]], etc.

I'm currently working on algorithms for addition, multiplication (which depends on addition, as [imath]a^b \times a^c = a^{b+c}[/imath]), and other operations on these numbers. I also wish to know what numbers can be represented in this form; I know that all rational numbers can.. I'm not sure about all reals, or even all algebraic numbers.

Anyway, I am grateful for any feedback.

EDIT: I forgot this.

Some small numbers have extremely long, tedious representations, such as the eleventh prime:

100000000001

One could easily write "1 (ten 0s) 1"; however, I came up with the following shorthand:

1[0101]1

Recall that 1101 means the number ten. So, in other words, when a number begins with 0, it simply means "this many zeroes". Whenever we see repeated zeroes, we can apply this rule. So we can replace n zeroes with the following strings :

2: 00 -> [01]

3: 000 -> [001] -> [[01]1]

4: 0000 -> [0[11]]

5: 00000 -> [0001] -> [[[01]1]1]

6: 000000 -> [011]

...

The natural numbers, with repeated zeroes taken out according to this rule:

1, 11, 101, 1[11], 1[01]1, 111, 1[[01]1]1, 1[101], 10[11], 1101, 1[[[01]1]1]1, ...

EDIT: fixed some very careless mistakes.

Its basis is the fundamental theorem of arithmetic, which states that every integer greater than one is a unique product of primes.

In other words, every integer greater than one can be written as[math]2^{n_1} \times 3^{n_2} \times 5^{n_3} \times 7^{n_4} \times \dots[/math]where [imath]n_1[/imath], [imath]n_2[/imath], [imath]n_3[/imath], ... are non-negative integers. We can write this shortly as[math]{n_1}\:{n_2}\:{n_3}\:{n_4} \dots[/math]For instance, we write the number 1400 as 3021, because [imath]1400 = 2^3 \times 3^0 \times 5^2 \times 7^1[/imath].

This has some problems. First, we have no way of expressing zero or one. To accomplish this, we simply prepend our numbers with the number one (3021 -> 13021) and write zero and one as 0 and 1, respectively. Remember that the first "digit" is merely a "flag". 13021 does NOT mean [imath]1^1 \times 2^3 \times 3^0 \times 5^2 \times 7^1[/imath]. Also note that if 0 is the first digit, it must be the only digit; strings such as 011 have no meaning (at this point).

Second, this notation breaks down when you consider numbers such as [imath]3072 = 2^{10} \times 3[/imath]. We cannot simply write 1101, as this is exactly how we write [imath]10 = 2 \times 5[/imath]. We can borrow symbols from other alphabets to represent the numbers eleven and above, but we ultimately must use brackets: 1[10]1 clearly is not the same as 1101.

However, there is an even better solution--we simply write the individual digits in this form as well (surrounded by brackets, if necessary). So the number 1400, previously written as 13021, we can now write as 1[101]0[11]1, since 3 is written as 101, and two is written as 11. We repeat this process until all digits are either 0 or 1.

So every natural number can be represented by a unique tree of ones and zeroes.

Here are some common integer sequences written in this notation. Notice how recursively and simply they are expressed.

The natural numbers:

0 = 0

1 = 1

2 = 11

3 = 101

4 = 1[11]

5 = 1001

6 = 111

7 = 10001

8 = 1[101]

9 = 10[11]

10 = 1101

...

The powers of two:

1, 11, 1[101], 1[1[11]], 1[1001], 1[111], 1[10001], ...

The primes:

11, 101, 1001, 10001, 100001, 1000001, ...

The perfect squares:

1, 1[11], 10[11], 1[1[11]], 100[11], 1[11][11], 1000[11], 1[1[1[11]]], ...

Now, let's add one rule: by substituting the first digit '1' with '-1' (remember that the first digit is just a flag), we negate the number. This allows us to write negative numbers:

-1, -11, -101, -1[11], -1001, -111, -10001, -1[1[11]], ...

Fractions:

1/2 = 1[-1]

1/3 = 10[-1]

1/4 = 1[-11]

...

2/3 = 11[-1]

3/2 = 1[-1]1

2/5 = 110[-1]

3/5 = 101[-1]

5/2 = 1[-1]01

...

Fractional powers:

[imath]\sqrt 2[/imath] = 1[1[-1]]

[imath]\sqrt 3[/imath] = 10[1[-1]]

[imath]\sqrt 5[/imath] = 100[1[-1]]

...

[imath]2^{\frac{1}{3}}[/imath] = 1[10[-1]]

[imath]3^{\frac{5}{2}}[/imath] = 10[1[-1]01]

...

This process can be continued forever. For example, [imath]2^{\sqrt 2}[/imath] is written as 1[1[1[-1]]], [imath]2^{2^{\sqrt 2}}[/imath] is 1[1[1[1[-1]]]], etc.

I'm currently working on algorithms for addition, multiplication (which depends on addition, as [imath]a^b \times a^c = a^{b+c}[/imath]), and other operations on these numbers. I also wish to know what numbers can be represented in this form; I know that all rational numbers can.. I'm not sure about all reals, or even all algebraic numbers.

Anyway, I am grateful for any feedback.

EDIT: I forgot this.

Some small numbers have extremely long, tedious representations, such as the eleventh prime:

100000000001

One could easily write "1 (ten 0s) 1"; however, I came up with the following shorthand:

1[0101]1

Recall that 1101 means the number ten. So, in other words, when a number begins with 0, it simply means "this many zeroes". Whenever we see repeated zeroes, we can apply this rule. So we can replace n zeroes with the following strings :

2: 00 -> [01]

3: 000 -> [001] -> [[01]1]

4: 0000 -> [0[11]]

5: 00000 -> [0001] -> [[[01]1]1]

6: 000000 -> [011]

...

The natural numbers, with repeated zeroes taken out according to this rule:

1, 11, 101, 1[11], 1[01]1, 111, 1[[01]1]1, 1[101], 10[11], 1101, 1[[[01]1]1]1, ...

EDIT: fixed some very careless mistakes.

Last edited by afarnen on Thu Feb 18, 2010 9:40 pm UTC, edited 3 times in total.

- Xanthir
- My HERO!!!
**Posts:**5400**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: An interesting numeral system

http://en.wikipedia.org/wiki/Mixed_radi ... ased_radix

This is sometimes known as the "Primoradic" numbering system.

This is sometimes known as the "Primoradic" numbering system.

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

### Re: An interesting numeral system

Xanthir wrote:http://en.wikipedia.org/wiki/Mixed_radix#Primorial_based_radix

This is sometimes known as the "Primoradic" numbering system.

Thanks for the link.

Yes, they're similar in appearance... as they are both numeral systems, and both refer to the prime numbers, but they are fundamentally completely different.

To clarify to all:

* This is not a positional numeral system,

* This is recursively defined (and thus tree-structured),

* This uses only three symbols,

* And this has nothing to do with the primorial function.

### Re: An interesting numeral system

Yeah I came up with pretty much this at some point too, only I actually drew the trees instead of writing them out.

Multiplication is in general only as easy as addition and addition is hard because computing primes is hard.

It's a pretty neat thing to play around with, though.

Multiplication is in general only as easy as addition and addition is hard because computing primes is hard.

It's a pretty neat thing to play around with, though.

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: An interesting numeral system

Nice, I'll have to mess with this some, see if I can find some other patterns.

SexyTalon wrote:If it walks like a person, talks like a person, and tastes like a person, it's probably a person. Or I Can't Believe It's Not People, which cannibals prefer to Soylent Green nearly 5 to 1 in a blind taste test.

### Re: An interesting numeral system

I remember reading about something like this before. Conway created a programming language called FRACTRAN that stored numbers using the exponents of their prime factorisations. It could be used to create algorithms for many common things (actually most things, since it's Turing complete). You might find some of the techniques interesting http://en.wikipedia.org/wiki/FRACTRAN.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: An interesting numeral system

afarnen wrote:* This uses only three symbols,

for large values of three.

This is interesting, and not something I'd seen before.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: An interesting numeral system

The first part is essentially the reverse of Godel Numbering. He used it to encode any string of symbols from a finite alphabet into a unique natural number. You are doing the reverse, for any natural number finding a string of symbols to represent it.

### Re: An interesting numeral system

jestingrabbit wrote:afarnen wrote:* This uses only three symbols,

for large values of three.

Yeah, I guess I meant five.

### Re: An interesting numeral system

Oh, I'm fairly sure there's no way to write, for instance, sqrt(2)+sqrt(3). Which, if true, might have some effect on your thoughts about an addition algorithm.

Anyway, certainly not all reals can be written this way, as there are uncountably many of them.

Anyway, certainly not all reals can be written this way, as there are uncountably many of them.

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

- Xanthir
- My HERO!!!
**Posts:**5400**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: An interesting numeral system

afarnen wrote:* This is not a positional numeral system,

It most certainly is. The value of a digit depends entirely on its position within the number, in a well-defined manner. You then transform digit-values into a complete number in a slightly different way than normal, but that doesn't make it non-positional (to get that, you have to create something like unary or roman numerals).

* This is recursively defined (and thus tree-structured),

That's only a relatively small modification from ordinary numbering systems.

* This uses only three symbols,

Again, small modification to stock, as a result of the previous line.

* And this has nothing to do with the primorial function.

You're half right here. I was misinterpreting the definition of primoradics. In there, the nth digit's value is n$, and it then proceeds as normal for a mixed radix number. It's still related to the primorial function, though not as directly as I had thought.

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

- MartianInvader
**Posts:**807**Joined:**Sat Oct 27, 2007 5:51 pm UTC

### Re: An interesting numeral system

antonfire wrote:Anyway, certainly not all reals can be written this way, as there are uncountably many of them.

It's possible you could extend this to inifinite strings, much like you would infinite decimal expansions, except we would be dealing with infinite products instead of infinite sums. Like writing out [imath]2^{1}3^{1/2}5^{1/4}...[/imath] (I don't actually know if this product converges, but you get the idea). That could, conceivably, give you uncountably many numbers, and possibly all the reals. Unique expression probably goes out the window, though.

Edit: I'm going to go ahead and claim that the product I wrote does indeed converge. Its logarithm gives a series that is just barely bigger than exponential decreasing.

Edit #2: It probably DOES give you all the reals. For any real number r > 1, you could just take each position and make it p^(1/n), where n is chosen as small as possible so that your product-so-far isn't any bigger than r. Then the sequence of partial products is strictly increasing, bounded above by r, and I don't think it's bounded by anything less than r. Bada-bing.

Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

- Yakk
- Poster with most posts but no title.
**Posts:**11115**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: An interesting numeral system

I'd use 3 symbols: [] and .

I'd always surround digits with [].

The first positional is always [.] for a non-zero number.

Counting from 0 to 14:

[]

[.]

[.][.]

[.][][.]

[[.][.]][.]

[.][][][.]

[.][.][.]

[,][][][][.]

[[.][][.]][.]

[[.][.]][][.]

[.][][.][.]

[.][][][][][.]

[.][[.][.]][.]

[.][][][][][][.]

[.][][][.][.]

Note that + is a very awkward operation to use, and our standard definition of * relies on an easy to use + during the convolution step. Multiplying two numbers in the above notation is surprisingly difficult -- multiply 2^7 by 2^5, and you'll see that it turns into an addition problem.

Instead of importing the + and * from standard notation, what if we tried playing around with what operations would be natural in this notation, and seeing if they are interesting?

Some ideas include |, & and ^ (xor), defined recursively. But these are pretty boring, I think...

The key thing that makes + interesting (beyond it being physical) is that it actually maps 3 digits to 2 digits, not 2 digits to 1 digit. This lets it cause ripples in the output.

Hmm. That [.] for the 1s place is annoying. But we need a representation for 0, don't we?

I'd always surround digits with [].

The first positional is always [.] for a non-zero number.

Counting from 0 to 14:

[]

[.]

[.][.]

[.][][.]

[[.][.]][.]

[.][][][.]

[.][.][.]

[,][][][][.]

[[.][][.]][.]

[[.][.]][][.]

[.][][.][.]

[.][][][][][.]

[.][[.][.]][.]

[.][][][][][][.]

[.][][][.][.]

Note that + is a very awkward operation to use, and our standard definition of * relies on an easy to use + during the convolution step. Multiplying two numbers in the above notation is surprisingly difficult -- multiply 2^7 by 2^5, and you'll see that it turns into an addition problem.

Instead of importing the + and * from standard notation, what if we tried playing around with what operations would be natural in this notation, and seeing if they are interesting?

Some ideas include |, & and ^ (xor), defined recursively. But these are pretty boring, I think...

The key thing that makes + interesting (beyond it being physical) is that it actually maps 3 digits to 2 digits, not 2 digits to 1 digit. This lets it cause ripples in the output.

Hmm. That [.] for the 1s place is annoying. But we need a representation for 0, don't we?

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Re: An interesting numeral system

Yeah, I've thought about this too before. It's interesting how easy multiplication becomes, but how difficult addition becomes. The other problem is when a number has a prime exponent greater than 10. How do you write 1024 (2^10)? Is that what you're using brackets for?

I have thought about doing this for units too, though, where each place would represent an exponent of the SI base units. So like, (a, b, c, d, e, f, g) would be a m^a kg^b s^c A^d K^e mol^f cd^g

Thus a meter would be (1, 0, 0, 0, 0, 0, 0), a joule would be (2, 1, -2, 0, 0, 0, 0), a volt would be (2, 1, -3, -1, 0, 0, 0), etc.

It would be nice because you never have to add two different units, but you multiply them all the time. I would imagine software that works with this (eg MathCad) does this internally anyways.

I have thought about doing this for units too, though, where each place would represent an exponent of the SI base units. So like, (a, b, c, d, e, f, g) would be a m^a kg^b s^c A^d K^e mol^f cd^g

Thus a meter would be (1, 0, 0, 0, 0, 0, 0), a joule would be (2, 1, -2, 0, 0, 0, 0), a volt would be (2, 1, -3, -1, 0, 0, 0), etc.

It would be nice because you never have to add two different units, but you multiply them all the time. I would imagine software that works with this (eg MathCad) does this internally anyways.

lol everything matters

-Ed

-Ed

- Yakk
- Poster with most posts but no title.
**Posts:**11115**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: An interesting numeral system

duckshirt wrote:Yeah, I've thought about this too before. It's interesting how easy multiplication becomes, but how difficult addition becomes. The other problem is when a number has a prime exponent greater than 10. How do you write 1024 (2^10)? Is that what you're using brackets for?

The idea is that you write each of the components in the same system.

All of a sudden, multiplication isn't easy. Because in order to multiply, you have to add up each of the components -- and the components are written in a system in which addition is hard!

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Re: An interesting numeral system

All right, the system (as is) is written as n

_{1}n_{2}n_{3}... But this doesn't make sense. That requires an extra level of complexity for zero, but what if we wrote it BACKWARD? That is how regular base works (large in front) and would allow for some greater sense of the true size of a number.SexyTalon wrote:If it walks like a person, talks like a person, and tastes like a person, it's probably a person. Or I Can't Believe It's Not People, which cannibals prefer to Soylent Green nearly 5 to 1 in a blind taste test.

### Re: An interesting numeral system

Under the spoiler are two (rather tall) pictures of how I roll.

That's right, zero is the empty tree. What of it?

**Spoiler:**

That's right, zero is the empty tree. What of it?

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

- Yakk
- Poster with most posts but no title.
**Posts:**11115**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: An interesting numeral system

Why not call it Block +? Or just block?

Ie, you have three types of node -- +, - and 0 nodes. All can have children.

+ nodes are used to generate integers, - generates negative integers, position generates what prime you use.

0 nodes generate repeated 0s.

...

As noted, addition is expensive. Multiplication is expensive, because you need to add up the child trees.

I'm still playing with what would be a natural operation. Both & and | are interesting -- but even they are a bit annoying to calculate and/or define when you allow for 0 and - nodes.

Ie, you have three types of node -- +, - and 0 nodes. All can have children.

+ nodes are used to generate integers, - generates negative integers, position generates what prime you use.

0 nodes generate repeated 0s.

...

As noted, addition is expensive. Multiplication is expensive, because you need to add up the child trees.

I'm still playing with what would be a natural operation. Both & and | are interesting -- but even they are a bit annoying to calculate and/or define when you allow for 0 and - nodes.

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Re: An interesting numeral system

In the second notation, yes, taking it to be block plus would be perfectly consistent. I don't actually much care for the second notation, though, beyond its appeal as shorthand.

Also, I was thinking of the block as a modifier of the edge it's on rather than the node. I don't want to allow a block at the root of a tree because such trees won't, for the most part, actually represent numbers.

Plus, I like 0 being the empty tree, it's fairly natural.

Edit (Feb 17):

One possibly interesting thing to investigate would be what "proportion" of numbers have trees of a certain structure. For instance on average there are 6 squarefree numbers for every pi^2 consecutive natural numbers, so in some sense 6/pi^2 of the trees have depth 1.

Also, another operation you could play with is replacing every leaf (by which I mean a plus node with no children) of tree M with an instance of another tree N. Call it M -> N or something. Then M -> 1 = M; 1 -> N = N; 0 -> N = 0; and M -> 0 "prunes" M. Of course -> is associative. It also distributes on the right over multiplication of relatively prime numbers. That is, for fixed N, f(M) = M -> N is multiplicative, which means you can probably do some number theory with it. If M is squarefree and not 1 (i.e. if M -> 0 = 1) then M -> N is M^N, but for deeper M it is bigger.

You could, of course, also replace every node in M with an instance of N, (call that, say, M >> N) so that for instance 35 >> 6 = 2^(5

These are pretty natural operations on trees, so there is probably better notation already existing for them, not to mention that you can probably come up with natural names by thinking about some category or another, but I can't be arsed to dig it up and/or work through it right now.

Also I'm surely not the only one who's noted that this stuff looks a bit like the stuff involved in Goodstein's Theorem, but I figure it's worth noting it explicitly.

Also, I was thinking of the block as a modifier of the edge it's on rather than the node. I don't want to allow a block at the root of a tree because such trees won't, for the most part, actually represent numbers.

Plus, I like 0 being the empty tree, it's fairly natural.

Edit (Feb 17):

One possibly interesting thing to investigate would be what "proportion" of numbers have trees of a certain structure. For instance on average there are 6 squarefree numbers for every pi^2 consecutive natural numbers, so in some sense 6/pi^2 of the trees have depth 1.

Also, another operation you could play with is replacing every leaf (by which I mean a plus node with no children) of tree M with an instance of another tree N. Call it M -> N or something. Then M -> 1 = M; 1 -> N = N; 0 -> N = 0; and M -> 0 "prunes" M. Of course -> is associative. It also distributes on the right over multiplication of relatively prime numbers. That is, for fixed N, f(M) = M -> N is multiplicative, which means you can probably do some number theory with it. If M is squarefree and not 1 (i.e. if M -> 0 = 1) then M -> N is M^N, but for deeper M it is bigger.

You could, of course, also replace every node in M with an instance of N, (call that, say, M >> N) so that for instance 35 >> 6 = 2^(5

^{6}7^{6}) 3^(5^{6}7^{6}). This is also associative, also has 1 as a two-sided identity, and 0 >> N = N >> 0 = 0 (I think).These are pretty natural operations on trees, so there is probably better notation already existing for them, not to mention that you can probably come up with natural names by thinking about some category or another, but I can't be arsed to dig it up and/or work through it right now.

Also I'm surely not the only one who's noted that this stuff looks a bit like the stuff involved in Goodstein's Theorem, but I figure it's worth noting it explicitly.

### Re: An interesting numeral system

I played with a system like this last year, but I didn't do the recursive part: I just treated each number as the (multi-)set of its prime factors, with 1 as the empty set and no way to represent 0. With that representation, multiplication is trivial set union.

Addition is hard, and I couldn't even figure out any way to define an ordering for numbers represented in this way: given two sets of prime factors, how can you tell which one represents the larger number (without multiplying the factors together)? (I thought about representing numbers as the multi-set of the logarithms of their prime factors. Then relative order could be determined by adding the logarithms, but that seems like cheating.)

It is possible to enumerate all numbers by enumerating all possible sets of primes, but I don't see any way to enumerate those sets in order: that is, there is no way to count using this representation of numbers.

I would guess (but I am at the limit of my mathematical ability here) that the difficulty of adding numbers like these is equivalent to the difficulty of factoring numbers.

Anyone tried to think about modular arithmetic on these numbers? I suppose that is as difficult as addition...

Addition is hard, and I couldn't even figure out any way to define an ordering for numbers represented in this way: given two sets of prime factors, how can you tell which one represents the larger number (without multiplying the factors together)? (I thought about representing numbers as the multi-set of the logarithms of their prime factors. Then relative order could be determined by adding the logarithms, but that seems like cheating.)

It is possible to enumerate all numbers by enumerating all possible sets of primes, but I don't see any way to enumerate those sets in order: that is, there is no way to count using this representation of numbers.

I would guess (but I am at the limit of my mathematical ability here) that the difficulty of adding numbers like these is equivalent to the difficulty of factoring numbers.

Anyone tried to think about modular arithmetic on these numbers? I suppose that is as difficult as addition...

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: An interesting numeral system

antonfire wrote:Multiplication is in general only as easy as addition and addition is hard because computing primes is hard.

I think you mean because factoring into primes is hard. PRIMES is in P.

The most obvious advantage to this numeral system is that prime factorization is easy, while the most obvious disadvantage is that addition, multiplication, and comparisons are all hard. This tradeoff is likely inevitable - if you could easily add in a system where prime factorization was easy, you could easily perform prime factorization using our usual binary (or decimal, or whatever) representation of numbers. And there is no known fast algorithm for integer factorization - in fact it has been conjectured that no polynomial time algorithm exists, period.

So an efficient algorithm for addition in this system probably just doesn't exist, which is why you haven't found one. Of course you can always add two numbers by converting to binary or decimal, adding, and then factoring (and factoring the exponents, etc.) to convert back to this system. But if that's how you add, then it makes this system... not so nice.

Last edited by skeptical scientist on Sat Feb 20, 2010 7:20 am UTC, edited 1 time in total.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: An interesting numeral system

skeptical scientist wrote:I think you mean because factoring primes is hard.

I lol'd.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: An interesting numeral system

jestingrabbit wrote:skeptical scientist wrote:I think you mean because factoring primes is hard.

I lol'd.

What are you talking about?

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

### Re: An interesting numeral system

Another thing that might be worth investigating is whether it's even possible to define addition on these trees in more than one way. That is, perhaps under reasonable constraints (like commutativity, associativity, distributivity, and maybe some cancellation properties), perhaps up to the obvious "permute the primes" business there's only one way to add these trees and it corresponds to the natural numbers.

If so, that would be pretty cool.

If not, whatever other structures you can define on it might be pretty cool.

If so, that would be pretty cool.

If not, whatever other structures you can define on it might be pretty cool.

- Yakk
- Poster with most posts but no title.
**Posts:**11115**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: An interesting numeral system

There is a reasonably natural order on these recursive prime-trees -- a "lexicographic" tree ordering.

A < B if B!={} and A = {}, or if A.left < B.left, or A.left = B.left and A.right < B.right.

The order does end up ordering numbers strangely. For example, 8 < 4.

A < B if B!={} and A = {}, or if A.left < B.left, or A.left = B.left and A.right < B.right.

The order does end up ordering numbers strangely. For example, 8 < 4.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Re: An interesting numeral system

Well that particular strangeness is mainly because the primes are backwards, so the 2's place is more significant than the 3's place. You can make it a little more mundane by reversing that. It's still a bit weird in that 3 is then bigger than any power of 2 (and so 8 is bigger than, for instance, 256), but it's a bit more sensible that way.

### Re: An interesting numeral system

Here's a way to solve the problem/redundancy of every number except for zero starting with a 1.

Here f is the function that encodes a number as a string, and + is string concatenation:[math]f(n)=\begin{cases}

\textrm{"0"} & n=0\\

\textrm{"1"} & n=1\\

\textrm{"["}+f(n_{0})+f(n_{1})+f(n_{2})+\dots+\textrm{"]"} & n=2^{n_{0}}\times3^{n_{1}}\times5^{n_{2}}\times\dots\end{cases}[/math]

So the natural numbers:

0, 1, [1], [01], [[1]], [001], [11], [0001], [[01]], [0[1]], [101]

Note the number of brackets is important. Also, there's no longer the repeated zeroes shorthand.

You can replace "0" with "[]" and only use three symbols.

Here f is the function that encodes a number as a string, and + is string concatenation:[math]f(n)=\begin{cases}

\textrm{"0"} & n=0\\

\textrm{"1"} & n=1\\

\textrm{"["}+f(n_{0})+f(n_{1})+f(n_{2})+\dots+\textrm{"]"} & n=2^{n_{0}}\times3^{n_{1}}\times5^{n_{2}}\times\dots\end{cases}[/math]

So the natural numbers:

0, 1, [1], [01], [[1]], [001], [11], [0001], [[01]], [0[1]], [101]

Note the number of brackets is important. Also, there's no longer the repeated zeroes shorthand.

You can replace "0" with "[]" and only use three symbols.

### Re: An interesting numeral system

I used to experiment with this. I sometimes called it "Base prime" but it's not really a base, so maybe "prime representation" is better terminology.

afarnen, It's interesting to use that way of encoding 0 and 1. I didn't think about extending the form in that manner.

When I played with this number system, I considered 0 Not-a-Number and represented 1 canonically as {0}. Because 2^0 = 1. (I also used a bracket notation, but I find {1,2,10,3} to be more readable than 112[10]3 or 1[1][2][10][3].)

You can represent fractional numbers using negative powers, so 0.5 is {-1}.

If you wanted zero to exist in this system, it could be expressed as a limit, or as an infinite sequence. For a limit: lim {-n} as n->Inf. So {-Inf} would work, if you allow infinities in your place-values to represent limits. For an infinite sequence: {-1,-1,-1,...} could be a canonical form, but we have the option of having a countably infinite number of possible ways of writing zero. This is kind of interesting, because we have multiple "numbers" in this prime-representation numeral system whose values could potentially be compared term-by-term to give us an ordering (although I don't know that it could be made into a well-ordering... I'd have to brush up on my set theory), so we could have zeroes that are greater-than or less-than other zeroes

(This reminds me of some of the ways that infinitesimals and other such things can be expressed in the hyperreals and compared...)

Also you can come up with a (nearly) binary tree providing a well-ordering of prime-rep numbers.

{0} has one child, {1} (which is what makes this not a true binary tree). But all nodes below have two children. The left child is formed by incrementing the first place-value (the exponent of 2 in the prime factorization), and the right node is found by shifting all place-values to the next higher ones. So {1} has a left child {1} and a right child {0,1}. All natural numbers can be represented in this tree. The tree can also be flattened, one row at a time, to produce a sequence; finding the sequence-positions of the natnums in the tree-sequence yields another odd sequence.

I used to write these numbers in 2^a * 3^b * 5^c * ... form as {a,b,c,...}.

However, after reading about the Zeckendorf Fibonacci representation (which is a very interesting mixed-radix base system, see http://www.maths.surrey.ac.uk/hosted-si ... ibrep.html ), I thought maybe it's better to write it how we write numbers in normal base systems, where the least significant digit is on the far right. So we'd have [...,c,b,a]. (I changed from braces to brackets to prevent ambiguity when changing forms)

If you execute an "addition" operator on the terms of prime-rep numbers, you have actual multiplication.

If you execute a long-hand "multiplication" operator on the terms (really, it's a form of convolution operator), you get a very odd table indeed. One of the first rows of this table shows up in the OEIS as A003961 (it's the result of a math puzzle by Marc LeBrun, which I cannot find a link to now).

I've played a lot with this representation, but I'm not sure what the utility of it is. It may end up being useful for providing sequences and forms which may eventually be found to show up in other branches of math. But I haven't found any yet. I am also curious about plugging in the place-values directly to Zeckendorf Fibonacci number system, primorial number system ( https://oeis.org/wiki/Primorial_numeral_system ), and factoradic number system ( https://en.wikipedia.org/wiki/Factorial_number_system ), and seeing what kinds of patterns emerge.

I wrote a bunch of code (for SAGE, bc, scheme, HP-RPL, and even bash) to play with these things, and I'm in the process of re-writing it to be a little better (commented, mostly-efficient SAGE functions for prime-rep, fibonacci representation, factoradic base, and primorial base).

Has anyone ever played with the aforementioned multiplicative operator, any different well-orderings, using nontrivial infinite sequences for the place-values, or using imaginary/complex exponents (e.g. to represent negative numbers)?

afarnen, It's interesting to use that way of encoding 0 and 1. I didn't think about extending the form in that manner.

When I played with this number system, I considered 0 Not-a-Number and represented 1 canonically as {0}. Because 2^0 = 1. (I also used a bracket notation, but I find {1,2,10,3} to be more readable than 112[10]3 or 1[1][2][10][3].)

You can represent fractional numbers using negative powers, so 0.5 is {-1}.

If you wanted zero to exist in this system, it could be expressed as a limit, or as an infinite sequence. For a limit: lim {-n} as n->Inf. So {-Inf} would work, if you allow infinities in your place-values to represent limits. For an infinite sequence: {-1,-1,-1,...} could be a canonical form, but we have the option of having a countably infinite number of possible ways of writing zero. This is kind of interesting, because we have multiple "numbers" in this prime-representation numeral system whose values could potentially be compared term-by-term to give us an ordering (although I don't know that it could be made into a well-ordering... I'd have to brush up on my set theory), so we could have zeroes that are greater-than or less-than other zeroes

(This reminds me of some of the ways that infinitesimals and other such things can be expressed in the hyperreals and compared...)

Also you can come up with a (nearly) binary tree providing a well-ordering of prime-rep numbers.

{0} has one child, {1} (which is what makes this not a true binary tree). But all nodes below have two children. The left child is formed by incrementing the first place-value (the exponent of 2 in the prime factorization), and the right node is found by shifting all place-values to the next higher ones. So {1} has a left child {1} and a right child {0,1}. All natural numbers can be represented in this tree. The tree can also be flattened, one row at a time, to produce a sequence; finding the sequence-positions of the natnums in the tree-sequence yields another odd sequence.

I used to write these numbers in 2^a * 3^b * 5^c * ... form as {a,b,c,...}.

However, after reading about the Zeckendorf Fibonacci representation (which is a very interesting mixed-radix base system, see http://www.maths.surrey.ac.uk/hosted-si ... ibrep.html ), I thought maybe it's better to write it how we write numbers in normal base systems, where the least significant digit is on the far right. So we'd have [...,c,b,a]. (I changed from braces to brackets to prevent ambiguity when changing forms)

If you execute an "addition" operator on the terms of prime-rep numbers, you have actual multiplication.

If you execute a long-hand "multiplication" operator on the terms (really, it's a form of convolution operator), you get a very odd table indeed. One of the first rows of this table shows up in the OEIS as A003961 (it's the result of a math puzzle by Marc LeBrun, which I cannot find a link to now).

I've played a lot with this representation, but I'm not sure what the utility of it is. It may end up being useful for providing sequences and forms which may eventually be found to show up in other branches of math. But I haven't found any yet. I am also curious about plugging in the place-values directly to Zeckendorf Fibonacci number system, primorial number system ( https://oeis.org/wiki/Primorial_numeral_system ), and factoradic number system ( https://en.wikipedia.org/wiki/Factorial_number_system ), and seeing what kinds of patterns emerge.

I wrote a bunch of code (for SAGE, bc, scheme, HP-RPL, and even bash) to play with these things, and I'm in the process of re-writing it to be a little better (commented, mostly-efficient SAGE functions for prime-rep, fibonacci representation, factoradic base, and primorial base).

Has anyone ever played with the aforementioned multiplicative operator, any different well-orderings, using nontrivial infinite sequences for the place-values, or using imaginary/complex exponents (e.g. to represent negative numbers)?

### Re: An interesting numeral system

Where'd you come across this system? I invented it independently, plus a couple of closely related systems for representing not just natural numbers but rational numbers and roots (most easily by going from binary to balanced ternary {-1,0,1}). I figured it's so simple that it must have been done long ago, but haven't found anything more than tangentially related. Another interesting application is in infinite numbers, where it seems to provide a possible loophole in Cantor diagonal arguments. The representation maps directly onto n-dimensional matrices and n-dimensional cellular spaces, though only tree structures within the space are unique numbers (the others are either 0, or 0^something = 1,). The mapping onto space allows specifying new kinds of possible functions graphically, say taking the pattern of one number and translating, rotating, reflecting,tiling etc. to get another pattern which specifies another number.

Here's an article I wrote on what I call "ternary factor tree representation", followed some very simple but recursive code to convert TFTR numbers to decimal or rational notation http://mindsbasis.blogspot.com/2014/07/a-curious-way-to-represent-numbers.html

Here's an article I wrote on what I call "ternary factor tree representation", followed some very simple but recursive code to convert TFTR numbers to decimal or rational notation http://mindsbasis.blogspot.com/2014/07/a-curious-way-to-represent-numbers.html

### Who is online

Users browsing this forum: No registered users and 2 guests