It is well known that a number is divisible by 9 if and only if its digital root is 9. Less well known is that a similar trick kind applies to numbers other than 9, but doesn't really work out.

In order to make this trick "work" (I'll get to why it sometimes doesn't) for number

`k`

, the digit at position `i`

has to be multiplied by `base^i - [the biggest multiple of k <= base^i]`

before adding it to the (modified) digital sum.For example for

`k = 7, base = 10`

, you'd multiply the ones
position by 3, the tens position by 2, the hundreds position by 6, and
so forth (3, 2, 6, 4, 5, 8, then it repeats). It

*does*transform every multiple of 7 into a multiple of 7 (and every non-multiple-of-7 into a non-multiple-of-7), but it can be the same number, for example 14: 3 * 4 + 2 * 1 = 14, or it can even be a bigger number, for example 9.

But we're programmers, so the base isn't 10. It can be 16. 6 * 6 = 36, so every (positive integer) power of 16 ends in a 6, which means that the nearest lower multiple of 5 is only 1 away. So for

`k = 5`

, it works out to a factor of 1 at every position.Even better,

`16^n-1`

is divisible by 15, so for base 16, `k = 15`

works out well too, with a factor of 1 at every position. This leads to the following algorithm:static bool IsMultipleOf15(int x) { // lookup table to speed up last step const ulong lookuptable = 0x1000200040008001; int t = (x & 0x0F0F0F0F) + ((x & unchecked((int)0xF0F0F0F0)) >> 4); t = (t & 0x001F001F) + ((t & 0x1F001F00) >> 8); t = (t & 0x0000003F) + ((t & 0x003F0000) >> 16); t = (t & 0xF) + ((t & 0x70) >> 4); return ((lookuptable >> t) & 1) != 0; }15, of course, has factors 3 and 5, so the same code works to test for divisibility by 3 or 5 just by changing the lookup table to

`0x9249249249249249`

or `0x1084210842108421`

,
respectively (the two of those ANDed together gives the lookup table
for 15, of course). I haven't encountered a situation where this is
useful; modulo by a constant is optimized by every sane compiler so this
is never an optimization, just a curiosity (or perhaps something to
torture interviewees with).In the next post, I'll cover a divisibility testing algorithm that is actually useful.

## No comments:

## Post a Comment