## Saturday, November 5, 2011

### Divisibility Rules For Powers Of 2

In this earlier post, I wrote about some divisibility rules for various numbers. In that post, I mentioned that it is easy to derive divisibility rules for composite numbers by breaking them down into co-prime products, and then checking divisibility by each of those prime numbers.

One problem that has been bothering me since that time is the problem of finding divisibility rules for powers of 2 (4, 8, 16, 32, etc.). The problem is that these numbers have 2 as their only prime factor. As such, just because a number is divisible by 2 does not make it divisible by all its powers, but there are no other co-prime numbers to check divisibility against, so what do we do?

Many other websites do have a simple divisibility rule for powers of 2: Essentially, a number is divisible by 2^n if the last n digits of the number are divisible by 2^n. Thus the divisibility rule for 4 (which is 2^2) is that the last 2 digits of the number have to be divisible by 4. Seems fair enough for 4, and perhaps even 8.

But for a number to be divisible by 16, the last 4 digits have to be divisible by 16. To be divisible by 32, the last 5 digits have to be divisible by 32. As you can see, the divisibility rule becomes almost as onerous to apply as the actual division of the whole number by 16 or 32. In fact, in many cases, you may be trying to check the divisibility of numbers by 16 or 32 that may not even have 4 or 5 digits! So, the divisibility check does become an actual case of division, and does not save any labor at all.

In that same post, I also came up with a divisibility rule for 16 that seems to be less laborious to apply than checking divisibility of the last 4 digits by 16. The rule seemed seductively simple, luring me into a false sense of correctness. In fact, I am surprised that nobody has pointed out that the rule I have posted is completely wrong!

Yes, completely wrong. The rule is copied below for reference:

... one can also take the sum of the first digit, twice the second digit, 4 times the 3rd digit and 8 times the 4th digits (digits are numbered from the right, not the left), and test this sum for divisibility by 16.

Why is it wrong? Well, it does not even work on the number 16! Applying this rule to the number 16, you get the sum as 8, and therefore 16 should not be divisible by 16. Obviously, there is something wrong with the rule!

The problem is that since the rule was simply an extension of rules that actually work for 2, 4 and 8, it was easy to believe that it would work. And its simplicity makes it all the more appealing, clouding your judgment. It would have been easy for me to check to make sure it actually works, but I did not.

