1. This forum section is a read-only archive which contains old newsgroup posts. If you wish to post a query, please do so in one of our main forum sections (here). This way you will get a faster, better response from the members on Motherboard Point.

Re: A Puzzle for Today

Discussion in 'Embedded' started by Jerry Avins, Apr 6, 2009.

1. Jerry AvinsGuest

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?

Jerry
--
Engineering is the art of making what you want from things you can get.
Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯Â¯

Jerry Avins, Apr 6, 2009

2. Jon KirwanGuest

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

Jon Kirwan, Apr 6, 2009

3. Jon KirwanGuest

On Mon, 06 Apr 2009 03:58:15 GMT, Jon Kirwan
<> wrote:

>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

^^^^^^
woops...

>0x1000 0x1001 - 0x0001 0xF1 x 0x11 - 1

Typo thing easily seen and fixed. Sorry about that.

Jon

Jon Kirwan, Apr 6, 2009