|
Well, he moved to Canada.
|
|
|
|
|
Pete O'Hanlon wrote: Well, he moved to had to move to Canada
FTFY 
|
|
|
|
|
If I were in Syria...
But true, a part of the move was worrying the my MS may develop into a less benign form.
|
|
|
|
|
Hey leppie  How are things going in the land of sun, skies and braai?
I've been busy man, haven't been on CP for sometime. Like Pete already said, I've moved back to Canada, I've been here since May and I can't wait for my wife and kids to catch up come this September
|
|
|
|
|
Mustafa Ismail Mustafa wrote: How are things going in the land of sun, skies and braai?
No sun, no blue skies, but still braaiing
I have been tempted to immigrate to Canada for a long time. One day I guess
|
|
|
|
|
I was raised here, I love it. I can actually say that I feel like I'm back home.
|
|
|
|
|
Maybe one day I will call it home too.
|
|
|
|
|
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;
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.
|
|
|
|
|
harold aptroot wrote: I haven't encountered a situation where this is useful
Euler question #1 
|
|
|
|
|
Well, I'm not sure. It can be used there, but afaict there is no advantage over doing it the normal way.
|
|
|
|
|
OK I figured out why 16^n-1 is divisible by 15: apply x*x=1+(x-1)(x+1) twice. I don't know why I didn't see this yesterday.
Let k = n / 2,
(16^k * 16^k - 1) / 15 =
(16^k - 1) * (16^k + 1) / 15 =
(16^(k-2) * 16 * 16 - 1) * (16^k + 1) / 15 =
(16^(k-2) * 15 * 17) * (16^k + 1) / 15 =
17 * 16^(k-2) * (16^k + 1)
So 16^n-1 was divisible by 15. For even n.
The step marked (!!) doesn't really work right for k < 2, but obviously 16^2-1 is also divisible by 15, with only one application of the "square - 1" rule.
So why is this true for odd n?
Kars gave a proof by induction that works something like this:
Base case: (16^1 - 1) / 15 = * z where z is a natural number, 1.
Inductive step: Show that (16^n - 1) / 15 is a natural number, given that (16^(n - 1) - 1) / 15 is.
(16^n - 1) / 15 =
((16^(n-1) - 1) * 16 + 16) / 15 =
(15 * z * 16 + 16) / 15 =
(15 * (z + 1) * 16) / 15 =
(z + 1) * 16
So, 16^n-1 is divisible by 15 for both even and odd n.
modified 5-Aug-12 10:58am.
|
|
|
|
|
|
Not very much, I think. It looks sort of the same when b is 1, but x * x - 1 = (x - 1)(x + 1) is really just a nice identity.
|
|
|
|
|
harold aptroot wrote: 16^n-1 is divisible by 15*
* I'm not really sure why - anyone?
16 ≅ 1 (mod 3) and (mod 5) ⇒ 16^n ≅ 1 (mod 15).
|
|
|
|
|
Thanks, that was much simpler than my other proofs
|
|
|
|
|
You're welcome
In regards to your problem, there's actually a whole set of ways to prove divisiblity of N (=a...bc) by n by checking if:
i*(a...b)+/-j*c is divisible by n for different i and j for how you split N up and whether you use a plus or minus sign. The simplest way is to usually just subtract a multiple of the last digit from the first group to make the number shrink faster.
n N (Constant)
3 327 32-7*(2)=18, 1-8*(2)=-15, 1-5*(2)=-9 (Stop when you reach the number or a single digit.)
7 133 13-3*(2)=7
11 132 13-2*(1)=11
|
|
|
|
|
Nice, where does the constant come from though?
|
|
|
|
|
I don't recall. There's a way to prove that every number has a unique constant (less than the number) associated with it. To derive it however, you can do trial and error based on the smallest two digit multiple of any number.
|
|
|
|
|
...Youtube is looking all magnified in Chrome?
Edit: For some reason, Chrome had zoomed youtube. I have no clue why this happened.
"Fear no factor", Prime Numbers.
|
|
|
|
|
It's just you...
I don't know, but I love to answer that to this question...
|
|
|
|
|
It's just you - try holding down the Control key, and moving the mouse wheel.
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
|
|
|
|
|
I thought that the other day. Think they have increased the default text sizes and the search box size etc.
|
|
|
|
|
|
Auntie has this[^] item on the South African double-amputee sprinter Oscar Pistorius' heat in the 400m at the Olympics.
The controversy over his prosthetics and whether they give him a mechanical advantage or not still simmers. Personally, I find this bloke completely inspirational and I wish him the very best in his other races in London. I don't know if he'll get a medal or not but what an amazing athlete he is.
"I do not have to forgive my enemies, I have had them all shot." — Ramón Maria Narváez (1800-68).
"I don't need to shoot my enemies, I don't have any." - Me (2012).
|
|
|
|
|
If his competitors do not like his "advantage", they can always have their legs amputated below the knee.
He doesn't have the choice.
Screw 'em - and good luck to him!
[edit]Typo = "then" for "they" - OriginalGriff[/edit]
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
