## Saturday, November 26, 2011

### Practice Makes Perfect

Last week I wrote about how I learned how to solve the Rubik's Cube, and how I have been able to solve the cube in between 5 and 10 minutes. Well, I have been practicing more and more, and this has made it easier for me to solve the cube because the procedures have become more and more memorized. In addition, my times have improved considerably also.

After all the practice of the past week, my average time has come down to about three and a half to five minutes. My personal best time is two minutes and 53 seconds. Interestingly, my daughter has also improved considerably, and in fact, her personal best time is two minutes and 33 seconds! Her average is no better than mine, but she got lucky once, and has a better personal best time than I have. I am wearing the cube and my fingers out trying to beat the record and take the title back from her!

I was actually wrong last week about the world record being 29 seconds. It turns out that the world record for solving the 3x3 cube is 5.66 seconds! That is less than the time it takes me to put together even a couple of cubes on the top side of my scrambled cube!! Oh well, the world record is quite safe from me as of now.

Anyways, I had posted a puzzle last week that illustrates isolation. As promised, here is the solution to that puzzle. The way to think about this is as follows: any cell in the table which is flipped an odd number of times changes from a 0 to a 1 or vice versa. Any cell which is flipped an even number of times remains what it was (a 0 remains a 0 and a 1 remains a 1). So, the idea is to flip every cell in the table zero or an even number of times, and flip just the cell (3,3) an odd number of times.

After some thought, you will realize that one way to accomplish this is to flip every cell in the row and column in which (3,3) is located exactly once. That way, cell (3,3) is flipped 7 times (an odd number of times), every other cell in row 3 and column 3 of the table is flipped 4 times (an even number of times), and all other cells in the table are flipped 2 times (an even number of times).

The sequence of flips is shown below. The original table is as below:

 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1

We start by flipping each element in column 3 first. After cell (1,3) is flipped, the table is as below (remember that every cell in the row and column in which the flipped element is present is also flipped):

 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1

Now we flip cell (2,3) to get the table below:

 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1

Now it is the turn of cell (3,3) to get flipped:

 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1

We move on to cell (4,3):

 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0

Now, we flip each element in the third row of the table. This is the state after flipping cell (3,1):

 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0

Now, we flip cell (3,2):

 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0

And finally, we move on to cell (3,4). Remember not to flip (3,3) twice. We flip each element in the third row and third column of the table exactly once:

 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1

Now, compare this last table to the first table. You will see that all the cells are exactly the same except for cell (3,3) which has been flipped from a 1 to a 0. Which was precisely the objective of the puzzle!

Can you find a shorter sequence of steps to accomplish the above transformation? I would love to hear it if you manage this in fewer steps. In a 4x4 table, this transformation took 7 steps. In a 2n x 2n table, this transformation takes 4n - 1 steps, which gets tedious for larger tables.

The more interesting challenge is to try to accomplish this in a square table with an odd number of elements per side (for example, in a 3x3 or 5x5 table). I have not been able to find any sequence of steps that will flip just one cell in such a table (obviously, it is trivial in a 1x1 table, but I am talking about tables that are true tables rather than a single element). If you come up with a set of steps to flip a single element in such a table, I would be very interested in hearing about it. Post your solution, if you find one, in the comments below.

In fact, the procedure above works for non-square tables also. The only condition is that each side of the table should have an even number of elements. So, the method would work perfectly fine on 4x10 tables, 14x40 tables, and so on. But if one or both sides have an odd number of elements, the procedure fails. So, it is no good on 5x3 tables, 15x30 tables and so on. It would be really good if a solution existed for odd-sided square tables, and the procedure could be extended to non-square tables without much additional thought. Good luck!

Obviously, there are similarities between this puzzle and what happens in a Rubik's Cube (when you try to change the position of one small cube, a whole layer of cubes moves), but also differences (it is not as simple as changing a 0 to a 1 or vice versa). The trick is to figure out isolation sequences for the cube which accomplish the changes you want while avoiding changes you don't want. The mathematics of it are interesting, but also quite challenging. I am just starting to read up on it. I will keep you posted as to how it goes.

