number divisible by 17?

Question

Given a large positive number of at most 1000 digits. You have to find out whether that number is divisible by 17 or not. I know an algorithm which says multiply the last digit by 5 and subtract from the remaining number, if the resulting number is divisible by 17, then the number is divisible by 17. Is there any more efficient method?

Answer 1

What you can do is iterate over the digits, keeping track of the current value modulo 17. When you get to the end, if the current value modulo 17 is zero, then it's a multiple of 17; otherwise, not.

For example, if your number is "12345" (I'm assuming you have this number stored in a decimal string?), then the steps are:

• start with 0
• (0 * 10 + 1) mod 17 → 1
• (1 * 10 + 2) mod 17 → 12
• (12 * 10 + 3) mod 17 → 4
• (4 * 10 + 4) mod 17 → 10
• (10 * 10 + 5) mod 17 → 3

so 12345 mod 17 is 3: 12345 is not divisible by 17.

(Of course, with 12345 you could just write 12345 mod 17 to begin with, but with huge numbers, the above approach lets us process just a little bit at a time, which is convenient because it means all of our numbers are small enough to fit in the processor's native 32- or 64-bit integers.)

Answer 2

Another variant. 10⁸ is -1 mod 17.

So take the first 8 digits, convert into a number and % 17 to get the remainder mod 17. Then repeat with the next 8 digits, except that you subtract the number this time. Then add the next 8 digits, etc.

This results in fewer string->number conversions, and fewer mod 17 operations.