Playing the Double Base

Here’s some mathematical nonsense:

10 > 12
100 > 122
1000 > 1222

How can 1000 > 1222? Well, it makes perfect sense in what you might call a double base. In this base, every number is identified by a unique string of digits, but the strings don’t behave as they do in a standard base.

To see how this double base works, first look at 9 in standard base 2. To generate the binary digits from right to left, you follow the procedure x mod 2 and x = x div 2, where (x mod 2) returns the remainder when x is divided by 2 and (x div 2) divides x by 2 and discards the remainder:

9 mod 2 = 1 → ...1
9 div 2 = 4
4 mod 2 = 0 → ..01
4 div 2 = 2
2 mod 2 = 0 → .001
2 div 2 = 1
1 mod 2 = 1 → 1001

So 9[b=10] = 1001[b=2]. To adapt the procedure to base 3, simply use x mod 3 and x = x div 3:

32 mod 3 = 2 → ...2
32 div 3 = 10
10 mod 3 = 1 → ..12
10 div 3 = 3
3 mod 3 = 0 → .012
3 div 3 = 1
1 mod 3 = 1 → 1012

So 32[b=10] = 1012[b=3].

But what happens if you mix bases and use (x mod 3) and (x div 2), like this?:

2 mod 3 = 2 → .2
2 div 2 = 1
1 mod 3 = 1 → 12

3 mod 3 = 0 → .0
3 div 2 = 1
1 mod 3 = 1 → 10

So 10 > 12, i.e. 10[b=3,2] > 12[b=3,2].

5 mod 3 = 2 → ..2
5 div 2 = 2
2 mod 3 = 2 → .22
2 div 2 = 1
1 mod 3 = 1 → 122

6 mod 3 = 0 → ..0
6 div 2 = 3
3 mod 3 = 0 → .00
3 div 2 = 1
1 mod 3 = 1 → 100

So 100 > 122.

11 mod 3 = 2 → ...2
11 div 2 = 5
5 mod 3 = 2 → ..22
5 div 2 = 2
2 mod 3 = 2 → .222
2 div 2 = 1
1 mod 3 = 1 → 1222

12 mod 3 = 0 → …0
12 div 2 = 6
6 mod 3 = 0 → ..00
6 div 2 = 3
3 mod 3 = 0 → .000
3 div 2 = 1
1 mod 3 = 1 → 1000

And 1000 > 1222. Here are numbers 1 to 32 in this double base:

1 = 1
12 = 2
10 = 3
121 = 4
122 = 5
100 = 6
101 = 7
1212 = 8
1210 = 9
1221 = 10
1222 = 11
1000 = 12
1001 = 13
1012 = 14
1010 = 15
12121 = 16
12122 = 17
12100 = 18
12101 = 19
12212 = 20
12210 = 21
12221 = 22
12222 = 23
10000 = 24
10001 = 25
10012 = 26
10010 = 27
10121 = 28
10122 = 29
10100 = 30
10101 = 31
121212 = 32

Given a number represented in this mixed base, how do you extract the underlying n? Suppose the number takes the form n = (digit[1]..digit[di]), where digit[1] is the first and leftmost digit and digit[di] the final and rightmost digit. Then this algorithm will extract n:

n = 1
for i = 2 to di
..n = n * 2
..while n mod 3 ≠ digit[i]
....n = n + 1
..endwhile
next i
print n

For example, suppose n = 12212[b=3,2]. Then di = 5 and the algorithm will work like this:

n = 1
n = n * 2 = 2.
2 mod 3 = 2 = digit[2]
2 * 2 = 4
4 mod 3 = 1 ≠ digit[3]
5 mod 3 = 2 = digit[3]
5 * 2 = 10
10 mod 3 = 1 = digit[4]
10 * 2 = 20
20 mod 3 = 2 = digit[5]

Therefore 12212[b=3,2] = 20[b=10].

Now try some more mathematical nonsense:

21 > 100
111 > 1,000
1,001 > 10,000
10,001 > 100,000

How can numbers with d digits be greater than numbers with d+1 digits? Easily. In this incremental base, the base adjusts itself as the digits are generated, like this:

5 mod 2 = 1 → .1
5 div 2 = 2
2 mod (2 + 1) = 2 mod 3 = 2 → 21

The first digit generated is 1, so the base increases to (2 + 1) = 3 for the second digit. Compare the procedure when n = 4:

