Category Archives: Creamy Filling

Evenness in Odd Bases

Everyone knows how to test for evenness: just check the last digit. If it’s in \{0,2,4,6,8\} then the number is even, no matter what other digits it has. This rule works in base 10 but not in base 3. In fact, this rule works in all even bases and fails in all odd bases. Why? And how do we test for evenness in odd bases?

Before we go into the details I want to ask two favors. First, if you are a math person, please forgive my sloppy use of terminology and typesetting; I have read very little math and written less. Second, for those who don’t already know the trick in odd bases: please don’t try to get the answer by inspection and intuition. Many people will find it easy to spot the pattern in a series of numbers. The treasure in this post is not the simple trick we learn for testing evenness, but the journey following the reasoning that proves that the trick works. So don’t even think about pondering a series of odd numbers because you’ll miss the journey of the proof.

Okay, let’s get the terminology and notation down before we start. Base 10 means we represent all numbers using only ten digits: 0-9. (Another word for base is radix.) Normally we write and read numbers in the decimal system which uses base 10 but any whole number can be used as a base: 2, 3, 10, 60, etc. When we represent numbers in different bases we place the number in parentheses followed by the base in subscript.

(number)_{base}

When we omit the subscript, the base is assumed to be 10. It’s important to have this notation because similar numbers have different values in different bases. For example, the three-digit number 100 represents one hundred in base 10.

(100)_{10} = 1\times10^2 + 0\times10^1 + 0\times10^0 = 100

In base 2 those digits represent a value of four.

(100)_2 = 1\times2^2 + 0\times2^1 + 0\times2^0 = 4

In base 3 the same three digits represent nine.

(100)_3 = 1\times3^2 + 0\times3^1 + 0\times3^0 = 9

That covers all of the technical lingo we need for this journey so let’s start.

First, let’s see why the evenness test is so easy in even bases. Evenness is just divisibility by 2. So let’s review how numbers and bases work. A number is the sum of its parts, which are its digits multiplied by their place values. We add 100 and 20 and 3 to get 123.

123 = 100 + 20 + 3 = 1\times10^2 + 2\times10^1 + 3\times10^0

Whatever is in the tens place, its value will be a multiple of ten. Two is a factor of ten. Two is therefore a factor of any whole multiple of ten. Adding an even number (a multiple of two) to any number X can not change the evenness of X. So it makes no difference how many tens or hundreds or thousands we add; the units place alone determines whether the number is divisible by 2. This is true in all even bases, not just 10. We can illustrate this by writing 123 in bases 8, 6, 4 and 2.

123 = (173)_8 = (323)_6 = (1323)_4 = (1111011)_2

In each of the above representations of 123, the digit in the units place is an odd number. That’s enough information to settle the question of evenness. It doesn’t matter that we don’t immediately recognize the that (1232_4) = 123; we can tell that it’s even just by checking the last digit.

Now let’s see what happens when we rewrite 123 in a few odd bases.

123 = (146)_9 = (234)_7 = (443)_5 = (4120)_3

The last digit can be even or odd but we know these numbers are all odd. Clearly the units place is not a reliable indicator of evenness. Why not? Because the radix is odd, multiples of the radix can be odd or even. Therefore the digits in the other places are capable of holding odd or even values. So our evenness test must consider all of the digits of the number.

Let’s remember how digits work together to make a number: they are added together. How does addition affect evenness? Adding an even number has no effect, but adding an odd number to X reverses the evenness of X. Adding two odds makes an even. Extending this, adding an even number of odds makes an even.

How does this help us? Well, every product of two odd numbers is itself odd. This is true because odd numbers are defined by the lack of 2 in its prime factorization. It also applies to powers of odd numbers. No matter how many times you multiply 3 by itself, the result is odd. So we know that each and every place value in an odd base is odd because it is a power of an odd number. This gives us the last clue we need for our trick: every even digit adds an even number, while every odd digit adds an odd number to the total.

The trick, then, finally, is to count the number of odd digits in the number, ignoring any evens. If the number of odd digits is even, all of the oddness cancels out and the number is even. If the number of odd digits is odd, the number is odd.

While the odd-based evenness test may lose to the even-based test on the grounds of speed (inspecting every digit instead of just one) and on the grounds of usefulness (does anyone use odd bases for anything, ever?) I find it much more satisfying because I can derive it myself.

If you found this little journey interesting, others divisibility tricks also have parallels in other bases. Take the trick for 9: if the digits sum to 9, the number is divisible by 9. This works in base 10 because 9=10-1. The same trick works in base 8: if the digits sum to 7, the number is divisible by 7. In general terms, if the digits sum to radix - 1, the number is divisible by radix - 1. I haven’t derived the proof for that one yet.

Let me know if you would like this kind of thing better as a vihart-style video.

Credit goes to Zoe Skelton for helpful feedback prior to publication.

 

Macro Monday

Yesterday the girls played with frogs out in the neighborhood. If you asked the frogs, who were quite worn out at the end of the session, this would not be a good subject for macro photography. I brought out my Panasonic GX8 with 10mm macro extension tube and 14-140mm lens and shot video for about 20 minutes. Most of the footage is blurred by focus and/or motion but there were a few good clips and several good frames. You can have the frames now and I will post the clips on YouTube later, so go and subscribe to my YouTube channel today.

Update:

Where is Tesla taking us?

We know they plan a network of charging stations. How far will that go?

I want to see full-service pit stations that can change batteries faster than they can charge them. Even faster than you can fill a 15-gallon tank.

Customer: Car says it needs a lube. I’m going inside for a rest.

She has already accepted the service with a tap while rolling into the service bay. Her instructions echo what the mechanic has already downloaded from the car.

Station: Did you want to freshen these tires? We have a new set just like yours on clean rims. Takes about 10 minutes. If not we’ll park it over there with fresh batteries and lube.

The verbal offer echoes what the driver can already read on her car’s screen. With another tap the deal is accepted. She thinks for a second, then taps “Wash” and places her car in “station valet” mode. She reads the estimated time of departure from the screen and walks inside.

A station or its agent is equipped with a device that allows the vehicle to be driven around the station. After the mechanical work is finished, the car is pulled forward into a wash bay, then dried and parked. The on-board computer and the station have independent alarms which are triggered if a car in station valet mode somehow leaves the premises.

The customer’s account profile contains her billing and communication preferences. She has opted to receive a text message describing the location of her car. Thoroughly refreshed, they reunite to continue their journey.

That’s a nice visit to a service station, manned or unmanned. But the one you’ll do most often is this: pull in, sit there for half a minute while your batteries are changed, pull out.