15,616,869 members

# Welcome to the Lounge

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 Re: So we were hanging out Chris Meech and I, yesterday.. Pete O'Hanlon4-Aug-12 10:29 Pete O'Hanlon 4-Aug-12 10:29
 Re: So we were hanging out Chris Meech and I, yesterday.. PIEBALDconsult4-Aug-12 12:35 PIEBALDconsult 4-Aug-12 12:35
 Re: So we were hanging out Chris Meech and I, yesterday.. Mustafa Ismail Mustafa4-Aug-12 13:19 Mustafa Ismail Mustafa 4-Aug-12 13:19
 Re: So we were hanging out Chris Meech and I, yesterday.. Mustafa Ismail Mustafa4-Aug-12 13:16 Mustafa Ismail Mustafa 4-Aug-12 13:16
 Re: So we were hanging out Chris Meech and I, yesterday.. `leppie`5-Aug-12 5:47 `leppie` 5-Aug-12 5:47
 Re: So we were hanging out Chris Meech and I, yesterday.. Mustafa Ismail Mustafa10-Aug-12 10:00 Mustafa Ismail Mustafa 10-Aug-12 10:00
 Re: So we were hanging out Chris Meech and I, yesterday.. `leppie`12-Aug-12 7:32 `leppie` 12-Aug-12 7:32
 Digital roots and divisibility harold aptroot4-Aug-12 3:50 harold aptroot 4-Aug-12 3:50
 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: C# ```static bool IsMultipleOf15(int x) { const ulong lookuptable = 0x1000200040008001; // lookup table to speed up last step 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). * 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.
 Re: Digital roots and divisibility `leppie`4-Aug-12 9:25 `leppie` 4-Aug-12 9:25
 Re: Digital roots and divisibility harold aptroot4-Aug-12 9:34 harold aptroot 4-Aug-12 9:34
 Re: Digital roots and divisibility harold aptroot5-Aug-12 1:23 harold aptroot 5-Aug-12 1:23
 Re: Digital roots and divisibility Kenneth Haugland5-Aug-12 7:12 Kenneth Haugland 5-Aug-12 7:12
 Re: Digital roots and divisibility harold aptroot5-Aug-12 8:50 harold aptroot 5-Aug-12 8:50
 Re: Digital roots and divisibility Bassam Abdul-Baki6-Aug-12 2:47 Bassam Abdul-Baki 6-Aug-12 2:47
 Re: Digital roots and divisibility harold aptroot6-Aug-12 3:36 harold aptroot 6-Aug-12 3:36
 Re: Digital roots and divisibility Bassam Abdul-Baki6-Aug-12 4:06 Bassam Abdul-Baki 6-Aug-12 4:06
 Re: Digital roots and divisibility harold aptroot6-Aug-12 4:41 harold aptroot 6-Aug-12 4:41
 Re: Digital roots and divisibility Bassam Abdul-Baki6-Aug-12 4:45 Bassam Abdul-Baki 6-Aug-12 4:45
 [Solved]Is it just me or... dan!sh 4-Aug-12 2:35 dan!sh 4-Aug-12 2:35
 Re: Is it just me or... Joan M4-Aug-12 3:29 Joan M 4-Aug-12 3:29
 Re: Is it just me or... OriginalGriff4-Aug-12 3:30 OriginalGriff 4-Aug-12 3:30
 Re: Is it just me or... DaveAuld4-Aug-12 4:57 DaveAuld 4-Aug-12 4:57
 Re: [Solved]Is it just me or... peterchen6-Aug-12 5:37 peterchen 6-Aug-12 5:37
 Oscar Pistorius. Septimus Hedgehog4-Aug-12 0:13 Septimus Hedgehog 4-Aug-12 0:13
 Re: Oscar Pistorius. OriginalGriff4-Aug-12 0:28 OriginalGriff 4-Aug-12 0:28
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Apr-23 3:34 Refresh ᐊ Prev1...24357243582435924360243612436224363243642436524366 Next ᐅ