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!

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 p² 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/pⁱ])

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 5⁷ 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)/pⁱ]) - sum(i=1..infinity, [(k)/pⁱ])

powers of p. If this is greater than

sum(i=1..infinity, [(k)/pⁱ])

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

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

[(n+k)/pⁱ] >= [(n)/pⁱ] + [(k)/pⁱ]

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

[(n+k)/pⁱ] - [(n)/pⁱ] >= [(k)/pⁱ]

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

Code

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

#! /usr/bin/python2.4 import sys def comb(n, k): # k = max(k, n - k) # would make it go faster c = 1 for i in range(k + 1, n + 1): c *= i assert c % (i - k) == 0 c /= i - k return c n = int(sys.argv[1]) for i in range(0, n + 1): print "comb(%d, %d) = %d" % (n, i, comb(n, i))

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.

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)

Independent nonsense: negligent doctors

As usual, the Indo provides some useless statistics, this time on malpractice cases. What they tell us is:

A senior house officer -- a grade of junior doctor -- was most likely to be involved (74pc) as against 14pc for registrars and 8pc for consultants.

What they don't tell us is what percentage of patients are dealt with by each type of doctor. So if only 50% of patients were dealt with by junior doctors but they were involved in 74% of malpractice cases then that's a black mark against junior doctors and would be something worth knowing. Elsewhere in the article it's stated that they deal with "the majority" of cases. Without these other figures, the statistics are not just useless, they're possibly quite misleading.

in reference to: http://www.independent.ie/national-news/ae-blunders-responsible-for-one-in-seven-medical-claims-1951185.html (view on Google Sidewiki)

The "open" web awards.

They want me to sign in with a twitter or facebook account, not any of the many other sign-in systems out there. Not very open...

in reference to: Mashable's 2009 Open Web Awards - Votes (view on Google Sidewiki)

Sichuan House - Spicy chilli chicken

Mostly a note to myself. I got in a quick trip to Sichuan House on Sunday with Riona. I ordered Spicy Chilli Chicken (山椒鳥 I think). It was quite tasty but the sauce was not very exciting. I was expecting a different dish actually but now I have no idea what that one is called. This was cubes of chicken but looked a lot like an Irish-style dish (I was assured it wasn't and in fairness it didn't taste like it was, just looked like it).

Looking up Kanji/Hanzi quickly on zhongwen.com

Update: I've turned this into a Google App Engine app - http://zhongwenlookup.appspot.com/

zhongwen.com is an excellent dictionary that shows the decomposition of all Chinese characters and links to the entry for each component. It's the online version of Rick Harbaugh's "Chinese Characters: A Genealogy and Dictionary". I've spent plenty of time looking things up in it while learning Kanji (both online and in my own copy).

The one problem I have is that it's not possible to just paste a character into the search box and get to the entry. You can only search by radical, pronunciation and radical none of which lead directly to a single character. Tonight I finally got bored with that and was about to mail the author to see if he would add a search by character feature. While composing the mail I started poking a bit further and realised that the URL scheme for the site is based on the BIG5 encoding of Chinese characters and so I could just do it myself.

Here's a little bash script that takes characters as arguments and gives you back the zhongwen.com URLs and pass them to a command called browser which, for me, opens them in Firefox. Yes it's ugly. I tried to convert it to Perl but ran into encoding problems that I couldn't be bothered solving.

#! /bin/bash -e if [ -z "$@" ]; then echo Usage: ./harb char1 char2 ... echo echo Will print the zhongwen.com URL for the characters and pass them to browser fi while [ $# -gt 0 ]; do url=$( echo $1| iconv -t big5| \ perl -lne '@c=unpack("CC", $_); print "http://zhongwen.com/d/$c[0]/x$c[1].htm"' ) echo $url browser "$url" shift done

Invoke it as harb 宅 煉 to get the URLs for those 2 characters. Characters must passed as separate arguments (e.g. space separated).

Here's my browser script, while I'm at it

#! /bin/bash if firefox -remote 'ping()'; then firefox -remote "openURL($1,new-tab)" else echo no ping firefox "$1" & fi

1889 Kanji Characters

It's been slow going for a while now but I'm 153 away from finishing the book. I would have said that's just a few weeks away but it seems that every week now something comes up and I end up add only 10 or so kanji. The current chapter is a mixed bag of kanji that don't really fit into the scheme at all and is supposedly the most difficult chapter. I hope I can finish the whole thing before December. I'd like to be able to say I cracked it in less than a year. At this point there is no way I'm giving up!

