# Monthly Archives: August 2018

# Weight-Botchers

Suppose you have a balance scale and four weights of 1 unit, 2 units, 4 units and 8 units. How many different weights can you match? If you know binary arithmetic, it’s easy to see that you can match any weight up to fifteen units inclusive. With the object in the left-hand pan of the scale and the weights in the right-hand pan, these are the matches:

01 = 1

02 = 2

03 = 2+1

04 = 4

05 = 4+1

06 = 4+2

07 = 4+2+1

08 = 8

09 = 8+1

10 = 8+2

11 = 8+2+1

12 = 8+4

13 = 8+4+1

14 = 8+4+2

15 = 8+4+2+1

The weights that sum to

*n*match the 1s in the digits of

*n*in binary.

01 = 0001 in binary

02 = 0010 = 2

03 = 0011 = 2+1

04 = 0100 = 4

05 = 0101 = 4+1

06 = 0110 = 4+2

07 = 0111 = 4+2+1

08 = 1000 = 8

09 = 1001 = 8+1

10 = 1010 = 8+2

11 = 1011 = 8+2+1

12 = 1100 = 8+4

13 = 1101 = 8+4+1

14 = 1110 = 8+4+2

15 = 1111 = 8+4+2+1

01 = 0001 in binary

02 = 0010 = 2

03 = 0011 = 2+1

04 = 0100 = 4

05 = 0101 = 4+1

06 = 0110 = 4+2

07 = 0111 = 4+2+1

08 = 1000 = 8

09 = 1001 = 8+1

10 = 1010 = 8+2

11 = 1011 = 8+2+1

12 = 1100 = 8+4

13 = 1101 = 8+4+1

14 = 1110 = 8+4+2

15 = 1111 = 8+4+2+1

But there’s another set of four weights that will match anything from 1 unit to 40 units. Instead of using powers of 2, you use powers of 3: 1, 3, 9, 27. But how would you match an object weighing 2 units using these weights? Simple. You put the object in the left-hand scale, the 3-weight in the right-hand scale, and then add the 1-weight to the

__left-hand__scale. In other words, 2 = 3-1. Similarly, 5 = 9-3-1, 6 = 9-3 and 7 = 9-3+1. When the power of 3 is positive, it’s in the right-hand pan; when it’s negative, it’s in the left-hand pan.

This system is actually based on base 3 or ternary, which uses three digits, 0, 1 and 2. However, the relationship between ternary numbers and the sums of positive and negative powers of 3 is more complicated than the relationship between binary numbers and sums of purely positive powers of 2. See if you can work out how to derive the sums in the middle from the ternary numbers on the right:

01 = 1 = 1 in ternary

02 = 3-1 = 2

03 = 3 = 10

04 = 3+1 = 11

05 = 9-3-1 = 12

06 = 9-3 = 20

07 = 9-3+1 = 21

08 = 9-1 = 22

09 = 9 = 100

10 = 9+1 = 101

11 = 9+3-1 = 102

12 = 9+3 = 110

13 = 9+3+1 = 111

14 = 27-9-3-1 = 112

15 = 27-9-3 = 120

16 = 27-9-3+1 = 121

17 = 27-9-1 = 122

18 = 27-9 = 200

19 = 27-9+1 = 201

20 = 27-9+3-1 = 202

21 = 27-9+3 = 210

22 = 27-9+3+1 = 211

23 = 27-3-1 = 212

24 = 27-3 = 220

25 = 27-3+1 = 221

26 = 27-1 = 222

27 = 27 = 1000

28 = 27+1 = 1001

29 = 27+3-1 = 1002

30 = 27+3 = 1010

31 = 27+3+1 = 1011

32 = 27+9-3-1 = 1012

33 = 27+9-3 = 1020

34 = 27+9-3+1 = 1021

35 = 27+9-1 = 1022

36 = 27+9 = 1100

37 = 27+9+1 = 1101

38 = 27+9+3-1 = 1102

39 = 27+9+3 = 1110

40 = 27+9+3+1 = 1111

To begin understanding the sums, consider those ternary numbers containing only 1s and 0s, like *n* = 1011_{[3]}, which equals 31 in decimal. The sum of powers is straightforward, because all of them are positive and they’re easy to work out from the digits of *n* in ternary: 1011 = 1*3^3 + 0*3^2 + 1*3^1 + 1*3^0 = 27+3+1. Now consider *n* = 222_{[3]} = 26 in decimal. Just as a decimal number consisting entirely of 9s is always 1 less than a power of 10, so a ternary number consisting entirely of 2s is always 1 less than a power of three:

999 = 1000 - 1 = 10^3 - 1 (decimal)

222 = 1000_{[3]} - 1 (ternary) = 26 = 27-1 = 3^3 - 1 (decimal)

If a ternary number contains only 2s and is *d* digits long, it will be equal to 3^*d* – 1. But what about numbers containing a mixture of 2s, 1s and 0s? Well, all ternary numbers containing at least one 2 will have a negative power of 3 in the sum. You can work out the sum by using the following algorithm. Suppose the number is five digits long and the rightmost digit is digit #1 and the leftmost is digit #5:

