Forwarded for Scott who's ISP is belly up. James Newton, PICList Admin #3 mailto:jamesnewton@piclist.com 1-619-652-0593 phone http://www.piclist.com ----- Original Message ----- From: Scott Dattalo To: Sent: Sunday, June 10, 2001 14:52 Subject: Re: [pic]: 9 James, Could you post this for me? I saw it in the archives... Peter L. Peres wrote: > The theorem that 'a number is divisible by 3 if the sum of its digits is > divisible by 3' is not valid in base 2 and afaik in no other base than > 10. It's valid in base 4. It's valid in base 7. It's valid for all bases in which (base % 3) = 1. See Tom Messenger's post of the explanation I wrote a couple of years ago: http://www.infosite.com/%7Ejkeyzer/piclist/2001/Jun/0836.html In fact, it's not too hard to see that the sum of digits trick works in base M for the digit N if (M % N) = 1. For example, in octal, if the sum of the digits of a number is divisible by 7 then so is the number. Try it! Nikolai Golovchenko wrote: > 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 Actually, the last one should be -2*abcd + efgh This is the one I was thinking that would be most optimal. That's why I said hint 16 = 18 - 2. Another way to look at this is to write the number explicitly: abcdefgh = (abcd)*16^1 + (efgh)*16^0 If you want to know if this is divisible by 9, then: abcdefgh % 9 = (abcd)*16 % 9 + efgh % 9 = (abcd)*(-2) % 9 + efgh % 9 because, 16 is congruent to -2 mod 9. It's also congruent to 7, so we could write: abcdefgh % 9 = abcd*7 % 9 + efgh % 9 if you know 'a' is 0, then you can determine if the number is divisible in 11 instructions using this trick: movwf temp swapf temp,w subwf temp,f skpdc addlw 7 subwf temp,w skpdc addlw 9 andlw 0x0f skpz addlw -9 Maybe someone sees a way to squeeze in the check of a. Scott -- http://www.piclist.com hint: To leave the PICList mailto:piclist-unsubscribe-request@mitvma.mit.edu