A Puzzle for Today

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?

-- 
http://www.wescottdesign.com

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?

That's simple: X must be (a << 4) + a;  check the lowest byte.

The magic numbers are 2^n +/- 1


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

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.

Perhaps you meant (a<<4) + a; good question for job interview.

Here is the question I like:

We have to transmit RS-232 by the AC coupled line. Hence the signal has 
to be DC balanced, i.e. have equal amount of ones and zeroes. How many 
bit combinations like that can be made of one byte? How about the 
general case of the block of N bytes?

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Sun, 05 Apr 2009 19:55:32 -0400, Jerry Avins <jya@ieee.org> 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

On Sun, 05 Apr 2009 19:01:43 -0500, Vladimir Vassilevsky
<antispam_bogus@hotmail.com> 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.
>
>Perhaps you meant (a<<4) + a; good question for job interview.
>
>Here is the question I like:
>
>We have to transmit RS-232 by the AC coupled line. Hence the signal has 
>to be DC balanced, i.e. have equal amount of ones and zeroes. How many 
>bit combinations like that can be made of one byte? How about the 
>general case of the block of N bytes?

If I gather that you can permit the entire 8 bit field to be out of
balance so long as it comes out balanced on 8 bit boundaries, it's
just combinatorial stuff.  70 ways to select 4 '1's out of 8 bits.
(n!/[r!*(n-r!)])  The notation is usually just a big paren with n on
top and r on bottom.

Since this is RS-232 signaling I might also assume it's asynch, and
then the start and stop bits plus the long mark times that may
intervene between byte transmissions may need accounting for.  But
then you said it's not RS-232 signaling since it is AC coupled, which
isn't RS-232 which specifies a DC path, so all bets are off.

Jon

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?
> 
> Jerry

Wow.  I didn't know about the N mod base+1 rule; I was thinking add all 
the bytes together (to get the number mod 255), then check the resulting 
one-byte number for divisibility by 17 ('cause 255 is 15 * 17).

Live and learn.

(but note that on my proposed machine, my method's probably faster 
because you don't have to shift and mask for 8-bit access the way you 
would for 4-bit access).

I once proved the N mod base-1 rule, but I can't remember the details; 
I'm going to look at Jon's proof.

-- 
http://www.wescottdesign.com

On Mon, 06 Apr 2009 04:00:15 +0000, Jon Kirwan wrote:

> On Sun, 05 Apr 2009 19:01:43 -0500, Vladimir Vassilevsky
> <antispam_bogus@hotmail.com> 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.
>>
>>Perhaps you meant (a<<4) + a; good question for job interview.
>>
>>Here is the question I like:
>>
>>We have to transmit RS-232 by the AC coupled line. Hence the signal has
>>to be DC balanced, i.e. have equal amount of ones and zeroes. How many
>>bit combinations like that can be made of one byte? How about the
>>general case of the block of N bytes?
> 
> If I gather that you can permit the entire 8 bit field to be out of
> balance so long as it comes out balanced on 8 bit boundaries, it's just
> combinatorial stuff.  70 ways to select 4 '1's out of 8 bits.
> (n!/[r!*(n-r!)])  The notation is usually just a big paren with n on top
> and r on bottom.
> 
> Since this is RS-232 signaling I might also assume it's asynch, and then
> the start and stop bits plus the long mark times that may intervene
> between byte transmissions may need accounting for.  But then you said
> it's not RS-232 signaling since it is AC coupled, which isn't RS-232
> which specifies a DC path, so all bets are off.
> 
> Jon

If both start and stop bits are one long they'll balance; you'll be left 
with just needing to balance your data.

If you could allow one bit of imbalance either way you could have 156 
combinations; that's gotta be better.

-- 
http://www.wescottdesign.com

On Mon, 06 Apr 2009 03:58:15 GMT, Jon Kirwan
<jonk@infinitefactors.org> 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

Vladimir Vassilevsky wrote:

> We have to transmit RS-232 by the AC coupled line. Hence the signal has 
> to be DC balanced, i.e. have equal amount of ones and zeroes. How many 
> bit combinations like that can be made of one byte? How about the 
> general case of the block of N bytes?

This is an interesting problem from a mathematical point of view. I'm a
programmer, so I have hacked a small program (see below), which calculates
it for n bits, because this was faster and more safe than when I try to
derive it mathematically. Then I searched the sequence at NJAS and found
this one:

http://www.research.att.com/~njas/sequences/A000984

So for N bytes there are (8*N)!/((4*N)!)^2 possible combinations.

For practical reasons (would be bad to have 10 bytes with 0 and 10 bytes
with 0xff) I would simply use some standard bi-phase encoding, like AES-3
or Manchester.

(loop for bit from 1 to 24 with number = 2
      do (loop for i to (1- number) with test = 0
               finally (format t "~a ~a~%" bit test)
               do (loop for j to bit with sum = 0 and b = i
                        finally (when (= sum (/ bit 2)) (incf test)) do
                        (when (= (logand b 1) 1) (incf sum))
                        (setf b (truncate b 2))))
      (setf number (* 2 number)))

-- 
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de