|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.
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)
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
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).
* I'm not really sure why - anyone? it looks like a weird mutant of
x*x=1+(x-1)(x+1) to me, but as far as I can tell, it's not exactly that.