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 Avins

    Jerry Avins Guest

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

  2. Jon Kirwan

    Jon Kirwan Guest

    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
     
    1. Advertising

  3. Jon Kirwan

    Jon Kirwan Guest

    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
     
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sk

    A puzzle to puzzle you

    sk, Jul 17, 2004, in forum: Hardware
    Replies:
    3
    Views:
    357
    jamotto
    Jul 18, 2004
  2. Vladimir Vassilevsky

    Re: A Puzzle for Today

    Vladimir Vassilevsky, Apr 6, 2009, in forum: Embedded
    Replies:
    0
    Views:
    274
    Vladimir Vassilevsky
    Apr 6, 2009
  3. Vladimir Vassilevsky

    Re: A Puzzle for Today

    Vladimir Vassilevsky, Apr 6, 2009, in forum: Embedded
    Replies:
    22
    Views:
    653
    Rocky
    Apr 22, 2009
  4. Jon Kirwan

    Re: A Puzzle for Today

    Jon Kirwan, Apr 6, 2009, in forum: Embedded
    Replies:
    2
    Views:
    274
    Jon Kirwan
    Apr 6, 2009
  5. Habib Bouaziz-Viallet

    Re: A Puzzle for Today

    Habib Bouaziz-Viallet, Apr 8, 2009, in forum: Embedded
    Replies:
    9
    Views:
    278
    Jerry Avins
    Apr 9, 2009
Loading...

Share This Page