So, we have to derive another simple divisibility rule for 16. Note that 10000 is divisible by 16, so any rule we come up with has to depend on the last 4 digits, but no other part of the number (the other parts of the number only add 10000's to the number and since 10000 is divisible by 16, they do not affect the divisibility of the number by 16). Similarly, the divisibility rule for 32 has to depend on the last 5 digits, but no other part of the number. You get the idea.

So, to recap, the following rules do work:

Divisibility rule for 2: If the last digit is divisible by 2, the entire number is divisible by 2.

Divisibility rule for 4: (a) If the last 2 digits are divisible by 4, the entire number is divisible by 4. (b) Alternatively, if the last digit + twice the digit before that is divisible by 4, the entire number is divisible by 4.

Divisibility rule for 8: (a) If the last 3 digits are divisible by 4, the entire number is divisible by 8. (b) The second rule is similar to that used for 4 also. We take the sum of three numbers: the first number is the last digit itself. The second number is twice the next-to-last digit. The third number is 4 times the digit 3rd from the end. If this sum is divisible by 8, then the entire number is divisible by 8.

(c) In addition, 8 has another divisibility rule also. Split up the last 3 digits into two chunks, the first chunk with the last 2 digits of the number and the second chunk with the 3rd digit from the end. Now, add the first chunk to 4 times the second chunk, and if the sum is divisible by 8, then the whole number is divisible by 8.

That last rule came out of lots of experimentation, and forms the basis for derivation of rules for higher powers of 2. Let us apply it on 368, for instance. We split up the last 3 digits into two chunks. The first chunk would be 68 and the second chunk would be 3. We then add 4*3 to 68 to get 80. Since 80 is divisible by 8, we conclude that 368 is divisible by 8.

So far, I have not found any counterexamples for these rules, so they seem to hold up to real-world anecdotal testing.

As mentioned earlier, the simple extension of the second divisibility rule for 8 does not work on 16. Why? I have no idea. It seems to be a matter of the rule failing when you go from checking divisibility by a single digit number (8) to a 2-digit number (16).

However, the extension of the 3rd rule for divisibility by 8 does work for 16. In addition, I seem to have stumbled upon a general rule for checking divisibility by using chunks of digits (chunks of 2 digits, 3 digits, etc.).

Thus, the rules for divisibility by 16 are as below:

Divisibility rule for 16: (a) If the last 4 digits of a number are divisible by 16, the entire number is. (b) Alternatively, divide the last 4 digits of the number into 2 chunks of 2 digits each. Add the first chunk (the last 2 digits) to 4 times the second chunk (the previous 2 digits). If this sum is divisible by 16, then the whole number is divisible by 16. (c) In addition, there is a third rule. Divide the last 4 digits into one 3-digit chunk (the last 3 digits), and one 1-digit chunk (the 4th digit from the end). Add the first chunk and 8 times the second chunk. If that sum is divisible by 16, the entire number is divisible by 16.

Let us apply these on some numbers to see if they work. Take 16 for instance. Applying either the second or third rule above is trivial (in both cases, the first chunk is 16 or 016, and the second chunk is 00 or 0, so their sum gives us 16, which is obviously divisible by 16). For something more challenging, let us try it on 560, instance. The two chunks for rule number 2 are 60 and 05. Adding 60 to 4*5 gives us 80, which is divisible by 16, so 560 is divisible by 16.

Now, let us try it on a 4-digit number. Take 3888 for instance. The two chunks are 88 and 38. 88 + 4*38 = 240. Applying the rule once again, gives us 40 + 4*2 = 48. We know 48 is divisible by 16, so we conclude that 3888 is divisible by 16.

Applying the third rule to 3888 gives us two chunks, 888 and 3. 888 + 8*3 = 912. At this point, we can apply the second rule to get 12 + 9*4 = 48, which is divisible by 16. Thus, we can conclude that 3888 is divisible by 16 using the third rule also.

Now, let us move on to 32. Obviously, it is true that if the last 5 digits are divisible by 32, the entire number is (because 100,000 is divisible by 32). Some simpler rules can be derived using the work we have done for 8 and 16. In fact, by extending the rules for 8 and 16 to 32, we can derive 4 different divisibility rules for 32. Here they are:

Divisibility rule for 32: (a) If the last 5 digits are divisible by 32, the entire number is divisible by 32. (b) Divide the last 5 digits of the number into 3 chunks of 2 digits, 2 digits and 1 digit (the last 2 digits, the previous 2 digits, and the 5th digit from the end). If the last chunk + 4 times the next chunk + 16 times the third chunk is divisible by 32, then the entire number is. (c) Divide the last 5 digits into two chunks, the first containing the last 3 digits of the number, and the second containing the 2 digits prior to that. If the first chunk + 8 times the second chunk is divisible by 32, then the entire number is. (d) This rule is a logical extension of the previous 2 rules: Divide the last 5 digits into two chunks, the first with the last 4 digits of the number, and the second with the 5th digit from the end. If the sum of the first chunk and 16 times the second chunk is divisible by 16, the entire number is.

Let us try these rules out on a sample number. Let us take 37024. For the second rule, the 3 chunks are 24, 70 and 3. We take 24 + 4*70 + 16*3. We find that the sum is 352. Reapplying the rule, we get 52 + 3*4 = 64. We know 64 is divisible by 32, so we conclude that 37024 is divisible by 32.

For the third rule, our chunks are 024 and 37. 24 + 8*37 = 320. Obviously, 320 is divisible by 32, so once again the third rule also gives us the same divisibility signal.

For the fourth rule, our chunks are 7024 and 3. 7024 + 16*3 is 7072. At this point, we can switch to either the second or third rules to continue checking for divisibility. Using the second rule, our chunks are 72, 70 and 0. 72 + 4*70 = 352. We know that 352 is divisible by 32, so the fourth rule also confirms divisibility by 32.

OK, so by now, the pattern for deriving divisibility rules for powers of 2 seems to be clear. First identify the last n digits of the number, where n is the power of 2 for which divisibility is to be checked. Divide these last n digits into chunks of at least m digits where m is the number of digits in the power of 2 for which we are checking divisibility (so we can use 1-digit chunks for 2, 4 and 8, but must switch to at least 2-digit chunks for 16, 32 and 64, and 3-digit chunks for 128, and so on). The last chunk (farthest from the end of the number) may contain less than m digits (do not include any digits in the last chunk that are outside the last n digits of the number).

Now, multiply the first chunk (last m digits) by 1. Multiply the next chunk by 2^m. So, 2^m is the second multiplier. Multiply the chunk after that by (2^m)^2. (2^m)^2 is the third multiplier. In general, keep squaring the previous multiplier to get the next multiplier after you get the second one. If the sum of all this is divisible by 2^n, then the whole number is divisible by 2^n. Simple, isn't it?

OK, so some of the above is correct, and some of it is not. The verification of the correctness of some of the rules presented here, as well as derivation of new rules is very simple using modulo arithmetic. I discovered this about a week after this post went up, and you can read about my discoveries in this later post.

I will leave the derivation of divisibility rules for 64 (and 128 and other higher powers) to the reader. I will also leave the thorough verification of these rules to make sure there are no rule-breakers out there, to the readers. I like to think of this as crowd-sourced testing and debugging! So, try these rules out on various numbers, and see whether any of these rules fail. Remember that counterexamples can be false negatives (a number is actually divisible, but the rule says it is not) or false positives (a number is not divisible, but the rule says it is). Well, get cracking, and good luck!

#### 1 comment:

HealthTips said...

Hello, thank you for sharing this powers of 2 knowledge for all, it can help me think out of more, so if you want to learn more on it easy step check for more what's powers of 2 learning here.

## Content From TheFreeDictionary.com

In the News

Article of the Day

This Day in History

Today's Birthday

Quote of the Day

Word of the Day

Match Up
 Match each word in the left column with its synonym on the right. When finished, click Answer to see the results. Good luck!

Hangman

Spelling Bee
difficulty level:
score: -