Enginursday: Divisibility

by Byron J.
February 26, 2015

Engineering

Thoughts and ramblings about numbers, plus an interesting discovery.

When I was in seventh grade, my math teacher often deviated from the textbook lessons, trying to instill an intuitive sense of how numbers work. These digressions were probably leftovers of the "new math" concepts from the sixties, and formed the seeds of what is known as numeracy, or numeric literacy.

One of those lessons was how to check for integer divisibility - can we divide an integer number by another, with no remainder? And can we do the check in the time it takes our eye to scan the number, not having to punch it into a calculator or grind out the long division?

As a side note - I didn't know it at the time, but the distinction between integers and fractional numbers becomes pretty significant when you start getting into computer programming - particularly for embedded platforms. On small chips like the AVR (the heart of a RedBoard), the chip has internal hardware that can handle integer math on its own, but its floating point numbers are computed using a software library. Doing floating point calculations is significantly less efficient on the AVR than integer calculation - understanding how to translate a floating point problem into an integer one is a very useful skill!

The divisibility checks broke down something like this for a given integer number:

Divisible by 1 is trivial - everything is divisible by 1.
Divisible by 2, 5 and 10 are pretty easy to check using the rightmost digit.
- If the rightmost digit is even (0, 2, 4, 6, or 8), it's divisible by 2.
- If it's 0, it's divisible by 10.
- If it's 0 or 5, it's divisible by 5.
Divisible by 6 means divisible by both 2 and 3.
Divisible by 4 means divisible by 2 twice - check for 2, if that passes, divide by 2 and check that.

You'll notice that I haven't mentioned the rule for divisibility by three or nine - while the rules above are obvious after you think about them a bit, three is the one that really stuck with me. It's a little more involved, but still quick and intuitive to apply.

Looking at the digits, add each successive digit.
- If the result is a recognizable multiple of 3 (0, 3, 6, 9, etc.), then then the original number is divisible by 3.
- If the sum is divisible by 9 (0 or 9), the original number is divisible by 9.
If the first sum is too long to easily recognize, then you can repeat the process, making a second sum that follows the same rules.

She didn't have a good rule for seven - for all of the shortcuts outlined above, divisibility by seven was still the realm of attempting the division and checking the remainder. Beware of prime numbers!

The divisibility by three thing has been an interesting piece of trivia through the years - in preparing to write this, an informal survey of my colleagues revealed that very few of them knew it, a greater number didn't, and one claimed to avoid shortcuts altogether.

Having some casual familiarity with numbers is useful to scientists and engineers. In software and computer engineering, casual familiarity with binary numbers is particularly useful.

Studying computer science in university, a good portion of my sophomore year was spent studying different number systems. I took an introduction to computer architecture class that was a sink-or-swim trial - we really had to be conversant with binary, octal and hex. I remember exams in that class where the instructor would ask us to show our work in the representation of his choosing. We got to be pretty good at doing simple arithmetic in our heads, but it was a great relief when we were allowed to use calculators to handle base conversion.

Binary numbers are the foundation of computing - it's easy to make circuits that are either on or off, and it's easy to gang those circuits up to increase resolution. Binary also quickly becomes cumbersome - an individual bit (or binary digit) doesn't store much information - by the time we've ganged up a bunch of them, the string of on/off indications is unwieldy. If I have 001100010111000000011100, are there 6 or 7 zeros in a row in the middle?

As shorthand, we gather the bits into groups, and use different number bases to describe the groupings:

Groupings of 3 bits at a time yield values from 0 to 7 - having eight possible codes, we call the result octal, and prefix it with 0c to differentiate it from decimal.
If we make 4-bit groupings, we get 16 possible codes, known as hexadecimal, or hex for short, with the prefix 0x. Since we run out of digits to represent hex values, we pull letters from the start of the alphabet: A, B, C, D, E and F.

In 2015, octal seems anachronistic, and hex has taken over. It's partly a divisibility by three situation: In the age of 32 and 64-bit computers, neither is evenly divisible by 3, though they are divisible by 4. When I was in that architecture class, we were studying the Digital Electronics Corp's PDP-8, which is intrinsically a 12-bit machine - octal and hex were both a part of that landscape.

I'm not really here to get deep into hex - we've got a tutorial that covers it more thoroughly than I can here.

But after years spent thinking (in the shower, while driving my car, riding my bike) about number systems and divisibility by three, I discovered something:

The divisibility-by-three shortcut also works in hexidecimal!

It takes a little bit of adjustment.

You have to remember to use hex math when adding the digits (0x9 + 0x1 = 0xA, not 10!).
You need to put 0xC and 0xF (decimal 12 and 15, repsectively) in the list of recognized multiples of three.

So let's examine how this works:

This may also be another reason to use hex instead of octal - octal doesn't follow the sum-of-digits shortcut!

Time will tell how useful this actually is. Computers are pretty deeply based on powers of two, so division by those numbers is much more easily applied, to such a degree that those numbers are frequently used as design specifications (RAM size is based on powers of 2, for example), where multiples of three are not. Still, it's an interesting piece of trivia. Maybe you'll find it useful sometime, if as nothing more than a geeky party trick.