Motherboard Forums


Reply
Thread Tools Display Modes

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools
Display Modes

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


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


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


Welcome!
Welcome to Motherboard Point
 

Advertisment