The Great Divide

Published on Sunday, April 27, 2014 in , , ,

Amirki's division with remainder imageGoing 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.
Now, if you want to test for divisibility by 11, you could simply scale it up to 99, and divide by 100 to test whether a number is a multiple of 11. Dividing by 100 is certainly easy enough.

Just as we did with Leapfrog Division II, perhaps there's a way to modify this approach to use the fact that numbers ending in 1 are also neighbors to numbers ending in 0.

I'll write more about this in the next post, but perhaps you can work out the approach on your own before then!


Leapfrog Division II

Published on Sunday, April 20, 2014 in , , , ,

Melchoir's, AzaToth's, Mets501's, and Sopoforic's 0.999 perspective imageA 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 1319, so I thought it might keep things simple if we used 1321 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 1321, converted it to 1320, dropped the zero to get 132. Subtracting 1 from the numerator at this point gives us 122 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 122 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)
Do you see how the new number to divide by 2 at each point. In each case, the tens digit is the remainder from the previous problem, and the ones/units digit is 9 minus the quotient from the previous problem. This is a little tricky until you get familiar and comfortable with the technique.

At this point, we can see that the pattern is already starting to repeat, which happens often. Checking with Wolfram|Alpha, we confirm that 1321 ≈ 0.61904761...

You would deal with improper fractions just as before, reducing them to mixed fractions (the links about improper fractions in the original post are still helpful here) before using the leapfrog technique. 7131, for example, should be converted to 2931 as the first step. So we have 2 something, and then we use this version of the leapfrog division technique to work out the decimal equivalent.

In this example, 931 becomes 930, which then becomes 93, and subtracting 1 from the numerator gives us 83. From here, we work out:
  • 08 ÷ 3 = 2 (remainder 2)
  • 27 ÷ 3 = 9 (remainder 0)
  • 00 ÷ 3 = 0 (remainder 0)
  • 09 ÷ 3 = 3 (remainder 0)
  • 06 ÷ 3 = 2 (remainder 0)
  • 07 ÷ 3 = 2 (remainder 1)
  • 17 ÷ 3 = 5 (remainder 2)
  • 24 ÷ 3 = 8 (remainder 1)
No, I don't see a pattern repeating yet, but that's more than enough digits to be impressive. Sure enough, Wolfram|Alpha confirms that 7131 ≈ 2.29032258...

If you take the time to become comfortable with the original version, and then this version, you have 2 very powerful tools for converting decimals to fractions. As a matter of fact, they may be more powerful than you think!

BONUS: Long-time Grey Matters readers may remember my posts on estimating square roots of non-perfect squares and a few tips and tricks. This square root estimation results in an answer in fraction form. Because you're always adding effectively adding two consecutive integers to get the denominator, you'll always have a fraction with an odd denominator.

So, the denominator in that feat will always end in either 1, 3, 5, 7, or 9. Thanks to both versions of the leapfrog division technique, you can now convert any denominators ending in 1 or 9. What about the others numbers?

It turns out that for denominators ending in 3, you can simply multiply the numerator and denominator by 3 to get an equivalent fraction with a denominator ending in 9. For example, 513 = 1539, so you can use the original version of the leapfrog division technique to work that out.

Similarly, when you have a denominator ending in 7, you can simply multiply the numerator and denominator by 3, which will give you a denominator ending in 1. 1217 = 3651, which should be easy for you with this second version of the technique.

For fractions with denominators ending in 5, this technique isn't often applicable. You may get lucky and be able to scale a fraction down to a number ending in 1 or 9, such as 2055 = 411, or 35145 = 729, but you can't always count on that. Using any whole number to scale a fraction up whose denominator ends in 5, of course, can only result in a denominator ending in 0 or 5, of course. If the denominator is just 5, though, you should have little problem working out the decimal equivalent.

Since you now realize you can handle odd denominators ending in 1, 3, 7, or 9, for the square root estimation feat, you stand a good 80% chance of being able to give a decimal equivalent, and taking the feat to an impressive new level!

I suggest practicing this, having fun with it, and impressing a few friends with your newfound skill. Enjoy!


How to Find Counterfeit Coins

Published on Sunday, April 13, 2014 in , , , , , ,

Toby Hudson's brass scale imageScam 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 (20) out of the first bag, 2 coins (21) out of the second bag, 4 coins (22) 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 (29) 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 2x 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 (29) 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 (28). 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
Are you getting the idea now? The only way for there to be 217 counterfeit coins in the group is if we'd take 128 counterfeit coins (27) from bag 7, 64 counterfeit coins (26) from bag 6, 16 counterfeit coins (24) from bag 4, 8 counterfeit coins (23) from bag 3, and 1 counterfeit coin (20) from bag0.

So, in our example with 217 counterfeit coins, the binary tells us that bags 7, 6, 4, 3, and 0 all contain counterfeit coins, and the rest are real. The decimal equivalents of the number from those bags, 128 + 64 + 16 + 8 + 1 = 217, confirms this answer.

Hopefully, you understand the concepts well enough at this point to figure out which bags are counterfeit if the total weight was, say, 1,062.2 grams (answer after the book excerpt below).

Martin Gardner covered this classic puzzle in a version with medicine (shown below), in his book Aha! Insight, which covers an amazing variety of perplexing situations which are solved with simple insights. They're all presented in the same friendly manner as the Medicine Mix-Up puzzles below.

I hope you enjoyed this look at a classic puzzle. There are many more versions out there, as well. Search the internet for the terms counterfeit coins, weighing, and puzzle to discover more ingenious approaches and ideas.


1062.2 grams - 1,023 grams = 39.2 grams

39.2 grams ÷ 0.1 gramscounterfeit coin = 392 coins

392 in binary = 0110001000

• Therefore, if the total weight is 1,062.2 grams, the bags containing counterfeit coins are bags 8, 7, and 3.


Calculate Powers of π In Your Head!

Published on Sunday, April 06, 2014 in , , , ,

Mehran Moghtadaei's Pi Digit GraphicAs 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 = 10y.

This method, just like the previous one, is also based on turning this problem into a logarithm. It becomes log10(πx) = y, which simplifies to x × log10(π) = 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 π16 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, π16 ≈ 107.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 π33 = 10y.

  • 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.
Once again, check for yourself on Wolfram|Alpha to see that π33 ≈ 1016.405

TIPS: Most of the tips I gave for e apply for π, as well. I'll repost the relevant ones below for convenience, modified for our Pi examples.

• By looking at the whole number part of the answer (the significand) and adding 1 to that, you can state the number of digits the full answer would have. In our 7.954 example, we take the whole number part, the 7, and add 1 to get 8, so we can state that the answer is a 8-digit number. Having worked out π33 to be about 1016.405, we can state that the answer is a 17-digit (16 + 1) number!

• You can handle exponents with a decimal in them by working them out as if they were a whole number, and then adjusting for an appropriate number of additional decimal points when you're moving the decimal point. For example, π1.6 is the same as π16, but with the decimal moved one place more to the left. Since π16 ≈ 107.954, it's easy to see that π1.6 ≈ 100.7954.

• If you want to take this a step further, and be able to say that π16 is roughly equal to 9 × 107, check out Nerd Paradise's Calculating Base 10 Logarithms in Your Head, the video Calculating logarithms in your head, and the PDF How to Quickly Calculate Logarithms to Three Decimal Places in Your Head.