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.