Going back through my Leapfrog Division and Leapfrog Division II posts, it put me in mind of divisibility tests. If you don't remember, those are simply ways of checking whether a given number is evenly divisible by another number.

In school, they often teach simple rules for quickly identifying 2, 3, 4, 5, 6, 8, 9, and 10. 7 is usually skipped because it's a prime number, and the tests are more difficult to teach.

It turns out, however, that by using the quotient and remainder and neighboring numbers, similar to the way we used them in the Leapfrog Division posts, many prime numbers become much easier to test!

The use of neighboring numbers divisible by 10 makes these rules surprisingly easy to recall and use. Instead of starting with 9, which already has its own simple divisibility test, I'll start with 19. Very few people know how to test for divisibility by 19.

DIVISIBILITY BY 19: The trick is to divide a given number by 20 (19 + 1), so that you get a quotient and remainder. If the quotient and remainder add up to a multiple of 19, then the original number is divisible by 19!

For example, let's test whether 437 is evenly divisible by 19. 437 ÷ 20 = 21, with a remainder of 17. 21 + 17 = 38, and since 38 is a multiple of 19, we know that 437 must be a multiple of 19, too! If you're wondering, 437 = 19 × 23.

Why does using a neighboring number work for divisibility tests? Think of it this way: We're given an integer (whole number) x and we want to test whether it's evenly divisible by n, so we divide by another integer n + 1, to get 2 more integers, a quotient, q, and a remainder, r. Thus, the problems boil down to this format:

^x⁄_{(n + 1)} = q + r

To simplify the equation, we multiply both sides by (n + 1) to get:

x = (n + 1)(q + r)

Expanding the right side results in this:

x = nq + nr + q + r

Since every variable here represents an integer, we know that nq, nr, as well as the sum of nq and nr must all be evenly divisible by n. Therefore, if q + r equals a multiple of n, then x must be evenly divisible by n, as well! Conversely, if q + r doesn't equal a multiple of n, then x won't be evenly divisible by n.

GENERALIZING DIVISIBILITY TESTS: Since our only assumption in the above equations is that we're using integers, and that there's an easily divisible number, such as a multiple of 10, 1 greater than the number for which we're testing, this test works well for any number ending in 9, as long as you're comfortable dividing by the following multiple of 10!

So, to test for divisibility by 29, you could divide by 30, and add the resulting quotient and remainder. Is 377 evenly divisible by 29? Let's try: 377 ÷ 30 = 12 remainder 17, and 12 + 17 = 29, so 377 is definitely divisible by 29! How about 523? 523 ÷ 30 = 17 remainder 13, and 17 + 13 = 30, so 523 is not evenly divisible by 29.

HOW CLOSE ARE WE TO A MULTIPLE?: The 523 example does give us 30, which is only 1 more than 29. Does this mean that 523 is 1 greater than a multiple of 29? Let's test out 522 and find out. 522 ÷ 30 is 17 remainder 12, and 17 + 12 = 29, so 522 must be evenly divisible by 29! In fact, 522 = 29 × 18.

As long as you know your first few multiples of the number n for which you're testing, you can often use this test to see how close you are to a perfect multiple of n.

For our next example, let's test 1,418 for divisibility by 19. 1,418 ÷ 20 = 70 remainder 18, and 70 + 18 = 88. 88 isn't a multiple of 19, so 1,418 isn't evenly divisible by 19.

However, you should realize that 19 does have two multiples close to 88, which are 76 and 95. So, you could subtract 12 (76 - 88) or add 7 (95 - 88) to get to a multiple of 19! This quickly tells us that 1,406 (1,418 - 12) and 1,425 (1,418 + 7) are perfect multiples of 19.

HANDLING BIG RESULTS: What happens if you get a result that is so big that you're not familiar with whether the result is a multiple? For example, is 31,842 evenly divisible by 29? Let's run it through our test and find out.

31,842 ÷ 30 = 1,061 remainder 12, and 1,061 + 12 = 1,073. As long as 1,073 is evenly divisible by 29, then 31,842 is evenly divisible by 29. There's the problem: Is 1,073 evenly divisible by 29? We can run the test again to find out.

