On Sun, 05 Apr 2009 19:55:32 -0400, Jerry Avins <> wrote:
>Tim Wescott wrote:
>> You have a Very Large Number, expressed as an binary integer, in the
>> memory of a machine that allows for byte-wide operations. For some
>> unfathomable reason, you need to determine if this number is evenly
>> divisible by 17.
>>
>> Without using long division or repeated subtraction, and without ever
>> performing a multiply or divide on a number greater than eight bits long,
>> how can you determine if your number is divisible by 17?
>>
>> Once you know this technique, what other potential divisors can you test
>> for using this method?
>
>Express the bytes as hex pairs. Subtract each high digit from the
>corresponding low digit and add the result to a running sum. When the
>entire number has been processed, repeat the operation on the sum,
>iteratively until the sum is just one digit. The value of that digit is
>the original number mod 17.
>
>Add all digits instead of subtracting alternate ones. the result is the
>original number mod 15.
>
>In any base, the alternate difference of the digits yields N mod base+1,
>while the sum of the digits yields N mod base-1.
>
>Work in octal, and get divisibility by 7 and 9.
>
>I once proved it. Can you?
Yes. As you say it works on the same basis as proving divibility by
11 using base 10 notation.
0x0001 0x0000 + 0x0001 0x00 x 0x11 + 1
0x0010 0x0011 - 0x0001 0x01 x 0x11 - 1
0x0100 0x00FF + 0x0001 0x0F x 0x11 + 1
0x1000 0x0111 - 0x0001 0xF1 x 0x11 - 1
etc.
A number is divisible by 17 iff the alternating sum of its hexadecimal
digits is a multiple of 17.
Jon
|
Similar Threads
Linear Mode