## Saturday, November 19, 2011

### The Conquest Of The Rubik's Cube

My daughter goes to school in a school bus. One day, she came back from school and told me that another student on her bus works on a Rubik's cube on the bus. She watches him solve the cube quite often, and her interest was piqued enough that she wanted to play around with a Rubik's cube herself.

So, I took her to a store and got her a new Rubik's cube. I also sat with her and taught her the general principles behind solving one side of the cube. I taught her how to move individual cubes out of the way, bring down a layer, slot the moved cube back into the layer, and then move the layer back to its original position. I also taught her how to get cubes out of the bottom layer or cubes which were stuck on the sides of the top layer (assuming she was trying to solve the top side). My daughter caught on quite quickly, and could solve one side of the cube without any problems. And then started asking me how to solve the whole cube.

The Rubik's cube first came out when I was in school, and all I ever did was learn how to solve one side of it. When I went to college, one of my friends knew how to solve all 6 sides of the cube. I sat with him a few times, and documented the procedure for solving all 6 sides in a notebook (remember, this was before the days of the internet, so I couldn't just Google for the solution technique at that time).

The procedure seemed complicated enough that I never really solved the cube properly using the procedure. I certainly could not memorize the procedure and all the variations and exceptions. After a while, I did not even have access to a cube anymore, and my experimentation with it was long-forgotten. And then I lost the notebook itself, and the cube was a challenge that went unconquered.

Now that I had access to a Rubik's cube once more, my curiosity was re-ignited. The cube came packaged with a solution technique that used simple pictures and a very understandable notation for describing which layers of the cube to turn in what directions. I was actually able to follow the directions and actually solve the cube after the first few attempts (the first couple of times I tried it, I misunderstood one of the steps, and kept messing up the cube). After those first few attempts, I took the time to memorize the directions using some simple mnemonics. And now, I can solve a fully scrambled Rubik's cube without referring to any directions or instructions at all. This set of instructions is not optimized, and so you have to use the same set of instructions multiple times to accomplish different steps in the solution process. I am sure there are better instructions out there that are optimized for the specific arrangement of cubes you find yourself facing. But, those instructions are probably more complicated and require more memorization.

In any case, from a fully scrambled state, I can get to a fully solved state in between 5 minutes and 10 minutes. I started out taking just over 10 minutes, but as I have become more familiar with the instructions and how to identify patterns in the arrangement of the cubes, I have improved somewhat. Obviously, I am not setting any records here. It seems more like magic than talent when I hear that the record for solving a cube fully is 29 seconds! 29 seconds!! I can't even solve one side of a cube in 29 seconds if my life depended on it!!!

I can solve one side in about 30 seconds to a minute if I didn't care about the sides. If I wanted to get the first layer of the sides solved along with the top side, then it takes me 90 seconds to 3 minutes. But, I don't really care. The Rubik's cube is one of those timeless puzzles that has fascinated me since my school days. To be able to solve one in less than 10 minutes seems like such an accomplishment that I am tickled pink by it!

When I initially played with a Rubik's cube, I never believed it possible that I would ever be capable of solving it fully without referring to instructions step by step. To be able to now solve it without any help from anybody or anything feels as if I have accomplished something that I could only dream of before. It is like getting a black belt in cube-solving! I can even solve the cube while carrying on a conversation with somebody else.

My conquest of the cube was inspired by my daughter's curiosity. She is still at a point in my life when she considers me smart enough to do anything I want in life. So, I could hardly let her down when she started asking me to teach her how to solve the cube fully. After becoming familiar with the instructions, I started teaching her how to do it.

The first few times, I helped her by reciting the instructions I had memorized at each step as she turned the cube and solved it. After hearing me repeat the instructions several times, they started becoming embedded in her brain, and pretty soon, she could repeat the instructions herself without any help from me. Now, she can also solve the cube in about 5 to 10 minutes without any external help.