1,073 ÷ 30 = 35 remainder 23, and 35 + 23 = 58. Yes, 58 is easily recognizable as a multiple of 29, so we now know that 31,842 is evenly divisible by 29!

One of the best parts about testing again and again in this way is that it preserves the same remainder throughout the repeated tests. So, if I'd tested 31,845 instead (3 more than 31,842), it would result in 1,076 (3 more than 1,073) in the first test, and 61 in the second test (3 more than 58). So, even with repeated tests, I can still determine how close a given number is to a perfect multiple!

TESTING NUMBERS NOT ENDING IN 9: Having just talked about the importance of knowing the first few multiples, you'd probably think it's unusual if I wanted to test, say, the number 91 for divisibility by 39. After all, just counting 39...78...117, we can already see that 91 isn't a multiple of 39. Let's run through the test anyway.

For 39, we'll divide by 40 and look at the quotient and remainder. 91 ÷ 40 = 2 remainder 11, and 2 + 11 = 13. Since 13 isn't a multiple of 39, we verified that 91 isn't a perfect multiple of 39, just like we expected. We can also say that 91 is 13 more than a multiple of 39, as discussed in the previous section.

But wait a minute, 13 may not be a multiple of 39, but 39 is a multiple of 13! If 91 is 13 beyond a multiple of 39, it must also be 13 beyond a multiple of 13! In other words, we can use our test for 39 not only for 39, but for divisibility by 13, as well!

When testing for divisibility by any number n with this approach, you can also use it as a test for factors of n! We could also use this approach to test for divisibility by 3, since 3 is a factor of 39, but 3 already has a much easier divisibility test, so this is overkill.

As I mentioned earlier, teachers often skip teaching divisibility by 7, but you should already see how to test for divisibility by 7 with this method. Since 7 is a factor of 49, we can divide by 50 (49 + 1) to test for division by 7!

Is 1,585 evenly divisible by 7? Checking, we see that 1,585 ÷ 50 = 31 remainder 35, and 31 + 35 = 66. You should know your multiples of 7 well enough to recognize that 66 isn't a multiple of 7, so 1,585 isn't evenly divisible by 7.

We also know, of course, that 66 is only 3 more than a multiple of 7, so 1,585 must be 3 more than a multiple of 7, too!

FINAL THOUGHTS: Think about the power of this style of divisibility testing:

• You can quickly recall the test for divisibility of any number ending in 9.
• You can use this test to find how close you are to a perfect multiple.
• If you're not sure of your results, you can repeat the test and still know how close you are to a perfect multiple.
• You can test for almost any odd number, by scaling it up so it ends in 9.

A little over a year ago, I wrote up my Leapfrog Division post. It's about time for a modification!

The original technique showed you how to work out the decimal equivalent for fractions whose denominators end in 9. In today's post, you'll learn a similar technique for denominators ending in 1.

Before learning this technique, you do want to be very comfortable working with the original Leapfrog Division technique, as it has all the basics of this modified version.

In that post, we worked out ¹³⁄₁₉, so I thought it might keep things simple if we used ¹³⁄₂₁ for our first example this time around. Just like before, we're going to use 20 as a base to divide, and minimize it to the number 2 (simply by dropping the 0), but there are a few changes.

Before any dividing, the next step this time is to take the numerator and subtract 1. So, we've taken ¹³⁄₂₁, converted it to ¹³⁄₂₀, dropped the zero to get ¹³⁄₂. Subtracting 1 from the numerator at this point gives us ¹²⁄₂ as our starting point.

Do this calculation in your head so that you get a quotient and a remainder, just as in the original technique: 12 ÷ 2 = 6 (remainder 0)

Just as in the original, you're going to have the remainder “leap in front of” the quotient, but here's where the new extra step comes in. Before the “leaping” is done, you're going to subtract the quotient from 9, then put the remainder in front of that new result.

With our 6 (remainder 0) example, we'd work out 9 - 6 (the quotient) = 3, and then put the remainder of 0 in front of that to get 03. You keep repeating the steps in this manner as far as you wish. Starting from the ¹²⁄₂ step:

• 12 ÷ 2 = 6 (remainder 0)
• 03 ÷ 2 = 1 (remainder 1)
• 18 ÷ 2 = 9 (remainder 0)
• 00 ÷ 2 = 0 (remainder 0)
• 09 ÷ 2 = 4 (remainder 1)
• 15 ÷ 2 = 7 (remainder 1)
• 12 ÷ 2 = 6 (remainder 0)
• 03 ÷ 2 = 1 (remainder 1)

Scam School has been scammed! Somebody slipped Brain Brushwood some counterfeit coins, and he needs your help to separate the counterfeit coins from the real ones.

OK, this is really just the start of a puzzle, but it's a rather fascinating puzzle. Just when you think you've got the hang of the puzzle, another version can come along and make things tougher.

We'll start by jumping right in to the counterfeit coin puzzles as presented on this week's Scam School (alternative YouTube link):



All in all, not a bad pair of puzzles. For the second puzzle, I would make sure to keep the weighed coins in separate piles, of course, so I can make sure to round up all of the counterfeit coins.

Let's add a new dimension to that second puzzle, just to challenge your thinking. What if, instead of 1 bag holding all counterfeit coins, there were an unknown number of bags? As in the original puzzle, each bag holds either all real coins, each weighing exactly 1 gram, or all counterfeit coins, each weighing 1.1 grams. You still have only one weighing to find out which bags, if any, contain counterfeit coins.

If you want to try and work this out for yourself, stop reading here, as I discuss the solution below.

.

.

.

.

.

.

.

If you think about it, what you really need is a series of yes-or-no answers for each bag in a way that allows you to get this information in a single weighing. How do you achieve this?

Our old friend the binary number system comes to the rescue! If you need a quick understanding of binary numbers, watch Binary Numbers in 60 Seconds.

The solution is take 1 coin (2⁰) out of the first bag, 2 coins (2¹) out of the second bag, 4 coins (2²) out of the third bag, and so on. For each bag, you double the number of coins taken from the previous bag, all the way up to 512 (2⁹) coins taken from the 10th bag.

You'll probably note that it's easier to denote the bags as 0 through 9, instead of 1 through 10. With the bags numbered 0 through 9, we can just remember that we take 2^x coins out of bag number x.

How does taking coins out in powers of 2 help? First, consider the weight we'd get if all the coins were real. We'd have 1,023 coins weighing a total of 1,023 grams. Any weight over 1,023 grams, then, can be attributed to the counterfeit coins.

Let's say we try this out, and find that we have a total weight of 1,044.7 grams. Take away the weight of the real coins, and we're left with 21.7 grams extra. At 0.1 grams extra for each of the counterfeit coins, we now know there are 217 counterfeit coins among the 1,023 coins.

That's great, you might say, but we still don't know which bags are counterfeit. If you stop and think for a minute, you may have more information than you think. First, since you took 512 (2⁹) coins out of bag 9, the coins in that bag couldn't be counterfeit. If they were, you'd have a minimum of 512 counterfeit coins in the total.

The same argument could be made for bag 8, from which you removed 256 coins (2⁸). Still, isn't it difficult to work out all the possibilities for the remaining bags?

No, and I can explain why in a very simple way. In our everyday decimal system, how many ways are there to write the number 217? There's only one way, of course, and that's by writing a 2 in the hundreds place, a 1 in the tens place, and 7 in the ones place. The same is true for any other base, include base 2 (binary).

There's only one way to write the binary equivalent of the decimal number 217. To find out what it is, you can either do a binary conversion with the help of a tool such as Wolfram|Alpha, or, if you've been reading Grey Matters long enough, do the conversion in your head.

Done either way, the binary equivalent of 217 is 11011001, but what does this tell us? Each of these numbers represents one of the bags. To be fair and include all 10 bags, we should write it as a 10-digit binary number, 0011011001, and arrange each number under its corresponding bag like this:

9 8 7 6 5 4 3 2 1 0
0 0 1 1 0 1 1 0 0 1

