14,265,748 members

# Welcome to the Lounge

The Lounge is rated PG. If you're about to post something you wouldn't want your kid sister to read then don't post it. No flame wars, no abusive conduct, no programming questions and please don't post ads.

 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: ```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... lw@zi 4-Aug-12 2:35 lw@zi 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: 17-Aug-19 12:53     Last Update: 17-Aug-19 12:53 Refresh « Prev1...18965189661896718968189691897018971189721897318974 Next »