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 Vladimir Vassilevsky, Apr 6, 2009.

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