I am now trying to get my other daughter to take up the cube as a challenge. She can solve one side right now in about 5 minutes, and solving the top with the first layers of the sides takes her longer. But, I am confident that she will eventually get interested enough to get beyond that to the full solution. I am working at keeping her interest level up so that she does not give it up in the initial stages. That is when things always seem way too hard, and the end result does not seem worth the trouble. We will see how it goes.

Most of the steps in solving the cube are related to isolating different parts of the cube and doing a set of twists and turns that rearranges cubes in a part of the cube without affecting other parts of the cube. I refer to this as isolation. You have to understand isolation and how to accomplish it to be able to go beyond memorizing instructions to solve the cube. If you want to come up with your own solution techniques, you have to figure out how to isolate parts of a cube so that you can rearrange cubes to the required positions while not destroying the arrangement of cubes in other parts of the cube.

To illustrate isolation, I gave my kids a puzzle that you might also find interesting. Take a 4x4 grid of 1's and 0's as below. It doesn't matter where the 1's and 0's are. The important thing is to start with this grid, and do a set of "manipulations" that result in a grid that has just one of those numbers changed from a 0 to a 1 or vice versa. So, consider the two grids below, for instance:

 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1

 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1

The second one is just the first one with the 1 in position (3,3) changed to a 0 (I have bolded the elements to show you what has changed). All the other elements are the same. Now, the rules of manipulations are very simple. You can flip any number in the grid from a 0 to 1 or vice versa. When you flip any element in the grid, all the elements in the grid in that row and column also flip (0's change to 1's and 1's change to 0's).