01. *i* = 1, *sum* = 0, *extra* = 0, *posi* = true.

02. if *posi* = false, goto step 07.

03. if digit #*i* = 0, *sum* = *sum* + 0.

04. if digit #*i* = 1, *sum* = *sum* + 3^(i-1).

05. if digit #*i* = 2, *sum* = *sum* - 3^(i-1), *extra* = 3^5, *posi* = false.

06. goto step 10.

07. if digit #*i* = 0, *sum* = *sum* + 3^(i-1), *extra* = 0, *posi* = true.

08. if digit #*i* = 1, *sum* = *sum* - 3^(i-1).

09. if digit #*i* = 2, *sum* = *sum* + 0.

10. *i* = *i*+1. if *i* <= 5, goto step 2.

11. print *sum* + *extra*.

As the number of weights grows, the advantages of base 3 get bigger:

With 02 weights, base 3 reaches 04 and base 2 reaches 3: 04-3 = 1.

With 03 weights, base 3 reaches 13 and base 2 reaches 7: 13-7 = 6.

With 04 weights, 000040 - 0015 = 000025

With 05 weights, 000121 - 0031 = 000090

With 06 weights, 000364 - 0063 = 000301

With 07 weights, 001093 - 0127 = 000966

With 08 weights, 003280 - 0255 = 003025

With 09 weights, 009841 - 0511 = 009330

With 10 weights, 029524 - 1023 = 028501

With 11 weights, 088573 - 2047 = 086526

With 12 weights, 265720 - 4095 = 261625...

But what about base 4, or quaternary? With four weights of 1, 4, 16 and 64, representing powers of 4 from 4^0 to 4^3, you should be able to weigh objects from 1 to 85 units using sums of positive and negative powers. In fact, some weights can’t be matched. As you can see below, if *n* in base 4 contains a 2, it usually can’t be represented as a sum of positive and negative powers of 4 (one exception is 23 = 2*4 + 3 = 11 in base 10). Certain other numbers are also impossible to represent as that kind of sum:

1 = 1 ← 1

2 has no sum = 2

3 = 4-1 ← 3

4 = 4 ← 10 in base 4

5 = 4+1 ← 11 in base 4

6 has no sum = 12 in base 4

7 has no sum = 13

8 has no sum = 20

9 has no sum = 21

10 has no sum = 22

11 = 16-4-1 ← 23

12 = 16-4 ← 30

13 = 16-4+1 ← 31

14 has no sum = 32

15 = 16-1 ← 33

16 = 16 ← 100

17 = 16+1 ← 101

18 has no sum = 102

19 = 16+4-1 ← 103

20 = 16+4 ← 110

21 = 16+4+1 ← 111

22 has no sum = 112

23 has no sum = 113

24 has no sum = 120

25 has no sum = 121

26 has no sum = 122

27 has no sum = 123

[...]

With a more complicated balance scale, it’s possible to use weights representing powers of base 4 and base 5 (use two pans on each arm of the scale instead of one, placing the extra pan at the midpoint of the arm). But with a standard balance scale, base 3 is the champion. However, there is a way to do slightly better than standard base 3. You do it by botching the weights. Suppose you have four weights of 1, 4, 10 and 28 (representing 1, 3+1, 9+1 and 27+1). There are some weights *n* you can’t match, but because you can match *n*-1 and *n*+1, you know what these unmatchable weights are. Accordingly, while weights of 1, 3, 9 and 27 can measure objects up to 40 units, weights of 1, 4, 10 and 28 can measure objects up to 43 units:

1 = 1 ← 1

2 has no sum = 2

3 = 4-1 ← 10 in base 3

4 = 4 ← 11 in base 3

5 = 4+1 ← 12 in base 3

6 = 10-4 ← 20

7 = 10-4+1 ← 21

8 has no sum = 22

9 = 10-1 ← 100

10 = 10 ← 101

11 = 10+1 ← 102

12 has no sum = 110

13 = 10+4-1 ← 111

14 = 10+4 ← 112

15 = 10+4+1 ← 120

16 has no sum = 121

17 = 28-10-1 ← 122

18 = 28-10 ← 200

19 = 28-10+1 ← 201

20 has no sum = 202

21 = 28-10+4-1 ← 210

22 = 28-10+4 ← 211

23 = 28-4-1 ← 212

24 = 28-4 ← 220

25 = 28-4+1 ← 221

26 has no sum = 222

27 = 28-1 ← 1000

28 = 28 ← 1001

29 = 28+1 ← 1002

30 has no sum = 1010

31 = 28+4-1 ← 1011

32 = 28+4 ← 1012

33 = 28+4+1 ← 1020

34 = 28+10-4 ← 1021

35 = 28+10-4+1 ← 1022

36 has no sum = 1100

37 = 28+10-1 ← 1101

38 = 28+10 ← 1102

39 = 28+10+1 ← 1110

40 = has no sum = 1111*

