tag:blogger.com,1999:blog-264226589944705290.post7964823523066068878..comments2023-11-05T03:45:25.001-08:00Comments on God Plays Dice: The Calkin-Wilf shirtMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-264226589944705290.post-27937062992002424272010-04-13T14:41:09.594-07:002010-04-13T14:41:09.594-07:00If you carry out Euclid's algorithm slowly, yo...If you carry out Euclid's algorithm slowly, you get a sequence of "right" and "left" steps. If you write the steps in one order, you get the Calkin-Wilf tree. If you reverse the order of the steps, you get the Stern-Brocot tree. For example, the fraction in position 010011 in one is in position 110010 in the other, where the length of the string tells you which row you are in. <br /><br />Since each row of the Stern-Brocot tree is increasing, you can also sort a row of the Calkin-Wilf tree to get the corresponding row of the Stern-Brocot tree.<br /><br />The Stern-Brocot tree doesn't have the property that the denominator of one fraction is the numerator of the next.<br /><br />Douglas ZareOLZhttps://www.blogger.com/profile/18161327623560940233noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-65029151163195100892010-03-17T20:14:08.250-07:002010-03-17T20:14:08.250-07:00Here's something similar I can say about the n...Here's something similar I can say about the number of ways to write n as a sum of powers of 3, where no power of 3 can be used more than three times. It's <a href="http://www.research.att.com/~njas/sequences/A054390" rel="nofollow">A054390</a>, and satisfies g(3n)=g(n-1)+g(n) and g(3n+1)=g(3n+2)=g(n).<br />Let T be a tree in which each node has 3 children, the root is numbered 1 and each node's children are ordered Left, Center, Right (L,C,R) and numbered 3n-1, 3n and 3n+1 respectively, and we associate with node number n the ordered pair (g(n-1),g(n)) and the rational number g(n-1)/g(n). Then if g(n-1)=r and g(n)=s, then node n has r/s and from the recurrence for g(n) the children L,C,R have r/r, r/(r+s) and (r+s)/s respectively. The C and R children of the node have the same relation to the parent as in the Calkin-Wilf tree, so if we take the subtree S of nodes for which the path from the root passes through only C and R children, it is exactly the C-W tree. The nodes of S are the nodes with numbers that have base-3 representations containing no 2s, and if we read them as binary numbers then it's also the natural numbering of nodes in the C-W tree.<br />Any L child has (r,r), so the subtree U that has L at the root and contains all of its descendants is a scaled copy of T in the sense that, for a node in T that has the ordered pair (a,b), the corresponding node in U has (r*a,r*b) and so both are associated with the same rational number.Zanderhttps://www.blogger.com/profile/03349792890949578936noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-53669985347747315412010-03-16T12:40:50.521-07:002010-03-16T12:40:50.521-07:00Oh snap. I'm going to have to get one of thos...Oh snap. I'm going to have to get one of those shirts.<br /><br />Jeffrey: is it? What's the disguise?Brenthttps://www.blogger.com/profile/14440861005012132386noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-43357548576736258682010-03-14T23:59:59.930-07:002010-03-14T23:59:59.930-07:00I heard about it from Yorgey's blog article, b...I heard about it from Yorgey's blog article, but I think he had not yet moved to Philadelphia then. <br /><br />So yes, it was a coincidence.<br /><br />Have you seen Wilf's appalling paper about the Coupon Collector problem?Mark Dominushttps://www.blogger.com/profile/17698641253266210249noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-33975880057245453162010-03-14T08:21:41.447-07:002010-03-14T08:21:41.447-07:00It's the Stern-Brocot tree in disguise.It's the <a href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree" rel="nofollow">Stern-Brocot tree</a> in disguise.Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.com