4 mod 2 = 0 → ..0
4 div 2 = 2
2 mod 2 = 0 → .00
2 div 2 = 1
1 mod 2 = 1 → 100

So 21 > 100, because 4 is a power of 2 and all the digits generated by (x mod 2) are 0 except the final and leftmost. 2 + 0 = 2. Now try n = 33:

33 mod 2 = 1 → ...1
33 div 2 = 16
16 mod (2+1) = 16 mod 3 = 1 → ..11
16 div 3 = 5
5 mod (3+1) = 5 mod 4 = 1 → .111
5 div 4 = 1
1 mod (4+1) = 1 mod 5 = 1.

33[b=10] = 1111[b=2,3,4,5].

Here are numbers 1 to 60 in this incremental base (note how 21 > 100, 111 > 1000, 1001 > 10000 and 10001 > 100000):

1 = 1
10 = 2
11 = 3
100 = 4*
21 = 5*
110 = 6
101 = 7
1000 = 8*
111 = 9*
210 = 10
121 = 11
1100 = 12
201 = 13
1010 = 14
211 = 15
10000 = 16*
221 = 17
1110 = 18
1001 = 19*
2100 = 20
311 = 21
1210 = 22
321 = 23
11000 = 24
1101 = 25
2010 = 26
1011 = 27
10100 = 28
421 = 29
2110 = 30
1201 = 31
100000 = 32*
1111 = 33
2210 = 34
1021 = 35
11100 = 36
2001 = 37
10010 = 38
1211 = 39
21000 = 40
1121 = 41
3110 = 42
2101 = 43
12100 = 44
1311 = 45
3210 = 46
1221 = 47
110000 = 48
2201 = 49
11010 = 50
2011 = 51
20100 = 52
1321 = 53
10110 = 54
10001 = 55*
101000 = 56
2111 = 57
4210 = 58
1421 = 59
21100 = 60

And here are numbers 256 to 270 (Note how 8,421 > 202,100 > 100,000,000):

100000000 = 256*
11221 = 257
101110 = 258
32101 = 259
202100 = 260*
13311 = 261
41210 = 262
10321 = 263
1111000 = 264
24201 = 265
131010 = 266
23011 = 267
320100 = 268
8421 = 269*
52110 = 270

Extracting n from a number represented in this incremental base is trickier than for the double base using (x mod 3) and (x div 2). To see how to do it, examine 11221[b=incremental]. The fifth and rightmost digit is 1, so the base increases to (2 + 1) = 3 for the fourth digit, which is 2. The base increases to (3 + 2) = 5 for the third digit, which is 2 again. The base increases to (5 + 2) = 7 for the second digit, 1. But the first and rightmost digit, 1, represents (x div 7) mod (7 + 1 = 8). So n can be extracted like this:

digit[1] * 7 = 1 * 7 = 7
7 mod 7 = 0 ≠ digit[2]
8 mod 7 = 1 = digit[2]
8 * 5 = 40
40 mod 5 = 0 ≠ digit[3]
41 mod 5 = 1 ≠ digit[3]
42 mod 5 = 2 = digit[3]
42 * 3 = 126
126 mod 3 = 0 ≠ digit[4]
127 mod 3 = 1 ≠ digit[4]
128 mod 3 = 2 = digit[4]
128 * 2 = 256
256 mod 2 = 0 ≠ digit[5]
257 mod 2 = 1 = digit[5]

So 11221[b=8,7,5,3,2] = 257[b=10].

Now try 8421[b=incremental]. The fourth and rightmost digit is 1, so the base increases to (2 + 1) = 3 for the third digit, which is 2. The base increases to (3 + 2) = 5 for the second digit, 4. But the first and rightmost digit, 8, represents (x div 5) mod (5 + 4 = 9). So n can be extracted like this:

digit[1] * 5 = 8 * 5 = 40
40 mod 5 = 0 ≠ digit[2]
41 mod 5 = 1 ≠ digit[2]
42 mod 5 = 2 ≠ digit[2]
43 mod 5 = 3 ≠ digit[2]
44 mod 5 = 4 = digit[2]
44 * 3 = 132
132 mod 3 = 0 ≠ digit[3]
133 mod 3 = 1 ≠ digit[3]
134 mod 3 = 2 = digit[3]
134 * 2 = 268
268 mod 2 = 0 ≠ digit[4]
269 mod 2 = 1 = digit[4]

So 8421[b=9,5,3,2] = 269[b=10].

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s