I was thinking about the Four Weights
problem again
recently. You might recall that puzzle poses the question: what are the four
weights that can weigh any object

The puzzle just asks you to find the values of the weights, which are
*how* do you weigh

I’m sure if I were the merchant who had to do this every day, I’d
quickly get an approximate feel for the weight of any

So I reduced to a simpler problem: *If I know the value of , how do I
balance the scale?*

This isn’t a practical question, since if I know

## Converting to a base-n representation #

Assume you want to represent a nonnegative integer with up to

```
i = 0 # assume indexing starts at 0
r = zeros(m) # all-zeros vector of length m
if x >= 2^m then throw("x is out of range")
while x > 0
d = floor(x/2)
r[i] = x mod 2
x = d
i = i+1
return reverse(r) # so lowest value digit is rightmost
```

Let’s do it by hand for

```
13/2 = 6 rem 1 (d = 6, r = 1)
6/2 = 3 rem 0
3/2 = 1 rem 1
1/2 = 0 rem 1
```

So we have 13 = 1101 in base-2, or `(1*8) + (1*4) + (0*2) + (1*1)`

.

For an unsigned trinary representation, the idea is the same, only you
divide by 3 instead of 2. Let’s try it with 18, using 4 digits (which
can represent up to the value

```
18/3 = 6 rem 0
6/3 = 2 rem 0
2/3 = 0 rem 2
```

So 18 = 0200 in base-3, or `(0*27) + (2*9) + (0*3) + (0*1)`

.

We can write a general function to convert a decimal number `x`

to
base-n representation. I’ll do it in R, just because I’ve been doing all
my puzzles in R.

```
# convert x to its unsigned base-n representation
# n: the base
# ndigits: the maximum number of digits
base_n = function(x, n, ndigits) {
r = numeric(ndigits)
if(x >= n^ndigits) stop("x is out of range")
i = 1
while(x > 0) {
d = floor(x/n)
r[i] = x %% n
x = d
i = i+1
}
rev(r)
}
# convert from unsigned base-n back to decimal
to_decimal = function(r, n) {
r = rev(r) # put the lowest digit to the leftmost
ndigits = length(r)
x = 0
for(i in 1:ndigits)
x = x + r[i] * n^(i-1)
x
}
```

```
# convert 13 to binary
r = base_n(13, 2, 4)
# confirm this is 13
stopifnot(to_decimal(r, 2)==13)
r
```

## [1] 1 1 0 1

```
# convert 18 to trinary
r = base_n(18, 3, 4)
# confirm this is 18
stopifnot(to_decimal(r, 3)==18)
r
```

## [1] 0 2 0 0

## Converting to signed trinary #

Recall that when solving the Four Weights problem, we established that
any nonnegative integer value

where the weights `(1, 3, 9, 27)`

—we write it smallest-first,
consistently with the previous post on this problem—and

The four digits still represent

To modify the unsigned trinary conversion to a signed one, we use the observation that

- The equation
`x/3 = d rem 2`

is equivalent to the equation`x/3 = (d+1) rem -1`

.

This is a bit of an abuse of the notation; but here’s an example of what we are trying to say. We know that

`8/3 = 2 rem 2`

, which is the same as saying`8 = 2*3 + 2`

.

Another way of writing this is

`8 = (2+1)*3 - 1 = 3*3 - 1`

which we’ll write as:`8/3 = 3 rem -1`

So (when considering only nonnegative

```
i = 0 # assume indexing starts at 0
r = zeros(m)
maxval = (3^m - 1)/2
if x > maxval then throw("x is out of range")
while x > 0
d = floor(x/3)
r[i] = x mod 3
if r[i]==2
d = d+1
r[i] = -1
x = d
i = i+1
return r # we won't reverse it, to be consistent with our puzzle solution
```

Let’s convert 18 to signed trinary.

```
18/3 = 6 rem 0
6/3 = 2 rem 0
2/3 = 0 rem 2 = 1 rem -1
1/3 = 0 rem 1
```

So 18 = [0 0 -1 1] = `(0*1) + (0*3) + (-1*9) + (1*27)`

. In the scale
notation that we used while solving the puzzle, we would write this as

Here’s the code.

```
# convert nonnegative x to signed trinary
weigh = function(x) {
if(x > 40) stop("x out of range")
r = numeric(4)
i = 1
while(x > 0) {
d = floor(x/3)
r[i] = x %% 3
if(r[i]==2) {
d = d+1
r[i] = -1
}
x = d
i = i+1
}
r
}
# write the signed trinary representation in our scale notation
scale_notation = function(signs) {
w = c(1, 3, 9, 27)
lefti = which(signs > 0)
righti = which(signs < 0)
leftset = paste(w[lefti], collapse=", ")
if(length(righti) > 0)
rightset = paste("x,", paste(w[righti], collapse=", "))
else
rightset = "x"
notation = paste("[ {", leftset, "} | {", rightset, "} ]")
notation
}
# convert signed trinary back to decimal
to_x = function(signs) {
w = c(1, 3, 9, 27)
x = sum(w*signs) # dot product of w and signs
}
```

Let’s try a few.

```
x = 18
signs = weigh(x)
# convert back and check it's the same number
stopifnot(x == to_x(signs))
scale_notation(signs)
```

## [1] "[ { 27 } | { x, 9 } ]"

```
x = 35
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)
```

## [1] "[ { 9, 27 } | { x, 1 } ]"

```
x = 15
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)
```

## [1] "[ { 27 } | { x, 3, 9 } ]"

```
x = 30
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)
```

## [1] "[ { 3, 27 } | { x } ]"

```
x = 4
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)
```

## [1] "[ { 1, 3 } | { x } ]"

So now we can weigh objects we know the weight of. Hurrah? But I still think it’s cute.