That is all there is to it. Using this rule, come up with a set of manipulations (flips) that change just the element in (3,3) from a 1 to a 0. That is what isolation is all about (though I would daresay, the isolations in a Rubik's cube are a lot more complicated and require a lot more spatial orientation skills). I will provide the solution to this simple puzzle next week. Good luck!

## Saturday, November 12, 2011

### Divisibility Rules For Powers Of 2 Redux

In my previous post, I had come up with some simple divisibility rules for 16 and 32 (at least, simpler than simply checking divisibility by doing actual division on the last 4 or 5 digits of the number we need to check for divisibility). The rules involved splitting the last few digits of the number into chunks of various lengths, multiplying the chunks by different powers of 2, and then adding these parts up and checking the sum for divisibility by the powers of 2.

In that post, I also mentioned that I had not verified the correctness of these derived rules for divisibility because I was not a theoretical mathematician or number theorist. It turns out you don’t need to be either of those to come up with proofs of correctness (or incorrectness) of these rules, and also to derive new ones. The secret lies in modulo arithmetic, which I introduced in this earlier lesson during a discussion of how and why osculation works in deriving divisibility tests. I also used those principles to derive a new divisibility rule for 7 that involved subtracting the number formed by the last 3 digits of the number from the rest of the number, and then checking to see if this is divisible by 7.

We can use the exact same principles to prove the divisibility rules for the powers of 2 that I published in the previous post, and also to derive new rules for these numbers.

First of all, let us get some basics out of the way. Any number with n+1 digits (say a) can be expressed as below:

10n*dn + 10n-1*dn-1 + . . . + 103*d3 + 102*d2 + 10d1 + d0

Now, we also know that divisibility of a number by 2m implies that a mod 2m = 0. Expanding out a, we can then say that:

(10n*dn + 10n-1*dn-1 + . . . + 103*d3 + 102*d2 + 10d1 + d0 ) mod 2m = 0

Knowing that 10m and higher powers of 10 are multiples of 2m, we can keep the modulo arithmetic intact by subtracting out these higher powers of 10. After the subtraction, all we are left with would be an (m-digit number) mod 2m = 0. This is the basis for saying that we only need to concern ourselves with the last m digits of a number when checking divisibility by 2m. Going forward, we will not even bother writing out the rest of the number to be checked for divisibility. We will only worry about the last m digits when proving or deriving divisibility rules for 2m.

Let us also not worry about 2 to begin with. The divisibility rule for 2 is trivial, and needs no proving. Simply, since 10 and higher powers of 2 are multiples of 2 anyways, the entire modulo equation becomes simply x mod 2 = 0 implies divisibility by 2, where x is the last digit of the number.

Let us move on to 4. We know that 100 and higher powers of 10 are multiples of 4. So, for some number to be divisible by 4, we simply have to make sure that (10x + y) mod 4 = 0, where y is the last digit, and x is the last but one digit. In fact, this is the first divisibility rule for 4: the number formed by the last 2 digits has to be divisible by 4 for the entire number to be divisible by 4. But let us examine further.

(10x + y) mod 4 = 0 implies

(2x + y) mod 4 = 0, and also

(-2x + y) mod 4 = 0, and also

(2x – y) mod 4 = 0

The second line comes about because we subtracted 8x from (10x + y). We know this is valid because 8x is a multiple of 4. Similarly, we can get the third line by subtracting 12x from (10x + y). The fourth line is simply flipping the sign on the third line. Notice also that the second line is, in fact, the second rule for divisibility by 4. The third and fourth lines are in fact, brand-new rules for divisibility by 4 which I have not mentioned before.

Now, obviously, instead of subtracting 8x from (10x + y), I can choose to add 96x to (10x + y). After all 96x is a multiple of 4, so it is perfectly valid. But the resulting rule becomes more difficult to apply than the rule it was derived from (verifying that (106x + y) is divisible by 4 is a lot harder than verifying that (10x + y) is divisible by 4). Our goal should be to reduce the coefficients next to x and y as much as possible to make the arithmetic as easy as possible. 2 and –2 are the closest we are going to be able to get to zero from 10 by subtracting multiples of 4 from it, so we are better off stopping with the rules we have gotten above.

Also, (10x + y) mod 4 = 0 implies

(30x + 3y) mod 4 = 0 (I can multiply by 3 and the implication works in both directions because 3 and 4 are co-prime), which implies

(-2x + 3y) mod 4 = 0, and also

(2x – 3y) mod 4 = 0.

In the above cases, I subtracted 32x from (30x + 3y) since 32x is a multiple of 4. You can derive an infinite number of divisibility rules based on the rules of modulo arithmetic, and I think the above derivations show some of the possibilities. You are limited only by your imagination!

The rules above can be expressed in the form of a table as below. In this table, the column headings denote the digits in the various places. The coefficients by which these digits have to be multiplied are the elements of the table. The sum of these products is then checked for divisibility by 4 to verify the divisibility of the entire given number by 4. When the number under the “tens digit” column is 10, and the number under the “ones digit” is 1, this means that the 2-digit number formed by the two digits can be treated as a single chunk, multiplied by 1. Here are the 6 rules for divisibility by 4 in this notation.

Divisibility Rules for 4:

 Rule Number Tens Digit Ones Digit 1 10 1 2 2 1 3 -2 1 4 2 -1 5 -2 3 6 2 -3

To apply rule number 4, for instance, simply take twice the last but one digit and subtract the last digit from it. If the total obtained after this is divisible by 4, the entire number is divisible by 4.

Now that we know the basics of how to use modulo arithmetic to derive divisibility rules, applying the rules to 8 should be quite simple. First of all, 1000 and higher powers of 10 are multiples of 8, so we only have to deal with the last 3 digits of the number, which can be expressed as (100x + 10y + z). Without further ado, let us go about deriving some divisibility rules based on modulo arithmetic:

(100x + 10y + z) mod 8 = 0 implies

(4x + 10y + z) mod 8 = 0 (subtract 96x which is a multiple of 8), which implies

(4x + 2y + z) mod 8 = 0 (subtract 96x + 8y, which is a multiple of 8). Also,

(-4x + 10y + z) mod 8 = 0, which implies

(4x – 10y – z) mod 8 = 0. Also,

(-4x –2y + z) mod 8 = 0, which implies

(4x + 2y – z) mod 8 = 0. Also,

(300x + 30y + 3z) mod 8 = 0, which implies

(4x – 2y + 3z) mod 8 = 0, and also

(-4x –2y + 3z) mod 8 = 0, and

(4x + 2y – 3z) mod 8 = 0.

As you can see, the number of divisibility rules we can get is practically limitless. Here is a table with just a few of them:

Divisibility rules for 8:

 Rule Number 100s Digit Tens Digit Ones Digit 1 100 10 1 2 4 10 1 3 4 2 1 4 -4 10 1 5 -4 2 1 6 4 -2 -1 7 4 -6 1 8 4 -2 3 9 -4 -2 3 10 4 2 -3

If you continue this exercise for 16, 32, 64, etc., you will see that the generalized rule I came up with for using multi-digit chunks of a number to check for divisibility in this earlier post are wrong. Those rules were arrived at by intuition rather than rigorous mathematical analysis, and I am not surprised that some of them turned out to be wrong. Intuition is valuable in mathematics and science, but it should be backed by solid analysis and verification.

The number of divisibility rules goes up exponentially as the number for which divisibility is being checked goes up. So, I am not going to make any attempt to list them all in the tables below. I am just going to show you a representative few, including the rules I did come up with for 16 and 32 that are actually correct. So, here goes:

Divisibility rules for 16:

 Rule Number 1,000s Digit 100s Digit Tens Digit Ones Digit 1 1000 100 10 1 2 8 100 10 1 3 8 4 10 1 4 40 4 10 1 5 8 4 -6 1 6 -8 4 -6 1 7 8 -4 6 -1 8 -8 4 10 1 9 8 -4 -10 -1 10 8 12 -2 3 11 -8 -4 -2 3 12 8 4 2 -3

You may be able to recognize some of the rules from the previous post in the table above. For instance, rule 4 above is the second rule from the previous post. Rule 2 is the third rule from the previous post.

Divisibility rules for 32:

 Rule Number 10,000s Digit 1,000s Digit 100s Digit Tens Digit Ones Digit 1 10000 1000 100 10 1 2 16 1000 100 10 1 3 16 8 100 10 1 4 16 8 4 10 1 5 16 40 4 10 1 6 -16 8 4 10 1 7 16 8 4 -22 1 8 -16 -24 -28 -22 1 9 16 24 28 22 -1 10 80 8 100 10 1 11 16 -8 12 -2 3 12 -16 8 -12 2 -3

The second rule from the previous post is rule number 5 in the table above. The third rule from the previous post is rule 10 above. And fourth rule from the previous post is rule number 2 in the table above.

I will leave you with a few divisibility rules for 64. You will notice that the general rules I postulated in my previous post for deriving divisibility rules for powers of 2 actually do not work with 64. That is one of the problems with trying to come up with or identify and extend patterns when you don't understand the underlying principles that result in the given pattern. I did not know what I was doing last week, and modulo arithmetic has enlightened me!

Divisibility rules for 64:

 Rule Number 100,000s Digit 10,000s Digit 1,000s Digit 100s Digit Tens Digit Ones Digit 1 100000 10000 1000 100 10 1 2 32 10000 1000 100 10 1 3 32 16 40 36 10 1 4 32 16 -24 -28 10 1 5 -32 16 -24 -28 10 1 6 32 -16 24 28 -10 -1

I will leave the derivation of divisibility rules for 128 and other higher powers of 2 to the readers (though I doubt you will encounter the need to check divisibility by such large numbers).

This was a lot of fun for me, and I hope you had fun reading this post. It is amazing how much you can discover in mathematics by using simple principles and applying them logically. The derivation of divisibility rules from modulo arithmetic is one such endeavor, where one of the most basic mathematical principles gives us such powerful results. I hope I have not made any arithmetic errors in this post. If I have, please do let me know. Good luck!

## 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!

## 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: -