Sunday, December 27, 2009

Mega Shark vs Giant Octopus

The Scifi channel have a habit of showing some fairly awful movies and Midori has a habit of recording them - tedious tromps around the woods looking for a Sasquatch that never comes into shot, ghosts of dinosaurs attacking oil drillers in Alaska. Last night she excelled herself. I was too tired to do anything but watch and 20 minutes in it played its trump card. A scene of such ball-shattering awsomnitude that the clip has been watched more than 750,000 times on youtube.

Actually that clip has only been watched 60,000 times but the other clip replaced the movie's soundtrack with a song for no apparent reason so I linked to this version.

Think of how many consecutive failures in quality control had to happen for that to appear on my TV last night.

More importantly, someone was paid to write that scene and in fact the whole film and if that wasn't you then you are losing the game of life!

Sunday, December 13, 2009

Computing combinatorials

I was commenting on this fun post about efficiently computing n-choose-c but my attempt to post some code seems to have been eaten by the comment system (I suspect use of square and angle brackets upset it), so I'll post something here instead.

Here's why c always takes integer values and more generally why (k + 1) * (k + 2) * ... * (k + n) is always divisible by factorial(n). There are three ways to show this.

Apologies for the crappy maths typesetting, I should really figure out how to do this nicely.

Proof by hand-waving.

First off, something hand-wavy. One of (k + 1)*(k + 2) is even so 2 divides into that product. One of (k + 1)*(k + 2)*(k + 3) is threeven (not a real word!) so 3 divides into that product. 4 is not so simple. One of (k + 1)*(k + 2)*(k + 3)*(k + 4) is fourven so 4 divides into that product - however maybe the fourven number was also the even number we used to cancel the 2 earlier on so it only has one 2 left for division but if that's the case then since one of the remaining 3 numbers is also even and you can get a 2 from that to make up the 4. 5 works just like 2 and 3. 6 contends with both 2 and 3 but you can resolve that too. This gets messy quickly but essentially, for any prime p, every time you come to the next multiple of p in the divisor you will have already added at least one multiple of p in the k+i product and by the time you hit a multiple of p2 you will have already hit a corresponding one in the k+i product too, so you'll still have enough ps in the product overall to cancel all the ps in the divisor. Still a bit hand-wavy but it could be made rigorous, however there is another proof that's easily rigorous but less insightful.

Proof by counting prime factors.

There is a well known formula for finding the power of p in factorial(n). It's

sum(i=1..infinity, [n/pi])

where [] means take the integer part, throwing away any fractions. So if p = 5, and n=30 then this is
[30/5] + [30/25} + [30/125] + [30/625] + ... = 6 + 1 + 0 + 0 + ...

It's all zeros after that, so the end result is 7. So 57 divides factorial(30) and 7 is the highest power of 5 that divides it.

So rewriting the k + i product as factorial(k + n)/factorial(k) we now know that for any prime p, it contains exactly

sum(i=1..infinity, [(n+k)/pi]) - sum(i=1..infinity, [(k)/pi])

powers of p. If this is greater than
sum(i=1..infinity, [(k)/pi])

then we know that factorial(n) divides factorial(k + n)/factorial(k).

Well, [x + y] >= [x] + [y] so

[(n+k)/pi] >= [(n)/pi] + [(k)/pi]

now bring one term over to the left hand side to get

[(n+k)/pi] - [(n)/pi] >= [(k)/pi]

Now sum over i=1..infinity and you get exactly what we needed to show. So for any prime p, there are at least as many powers of p in the k+i product as there are in factorial(n), all the ps in the divisor cancel out and the divisor divides in evenly.

Proof by "it just is".

The final and least insightful way is to note that factorial(n+k)/(factorial(k) * factorial(n)) is n+k choose n and so must be an integer


Here's a python snippet that checks that the division is always even with an assert.

Give it an n and it will print out comb(n, i) for all i. The assert never fires for me.

As it loops, c gets the values comb(k + 1, 1), comb(k + 2, 2), ..., comb(n, n - k), all of which are integers (and remember that comb(n, n - k) = comb(n, k) so c ends up with the desired value.)

If your lanugage does tail-call optimisation, you could define

comb(n, 0) = 1
comb(n, i) = comb(n - 1, i - 1) * n / (n - k)

and be done. With memoisation you could avoid lots of repeated calculations.

Wednesday, December 09, 2009

Eddie Hobbs and the car scrappage scheme.

Update:Eddie's reply is at the bottom

Lots of good things in this post but I'm surprised to see positive mention of the car scrappage scheme - "Focus on energy efficiency, green energy and a cash- for- clunkers scheme for low emission cars.". It is neither green nor good for the economy.

We don't have a car industry, we have a car sales force which funnels money straight out of this economy with a small bit staying locally. Stimulate this and you stimulate the Germany and Japanese economies far more than the Irish.

Scrapping cars that have plenty of life left just to have them replaced with something that is maybe 10% less emitting is going to cause a net increase when you factor in the manufacture of the car. Never mind that fact that some will upgrade their cars to bigger, more-polluting models.

Given all that I'm curious why Eddie thinks it's a good idea. he makes a virtue of not being beholden to vested interests so it's unlikely he's saying it for his mates in the motor trade. There are ways to spend the scrappage money that would produce a greater economic stimulus in this country and produce greater environmental impact per euro too.

I sent Eddia a link to this and he replied quite quickly which is very good of him. He said

Yeah, you’re right to pick me up on it. Technically it’s the wrong thing to do since we don’t have a car manufacturing industry but that is softened somewhat by the emphasis on Band A and B. It is, of course, front-end loading cars sales but the x factor is the sight of 2010 new plates on the road, car rooms with consumers in them and a lift in consumer morale. Very hard to measure I know and a subjective call but morale is pretty important to arrest the spending delay factor caused by deflation. Much will depend on the relative allocation to energy, efficiency etc where we’ll get a proper return so let’s see at teatime.
to which I say, hmmm... maybe. One small snag here is that these newly confident consumers just blew all their money on a new car so although they feel good, they're less likely to do anything as a result...

in reference to: Ten things Brian Linehan must get right (view on Google Sidewiki)