We’re so used to our positional notation system that we can’t really figure out how to write numbers in other systems. Most of the ancient systems are either tedious, complicated, or both. Zero, of course, plays a central role within that positional system. But is it indispensable?

In one of my classes, I discuss a lot of different numeration systems (like Egyptian, Babylonian, Roman and Greek) to explain why the positional system solves all, or at least most, of these systems’ problems. I even give the example of Shadok counting (in french) to show that the basis used isn’t that important (it still has to be greater than one, and, while not strictly necessary, preferably a positive integer). But can we write numbers in a positional system without zero?

The usual “to base 10” routine would look something like this:

```std::string to_decimal(int n)
{
std::string t;
do
{
t.insert(t.begin(),'0'+(n%10));
} while (n/=10);

return t;
}
```

The function extracts, one by one, a digit and prepends it to the string. But this function uses zero and behaves as we are used to. It can write a number like 204120, and its interpretation is unambiguous.

Now, how do we modify this routine so that it doesn’t use a zero but still writes down unambiguous numbers?

Let’s get back to the Shadoks. In the video, we see that before using a base-4 positional system, which includes a zero, the Shadoks used numerals for one, two, three and four, but no zero. Let’s see how a Shadok could have written numbers without using zeroes.

Without a zero, zero can’t be written down, so the numbers start at one, we’re in the real of natural numbers. We have only four symbols, let’s say a,b,c,d. The first numbers are, of course, a, b, c, and d, which are 1, 2, 3, and 4. Then we have aa, ab, ac, ad, which are 5, 6, 7, 8. Then ba, bc,… you get the idea.

In the above code snippet, we use modulo to extract a digit, but modulo extracts a number from 0 to base-1, whichever base we use. What we need to write without a zero is an operation that extracts a number from 1 to base, inclusive, for the next digit. In the Shadok system, it would extract 1, 2, 3, or 4. Turns out, modulo can still serve:

```std::string to_protoshadok(int n)
{
std::string t;

while (n)
{
int r = n % 4;
r=r ? r : 4;
t.insert(t.begin(),'a'+r-1);
n-=r;
n/=4;
}

return t;
}
```

There’s likely a better implementation of the two operations r=n%4 and r=r ? r : 4, but it will suffice for now. Indeed, it outputs the desired result:

```1	a
2	b
3	c
4	d
5	aa
6	ab
7	ac
9	ba
10	bb
11	bc
12	bd
13	ca
14	cb
15	cc
16	cd
17	da
18	db
19	dc
20	dd
21	aaa
22	aab
23	aac
...
```

*
* *

This system works, but is very counter-intuitive. In this system, 8 is not written as 2 times 4, but as 1 times 4 plus 4. But simple arithmetic, such as addition, seems to remains pretty much the same except that borrow and carry rules vary only slightly. It’s probably not that practical, but it shows that we can write numbers in a positional system without a zero.

### 2 Responses to The protoshadok number system

1. o0o says:

This idea has been rediscovered many times… afaict, the “official” name for it is “Bijective numeration”: https://en.wikipedia.org/wiki/Bijective_numeration

• Oh, I’m not pretending I’ve invented it; I’m just presenting the idea.