As a follow-up to last week's tutorial on calculating powers of e in your head, I'm going to teach you how to do the same for our old friend Pi!

As an added bonus, calculating powers of Pi can be slightly easier than powers of e, so even if you passed up last week's tutorial, you should still give this one a look.

BASICS: In a manner similar to the previous tutorial, we'll request a number x, and solve for y in the equation π^x = 10^y.

This method, just like the previous one, is also based on turning this problem into a logarithm. It becomes log₁₀(π^x) = y, which simplifies to x × log₁₀(π) = y. This works out to about x × 0.49714987... = y.

This time around, we can take advantage of the fact that this number is close to 0.5!

TECHNIQUE: We'll use π¹⁶ as our example requested power.

The first step this time involves setting up a subtraction problem with 2 numbers, both of which start with the given number (16, in our example).

BUILDING THE SUBTRACTION PROBLEM: To begin, take the given number an multiply it by 500. This can be made simpler, if you prefer, by simply tacking “,000” on the end of your number, and then dividing by 2. This is the first number we need.

Applying this step to our example number 16, we add a comma and 3 zeroes to it (16,000), and then divide by 2 to get 8,000. We have our first number.

Note: If you're given an odd number, you will always end up with a “,500” at the end. For example, if the given number was 15, this step would result in 7,500. Knowing this is a handy way to make sure you didn't misplace the comma.

To get the second number for the subtraction problem, simply multiply the given number by 3. This should be easy enough to do without any special tips.

Doing this, our second number is 16 × 3 = 48.

SUBTRACTION:Having set up the 2 numbers for the subtraction problem the next step, not surprisingly, is to perform the subtraction by subtracting the smaller number from the larger number.

We've worked out the numbers 8,000 and 48 in our 16 example, so the subtraction problem is 8,000 - 48.

If you're like most people, though, you remember writing down subtraction problems with lots of zeroes in school, and having to borrow over multiple places. That being the case, you're probably wondering how to deal with all this in your head! The following video teaches you how to deal with problems like these without ANY borrowing:



To work out 8,000 - 48 using the above technique, it's probably better if you think of the problem as 8,000 - 048. The first step, as in the video, is to round the leftmost digit up, from 0 to 1 in this case, and seeing that 80 - 1 = 79. We already know the answer begins with 79!

How far up would you have to go from 48 cents to get to a whole dollar? Getting the answer of 52 cents shouldn't be a problem here. That's the other half of the answer.

Your running total, at this point, is 7,952. After a little practice, subtracting from zeroes in your head will seem not only less scary, but nearly effortless.

ADJUSTING FOR APPROXIMATION: We're going to add a little now to improve the accuracy of our answer. How do we do that?

Take the number you just subtracted, and throw away the ones digit. Divide the remaining digits by 2. If that ends in a .5, just throw the .5 away, as well. This is the number you add to your running total.

We just subtracted 48 to get 7,952. We take 48 and throw away the ones digit, leaving 4. Dividing that by 2, we get 2. Finally, we add 2 to 7,952 to get 7,954 as our new running total.

DIVIDING BY 1,000: To divide by 1,000, I could tell you to move the decimal point three places to the left, but there's an even simpler technique this time. All you have to do is replace the comma in the total with a decimal point!

With this approach, 7,954 instantly becomes 7.954 with very little effort.

At this point, you're done! As you can verify on Wolfram|Alpha, π¹⁶ ≈ 10^7.954.

THE FULL PROCESS ALL AT ONCE: To run through this at once, and to better acquaint you with the full range of situations you'll run across, let's try to work out π³³ = 10^y.

• Multiply 33 × 1,000 to get 33,000, and divide by 2, getting 16,500.
• Multiply 33 × 3 to get 99.
• Subtract 16,500 - 99 = 16,401.
• Throw away the 9 (the ones place of 99), leaving 9, and divide that by 2 (4.5), throwing away the .5 to leave 4.
• Add 16,401 + 4 = 16,405.
• Replace the comma with a decimal point, resulting in 16.405.