41 = 28+10+4-1 ← 1112

42 = 28+10+4 ← 1120

43 = 28+10+4+1 ← 1121

`*N.B. 40 = 82-28-10-4, i.e. has a sum when another botched weight, 82 = 3^4+1, is used.
`

# Cat’s I

# WhirlpUlam

Stanislaw Ulam (pronounced OO-lam) was an American mathematician who was doodling one day in 1963 and created what is now called the Ulam spiral. It’s a spiral of integers on a square grid with the prime squares filled in and the composite squares left empty. At the beginning it looks like this (the blue square is the integer 1, with 2 to the east, 3 to the north-east, 4 to the north, 5 to the north-west, 6 to the west, and so on):

And here’s an Ulam spiral with more integers:

The primes aren’t scattered at random over the spiral: they often fall into lines that are related to what are called polynomial functions, such as n

^{2}+ n + 1. To understand polynomial functions better, let’s look at how the Ulam spiral is made. Here is a text version with the primes underlined:

Here’s an animated version:

Here’s the true spiral again with 1 marked as a blue square:

What happens when you try other numbers at the centre? Here’s 2 at the centre as a purple square, because it’s prime:

And 3 at the centre, also purple because it’s also prime:

And 4 at the centre, blue again because 4 = 2^2:

And 5 at the centre, prime and purple:

Each time the central number changes, the spiral shifts fractionally. Here’s an animation of the central number shifting from 1 to 41. If you watch, you’ll see patterns remaining stable, then breaking up as the numbers shift towards the center and disappear (the central number is purple if prime, blue if composite):

I think the animation looks like a whirlpool or whirlpUlam (prounced whirlpool-am), as numbers spiral towards the centre and disappear. You can see the whirlpUlam more clearly here:

Note that something interesting happens when the central number is 41. The spiral is bisected by a long line of prime squares, like this:

The line is actually a visual representation of something David Wells wrote about in *The Penguin Dictionary of Curious and Interesting Numbers* (1986):

Euler discovered the excellent and famous formula x

^{2}+ x + 41, which gives prime values for x = 0 to 39.

Here are the primes generated by the formula:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

You’ll see other lines appear and disappear as the whirlpUlam whirls:

Primes in line: 17, 19, 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227, 257 (n=0..15)

`
`

Primes in line: 59, 67, 83, 107, 139, 179, 227, 283, 347, 419, 499, 587, 683, 787 (n=0..13)

Primes in line: 163, 167, 179, 199, 227, 263, 307, 359, 419, 487, 563, 647, 739, 839, 947, 1063, 1187, 1319, 1459, 1607 (n=0..19)

Primes in line: 233, 241, 257, 281, 313, 353, 401, 457, 521, 593, 673, 761, 857 ((n=0..12)

Primes in line: 653, 661, 677, 701, 733, 773, 821, 877, 941, 1013, 1093, 1181, 1277, 1381, 1493, 1613, 1741, 1877 (n=0..17)

Primes in line: 409,333, 409337, 409349, 409369, 409397, 409433, 409477, 409529, 409589, 409657, 409733, 409817, 409909, 410009, 410117, 410233 (n=0..15)

Some bisect the centre, some don’t, because you could say that the Ulam spiral has six diagonals, two that bisect the centre (top-left-to-bottom-right and bottom-left-to-top-right) and four that don’t. You could also call them spokes:

If you look at the integers in the spokes, you can see that they’re generated by polynomial functions in which *c* stands for the central number:

North-west spoke: 1, 5, 17, 37, 65, 101, 145, 197, 257, 325, 401, 485, 577, 677, 785, 901, 1025, 1157, 1297, 1445, 1601, 1765, 1937, 2117, 2305, 2501, 2705, 2917... = c + (2n)^2

South-east spoke: 1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089, 1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481, 3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625... = c+(2n+1)^2-1

NW-SE diagonal: 1, 5, 9, 17, 25, 37, 49, 65, 81, 101, 121, 145, 169, 197, 225, 257, 289, 325, 361, 401, 441, 485, 529, 577, 625, 677, 729, 785, 841, 901, 961, 1025, 1089, 1157, 1225, 1297, 1369, 1445, 1521, 1601, 1681 = c + n^2 + 1 - (n mod 2)

North-east spoke: 1, 3, 13, 31, 57, 91, 133, 183, 241, 307, 381, 463, 553, 651, 757, 871, 993, 1123, 1261, 1407, 1561, 1723, 1893, 2071... = c + (n+1)^2 - n - 1

South-west spoke: 1, 7, 21, 43, 73, 111, 157, 211, 273, 343, 421, 507, 601, 703, 813, 931, 1057, 1191, 1333, 1483, 1641, 1807, 1981, 2163... = c + (2n)^2 + 2n

SW-NE diagonal: 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507, 553, 601, 651, 703, 757, 813, 871, 931, 993, 1057, 1123, 1191, 1261, 1333, 1407, 1483, 1561, 1641... = c + n^2 + n

Elsewhere other-engageable:

• All posts interrogating issues around the Ulam spiral