William Chops Westfield: >> Also, to tell if a number is divisible by three, add the digits. If the >> sum is divisible by three, so is the original number. > I've never quite understood how to prove this sort of thing. Entirely too > discrete, or something. This method works because of a regularity in the remainder after dividing each digit (or a bit in binary) by 3. For example: 1/3 = 1/3 10/3 = 3 + 1/3 100/3 = 33 + 1/3 1000/3 = 333 + 1/3 See, the remainder for each digit is 1/3. The integer portion of the result can be ignored, because it divides evenly. A number can be represented as a sum of its digits multiplied by their weights (ones, hundreds, thousands, etc.). E.g. 1245 = 1000 + 200 + 40 + 5. But we know the remainder of dividing each digit, and it can be simply accumulated, giving a next shot at the remainder: 1245 1000 + 200 + 40 + 5 ---- = ------------------- = 1 * (333 + 1/3) + 2 * (33 + 1/3) + 4 * (3 3 3 + 1/3) + 5 * (1/3) = Then we separate the evenly divided numbers: = (1*333 + 2*33 + 4*3) * 1/3 + (1 + 2 + 4 + 5) * 1/3 The left half of that can be ignored, and the current remainder value (not always final because of multiplication by digit values) is (1 + 2 + 4 + 5)=12, or the sum of all digits. Then a question is: does the sum divide by 3? Sum again all digits! 1+2=3. Yes, it really does. Another example: 1234572457152345 % 3 ? 1+2+3+4+5+7+2+4+5+7+1+5+2+3+4+5=60 Next step: 6+0=6. Answer: it divides, 1234572457152345 % 3 = 0 The same method works in binary: 1/3 = 1/3 2/3 = 2/3 4/3 = 1 + 1/3 8/3 = 2 + 2/3 16/3 = 5 + 1/3 etc. The pattern repeats each two bits. Each even bit (2^0, 2^2, 2^4,...) is multiplied by 1, each odd bit (2^1, 2^3, 2^5,...) multiplied by two, and it all is added together until you get a 2-bit result. In other words, break a binary number in strings of 2 bits and add them together! Example: 101011b = 43d Break and add: 10b+10b+11b = 111b Break and add again: 1b+11b=100b Break and add again: 1b+00b=1b The remainder is 1. The number doesn't divide by 3. A variation of this method is also done when finding a modulo 9 result, but the pattern is tricker. 1/9=1/9 2/9=2/9 4/9=4/9 8/9=8/9=1-1/9 16/9=1+7/9=2-2/9 32/9=3+5/9=4-4/9 64/9=7+1/9=8-8/9 128/9=14+2/9=16-16/9 There are a number of ways you can calculate this. Given bits abcdefgh, it can be one of: ab-cde+fgh a-2*bcd+efgh -abcd+efgh .... Now we need Scott to select the best one! :) > Furthermore... Does this HELP any if you have a > binary number in a computer? After all, you'd have to derive the decimal > digits of the number, which (usually) involves successive and multiple > divisions by 10, which is a lot harder than just dividing by three in > the first place... Of course it helps. Who cares about decimal? :) > I suppose that if you have an easy way to convert to base 9, then all > the numbers divisible by 9 will end in zero, right? Yes, that's what is actually done. We find a remainder and check its value. Nikolai -- http://www.piclist.com hint: To leave the PICList mailto:piclist-unsubscribe-request@mitvma.mit.edu