Some stats - I've done 22451 repetitions, that means I've written that many kanji. So on average I've written each one about 12 times which is not so bad really. I have an 88.2% success rate on "mature cards" which is also OK but I find recently that cards from 6 months ago are coming up and I'm flummoxed. I think Anki is a bit too aggressive in increasing the interval between repetitions. I could tune that but at this point it's mostly working and I don't want to screw with it. I've been doing this for for 319 days. On 160 of them I added new kanji, on 159 of them I added no new kanji.

Finally a graph:

Hyperbinary numbers

Update: The proof is over here.

I've been following along the a discussion on The Math Less Travelled about hyperbinary numbers (here, here and here). I'm posting this here because it's a bit too big to fit in the margins of the other blog (although I have found no remarkable proof). Since I have very little time to work on this (and have already given myself a few nights with insufficient sleep!) I thought I'd do a brain-dump of what I did in case someone else can finish it. Apologies for the awful formatting, I don't post much maths so have no nice styles for it and no time to find them.

Quick summary

h(n) is the number of ways of writing n as a sum of powers of 2 where each power of 2 can only occur 0, 1 or 2 times. See the articles for more details but the key facts are (I'll refer to them by these numbers):

1. h(2n) = h(n) + h(n - 1)
2. h(2n + 1) = h(n)

From those you can get several relationships, like h(k * 2^n - 1) = h(k-1). Other interesting stuff is in those posts. The main question is how to find the inverse of h(n). That is, given k, what values of n have h(n) = k. It turns out that each even solution to that leads to an infinite number of odd solutions and all odd solutions can be traced back to an even solution. So the question then is what are the even solutions - the "primary occurrences"? My contribution so far has been to notice that there seem to be φ(k) even solutions for a given k although I am still stumped on how to prove that.

Another useful things is that h(2n + 1) = h(n) means that all the odd positions are just repeats of earlier values. Applying fact 1 to the right hand side of fact 2 gets you h(2n) = h(2n + 1) + h(2n - 1). So all the even positions are just the sum of the values that come immediately before and after.

Finally, h(2^n - 1) = 1 and h(2^n) = n + 1 and from that you can get h(2^n + 1) = n

New stuff

The last bits got me thinking about h(2^n + k). It's fairly easy to figure that out for more and more values of k. For h(2^n + 2) just apply fact 1 to get that as the sum of 2 things we already know:

h(2^n + 2) = h(2^(n-1) + 1) + h(2^(n-1)) = (n-1) + (n-1) + 1 # note this line for discussion below. = 2n - 1.

Looking at the table of values primary occurrences (here) you can see that all of the odd entries do indeed have 2^n + 2. In fact after a bit, it's the lowest value for each odd entry.

What about 1? 2*1 - 1 = 1 but if n = 1 the line commented above is not valid because h(2^n + 1) = n is only valid for n > 1.

To get a bit further, consider h(2n) = h(2n + 1) + h(2n - 1) from above. Moving things around a little that becomes h(2n + 1) = h(2n) - h(2n - 1). So we can get the next odd entry by subtracting the previous odd entry from the previous even entry. So h(2^n + 3) = n - 1. Since 2^n + 3 is odd this doesn't tell us anything about primary occurrences but it's still useful as all odd entries are duplicated later on.

Now we can get h(2^n + 4) = h(2^(n-1) + 2) + h(2^(n-1) + 1) and again we know what they are = (2n - 1) + n = 3n - 1. And low and behold, all the entries (except 2) in the primary occurrences table of the form 3n - 1, include have 2^n + 4 (5 -> 12, 8 -> 20, 11 -> 36, ...). What about 2? 2 = 3*1 -1 but if n=1 then the relation above breaks because the 2n - 1 rule is only valid for n > 1.

Continuing on in the same vein you get the first 100:

h(2^n + 0) = 1n + 1 h(2^n + 2) = 2n - 1 h(2^n + 4) = 3n - 4 h(2^n + 6) = 3n - 5 h(2^n + 8) = 4n - 9 h(2^n + 10) = 5n - 12 h(2^n + 12) = 5n - 13 h(2^n + 14) = 4n - 11 h(2^n + 16) = 5n - 16 h(2^n + 18) = 7n - 23 h(2^n + 20) = 8n - 27 h(2^n + 22) = 7n - 24 h(2^n + 24) = 7n - 25 h(2^n + 26) = 8n - 29 h(2^n + 28) = 7n - 26 h(2^n + 30) = 5n - 19 h(2^n + 32) = 6n - 25 h(2^n + 34) = 9n - 38 h(2^n + 36) = 11n - 47 h(2^n + 38) = 10n - 43 h(2^n + 40) = 11n - 48 h(2^n + 42) = 13n - 57 h(2^n + 44) = 12n - 53 h(2^n + 46) = 9n - 40 h(2^n + 48) = 9n - 41 h(2^n + 50) = 12n - 55 h(2^n + 52) = 13n - 60 h(2^n + 54) = 11n - 51 h(2^n + 56) = 10n - 47 h(2^n + 58) = 11n - 52 h(2^n + 60) = 9n - 43 h(2^n + 62) = 6n - 29 h(2^n + 64) = 7n - 36 h(2^n + 66) = 11n - 57 h(2^n + 68) = 14n - 73 h(2^n + 70) = 13n - 68 h(2^n + 72) = 15n - 79 h(2^n + 74) = 18n - 95 h(2^n + 76) = 17n - 90 h(2^n + 78) = 13n - 69 h(2^n + 80) = 14n - 75 h(2^n + 82) = 19n - 102 h(2^n + 84) = 21n - 113 h(2^n + 86) = 18n - 97 h(2^n + 88) = 17n - 92 h(2^n + 90) = 19n - 103 h(2^n + 92) = 16n - 87 h(2^n + 94) = 11n - 60 h(2^n + 96) = 11n - 61 h(2^n + 98) = 16n - 89 h(2^n + 100) = 19n - 106

With the 2^n + k only being valid for n such that 2^n > k.

Obviously calculating these by hand gets a bit boring. To write some code to do it I had to play with f(n, m) = h(2^n + m) and it breaks down into 2 cases for m even and odd.

For the odd case, let m = 2k + 1. So

f(n, m) = h(2^n + m) = h(2^n + 2k + 1) = h(2n + 1) = h(2^n + 2k) - h(2^n + 2k - 1)

For the even case, let m = 2k. So

f(n, m) = h(2^n + m) = h(2^n + 2k) = h(2(2^(n-1) + k)) = h(2^(n-1) + k) + h(2^(n-1) + k -1) (applying fact 1) = h(2^(n-1) + m/2) + h(2^(n-1) + m/2 -1) = f(n - 1, m/2) + f(n -1, m/2 - 1)

Turning that into python and adding a couple of base cases gives the following code (it tries to also cope with 2^n - m but there's a bug somewhere). #! /usr/bin/python2.4 import sys class ANPlusB(object): def __init__(self, a, b): self.a = a self.b = b def Sub(self, n_plus): return ANPlusB(self.a, self.b + self.a * n_plus) def Eval(self, n): return self.a * n + self.b def __str__(self): if self.b < 0: s = "-" b = - self.b else: s = "+" b = self.b return "% 4sn %s % 4s" % (self.a, s, b) def __add__(self, other): return ANPlusB(self.a + other.a, self.b + other.b) def __sub__(self, other): return ANPlusB(self.a - other.a, self.b - other.b) TABLE = {-2: ANPlusB(1, -1), -1: ANPlusB(0, 1), 0: ANPlusB(1, 1), 1: ANPlusB(1, 0), } biggest = 1 smallest = -1 def F(n_plus, k): """Find the a*n +b for 2^(n + n_plus) + k .""" # Note something is broken for negaitve n_plus, going below -10 # causes infinite recursion. global smallest, biggest if k not in TABLE: if k < smallest: val = _FSmaller(k) smallest = k else: val = _FBigger(k) biggest = k TABLE[k] = val val = TABLE[k] return val.Sub(n_plus) def _FBigger(k): if k % 2: return F(0, k - 1) - F(0, k - 2) else: return F(-1, k / 2) + F(-1, (k / 2) - 1) def _FSmaller(k): if k % 2: return F(0, k + 2) - F(0, k + 1) else: return F(-1, k / 2) + F(-1, (k / 2) - 1) def main(): min, max = [int(x) for x in sys.argv[1:]] for i in range(min, max+1, 2): print "h(2^n + % 4d) = %s" % (i, F(0, i)) if __name__ == "__main__": main()

You can run it as ./hyperbinary.py 0 100 or to get the first 50 even entries. Looking at the output it seems that h(2^n + m) = h(m) * n + c. I haven't proved it formally but it should be easy enough, just show that the coefficient of n obeys the fact 1 and fact 2. I didn't find a good relation between m or h(m) and the c above (the best I can spot is that int(c/h(m)) is always log_2(m) and when m is 2^k c=k*h(m) + 1). Nor did I relate any of this to φ although at least now there appears to be some modulo arithmetic going on.

My contribution to the Lisbon debate.

This time around I have neither the time nor the energy to do very much. However I would really love to have a wind-driven rotating sign to express my opinion on the level of the debate. The kind that often stand outside shops for ice cream etc. Since that isn't going to happen I tried my hand at an animated GIF:

I'm a 35 year old man trapped in the body of...

... a 35 year old man. Basically I have no excuse or no reason to plead a special case. Well, my 2 small kids seem to sleep less than some others but not outside the ranges given in baby books. I just can't do things like I could before. I used to play a lot of soccer which made me quite fit (self-praise is no praise). When I played again a few weeks ago I was in a steaming heap after 10 minutes. Some of it is lack of exercise some is just getting older. I hardly drink any more because I just hate losing time to hangovers and I don't have to drink very much to get one anymore. It was nice be able to abuse my body and not pay the price in my teens and twenties (self-abuse is no abuse!).

What's the point? Nothing much. Just when I changing my socks I was playing with the phrase "An X trapped in the body of a Y" and I realised that if I claimed to be different on the inside and the outside I'd be kidding myself.

To vastly over-generalise and ignore changing life-circumstances, as people age they stop doing some things. I don't think they stop because they have lost the desire to do them but because they have lost the ability to do them. Of course that may then impact the desire or simply cause the focus to shift to new things which can be done but I think you don't stop wanting to do anything simply because you're older. Which probably explains the childishness of many people (myself included).

In Soviet Canada, healthcare system pays for your problems.

Their nearest neighbour makes it very hard to find a way to exclusively make fun of Canada...

Smalltalk's become() in python

Posting this here because blogger's sucky comment system won't let me post formatted code in a comment on this post. This is an implementation of Smalltalk's become() in python. It will not work on strings, int etc. but otherwise is identical

#! /usr/bin/python def become(a, b): swap(a, b, "__class__") swap(a, b, "__dict__") def swap(a, b, attr): tmp = getattr(a, attr) setattr(a, attr, getattr(b, attr)) setattr(b, attr, tmp) class Animal(object): def __init__(self, name): self.name = name class Dog(Animal): def Cry(self): print "%s says woof" % self.name class Sheep(Animal): def Cry(self): print "%s says baa" % self.name a = Dog("rover") b = Sheep("shaun") c = a a.Cry() c.Cry() become(a, b) a.Cry() c.Cry()

This prints

rover says woof rover says woof shaun says baa shaun says baa

Note how both a and c are now sheep. To do the same thing in perl you monkey around with bless and resetting all the hash entries, it's a bit uglier.

Answer to 1 of the 2 puzzles and a new puzzle.

I take Nicole's comment to mean she gives up, although Nicole, it turns out that your comment has a deep relation to this problem and raises a new question.

To find out on average how many items are left unmoved by a random permutation, you can consider every permutation and how many are left unmoved by each, add them all up and divide by the total number of permutations. To avoid mathsy notations I'm going to write a tiny program that calculates this total.

total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for p in perms: for i in 1..N: if p(i) == i: total = total + 1

Now, here's the key to this problem - swap the loops. The final answer stays the same we just end up adding things up in a different order.

total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for i in 1..N: for p in perms: if p(i) == i: total = total + 1

So now what we're doing is looping over the items and counting how many permutations leave that item in place and that's something we can work out. The number of permutations that fix a given item is (N-1)! (where ! is factorial) because when you fix 1 item, you're left with N-1 other items which you move around however you like so it's just the number of permutations of N-1 items which is (N-1)!. So now the code can be just

total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for i in 1..N: total = total + (N-1)!

which is just adding (N-1)! N times. That's N x (N-1)! which is just N!. Now we have to divide that by the total number of permutations which is also N! to get an average of 1.

You can also get to this answer by drawing a grid with all the permutations across the top and all the items down the side. You put a tick in a cell in the grid if the permutation on the top leaves the item on the left unmoved. Now count the ticks. Doing it column by column is hard but doing it row by row is easy because there will be (N-1)! ticks in each row.

So the conclusion is that if you do a perfect shuffle of a deck of cards, on average 1 card will end up in the same places as before.

So where does Nicole's comment come in? I knew it was Ralph Wiggum who said it but I couldn't remember the context turns out. I found it here. It's

  Lisa: Hey Ralph, want to come with me and Alison to play "Anagrams"?
Alison: We take proper names and rearrange the letters to form a
        description of that person.
 Ralph: My cat's breath smells like cat food.

and what we've just shown is that given a random anagram, you'd expect 1 letter on average to end up in the same place - well kind of, that's only true if there are no repeated letters. I hadn't thought of this in terms of anagrams before and that adds a nice twist in terms of repeated letters. Thanks Nicole!

So the new puzzle is - given a string written in scrabble tiles (it can have repeated letters), if you mess up the tiles and make a new string at random, how many letters do you expect to be in the same place as before?

No code has no bugs.

So the more no code you have, the more no bugs you have.