# Re: A Puzzle for Today

Jerry Avins
Guest
Posts: n/a

 04-05-2009, 11:55 PM
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jon Kirwan
Guest
Posts: n/a

 04-06-2009, 03:58 AM
On Sun, 05 Apr 2009 19:55:32 -0400, Jerry Avins <(E-Mail Removed)> 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
Guest
Posts: n/a

 04-06-2009, 04:56 AM
On Mon, 06 Apr 2009 03:58:15 GMT, Jon Kirwan
<(E-Mail Removed)> 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

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Vladimir Vassilevsky Embedded 22 04-22-2009 02:20 PM Habib Bouaziz-Viallet Embedded 9 04-09-2009 10:15 PM Jon Kirwan Embedded 2 04-06-2009 06:45 AM Vladimir Vassilevsky Embedded 0 04-05-2009 11:43 PM sk Hardware 3 07-18-2004 02:50 AM

All times are GMT. The time now is 06:53 AM.

Welcome!