recursion « The Math Less Traveled

Archive for the ‘recursion’ Category

The hyperbinary sequence and the Calkin-Wilf tree

Sunday, October 18th, 2009

Recounting the Rationals

And now, the amazing conclusion to this series of posts on Neil Calkin and Herbert Wilf’s paper, Recounting the Rationals, and the answers to all the questions about the hyperbinary sequence. Hold on to your hats!

The Calkin-Wilf Tree

First, recall the Calkin-Wilf tree, defined as follows: the “root” of the tree is the fraction 1/1, and every node labeled i/j in the tree has two “children”, with the left child labeled i/(i+j) , and the right labeled (i+j)/j . Here’s a picture of the first four levels of the tree (of course, the tree is infinite):

Now wait just one minute… those numbers look familiar! Let’s list those fractions in order, one level at a time, from left to right:

$\displaystyle \frac 1 1, \frac 1 2, \frac 2 1, \frac 1 3, \frac 3 2, \frac 2 3, \frac 3 1, \frac 1 4, \frac 4 3, \frac 3 5, \frac 5 2, \frac 2 5, \frac 5 3, \frac 3 4, \frac 4 1 \dots$

That’s right, it’s the hyperbinary sequence! In particular, the numerators are the hyperbinary sequence starting at index 0, and the denominators follow the same sequence, offset by one.

…but why?! The Calkin-Wilf tree is defined by a recursive rule for manipulating fractions, and the hyperbinary sequence is defined in terms of ways to write numbers as sums of powers of two… it certainly isn’t a priori obvious why these should have anything to do with each other!

Labelling the CW-tree

Let’s label the nodes in the Calkin-Wilf tree with positive integers, starting with 1 at the root and proceeding in order by levels, from left to right. This means that the fraction at node is h(n-1)/h(n) —at least, that’s what we’re trying to prove! Here’s an illustration of our numbering scheme:

Now, what do you notice about the relationship between the label on a node and the labels on its children? It’s not too hard to guess the pattern: the left child of the node labelled is labelled , and the right child is labelled 2k+1 . How can we prove this?

Well, it’s certainly true for the root note: it’s labelled 1, and its children are labelled 2 and 3. Now we note that if the pattern holds for the node immediately preceding node —that is, the children of node k-1 are 2k-2 and 2k-1 —then the children of node come immediately after the children of k-1 , so they are numbered and 2k+1 . If you think about it, this is true regardless of whether k-1 and are on the same level, or k-1 is the end of one level and is the beginning of the next.

We can think of labelling each edge of the Calkin-Wilf tree with either a 0 or a 1: 0 for left edges, and 1 for right edges. Then taking all the zeros and ones along the path from the root to any node and sticking an extra 1 at the beginning gives us the label of that node in binary! For example, the path that goes left, left, right corresponds to 0, 0, 1, and adding an extra 1 to the front gives us 1001–which is indeed the binary representation of 9!

So, is it really true that the fraction at node is always h(n-1)/h(n) ? It is indeed, and we now have the tools we need to see why. First of all, the root node of the tree—that is, node 1—is (by definition) 1/1 , which is indeed h(0)/h(1) . Next, suppose that the fraction at node is h(k-1)/h(k) ; we need to show that the fraction at the left child (which is node ) is h(2k-1)/h(2k) , and the fraction at the right child is h(2k)/h(2k+1) . But this is now easy: by the way the Calkin-Wilf tree is defined, the left child is

$\displaystyle\frac{h(k-1)}{h(k-1) + h(k)} = \frac{h(2k-1)}{h(2k)}.$

The equality, of course, follows directly from the recurrence relation for the hyperbinary sequence! Likewise, the right child is

$\displaystyle \frac{h(k-1) + h(k)}{h(k)} = \frac{h(2k)}{h(2k+1)}.$

Solving the $\phi(n)$ mystery

As pointed out by JM, this connection with the Calkin-Wilf tree is exactly what we need to prove Fergal Daly’s conjecture about the number of primary occurrences of any given number.

We defined a primary occurrence simply as a number at an even position in the hyperbinary sequence. Of course, even-labelled nodes in the Calkin-Wilf tree are exactly the ones which are left children, and so the primary occurrences are the denominators of left children (equivalently, the numerators of right children). Also, since left children are always of the form i/(i+j) , left children always have denominators bigger than their numerators. Finally, as you may recall, we showed earlier that every positive rational number occurs somewhere in the Calkin-Wilf tree, in lowest terms, exactly once.

Putting this all together: each primary occurrence of corresponds to a fraction m/n in the Calkin-Wilf tree, where m < n . And since every fraction occurs exactly once in lowest terms, there is exactly one such fraction m/n for each positive integer m < n which is relatively prime to . Of course, by definition, there are $\phi(n)$ such numbers, so this is the proof of Fergal’s conjecture! There are exactly $\phi(n)$ primary occurrences of , since that’s how many reduced fractions there are between 0 and 1 which have a denominator of .

Computing primary occurrences

The connection with the Calkin-Wilf tree also allows us to compute $h^{-1}$ —that is, given any , we can efficiently (in $O(n \log n)$ time) compute all the primary occurrences such that h(k) = n !

How does this work? Well, if you remember, the Euclidan Algorithm gives us a way to find our way up the Calkin-Wilf tree from any starting fraction. Combining this with the relationship we discovered earlier between the label on a node and the labels on its children allows us to compute the label on the node where we started.

As an example, let’s compute one of the primary occurrences of 5. In particular, let’s do the one that corresponds to the fraction 3/5 . Since 3 is smaller than 5, 3/5 must be the left child of 3/(5-3) = 3/2 . 3 is bigger than 2, so 3/2 is the right child of (3-2)/2 = 1/2 . Finally, 1/2 is the left child of 1/1 . Now we can work backwards: 1/1 is node ; 1/2 is to the left, so it’s node 2*1 = 2 ; 3/2 is to the right of that, so it’s node 2*2 + 1 = 5 ; and 3/5 is to the left again, so it’s node 2*5 = 10 . Therefore h(10) = 5 is a primary occurrence of 5! We can also think of this more succinctly by recalling that paths in the Calkin-Wilf tree correspond to binary representations of the labels. So we can run the Euclidean Algorithm, getting a zero or one at each step, and then reverse them and put an extra 1 at the beginning to get the binary representation of the primary occurrence. To be more precise:

Start with the pair where is relatively prime to . Call the current pair of numbers .
Given , if then write $(a,b) \stackrel{0}{\to} (a,b-a)$ . Otherwise write $(a,b) \stackrel{1}{\to} (a-b,b)$ .
Repeat step 2 until reaching .
Read off the primary occurrence of by prefixing 1 to the reverse of the binary digits written over the arrows.

All of this leads to the following (somewhat mind-blowing) observation: the position of each primary occurrence of in the hyperbinary sequence is a proof (encoded in binary) that is relatively prime to the number that comes immediately before it.

To tie this all together, here’s a little Haskell program I wrote to compute primary occurrences:

import System.Environment (getArgs)
import Control.Monad (forM_)
import Data.Maybe (catMaybes)
import Data.List (sort)

-- Find a fraction in the Calkin-Wilf tree.  findCW a b computes the
-- location of a/b in the Calkin-Wilf tree, or returns Nothing if a
-- and b are not relatively prime.
findCW :: Integer -> Integer -> Maybe Integer
findCW 1 1 = Just 1
findCW a b | a < b  = left  `fmap` findCW a (b-a)
           | a > b  = right `fmap` findCW (a-b) b
           | a == b = Nothing

left  x = 2*x
right x = 2*x + 1

-- Find the primary occurrences of n.
primaryOccs :: Integer -> [Integer]
primaryOccs n = sort . catMaybes $ [ findCW m n | m <- [1..n] ]

main :: IO ()
main = do (from:to:_) <- getArgs
          forM_ [read from..read to] $ \i -> do
            putStr $ show i ++ ": "
            putStrLn . unwords . map show . primaryOccs $ i

If there’s interest, I could write another post explaining how this program works in a bit more detail, but hopefully you can mostly understand what it’s doing from the preceding discussion. Let’s check that it works:

[brent@archimedes:~/teaching/mlt/hyperbin]$ ./prim-occs 2 16
2: 2
3: 4 6
4: 8 14
5: 10 12 16 30
6: 32 62
7: 18 22 24 28 64 126
8: 20 26 128 254
9: 34 46 48 60 256 510
10: 38 56 512 1022
11: 36 40 54 58 66 94 96 124 1024 2046
12: 44 50 2048 4094
13: 42 52 70 78 112 120 130 190 192 252 4096 8190
14: 68 80 110 122 8192 16382
15: 72 118 258 382 384 508 16384 32766
16: 92 98 134 158 224 248 32768 65534

Yup, looks good! And to show that it really is efficient, let’s use it to compute the primary occurrences of 1000 (yes, all 400 of them!):

[brent@archimedes:~/teaching/mlt/hyperbin]$ ./prim-occs 1000 1000
1000: 39770 42278 56024 58532 68396 70568 71444 75674 76688 85046 86480 92576 104030
... 386 more primary occurrences...
1071508607186267320948425049060001810561404811705533607443750388370351051124936
1224931983788156958581275946729175531468251871452856923140435984577574698574803
9345677748242309854210746050623711418779541821530464749835819412673987675591655
43946077062914571196477686542167660429831652624386837205668069374

On my computer this runs in about 0.03 seconds. Sweet! Note that the position of the final primary occurrence of 1000 has 303 digits–that’s approximately one centillion. I certainly wouldn’t want to go through the first one centillion numbers in the hyperbinary sequence looking for 1000 by hand, would you?

More hyperbinary fun

Monday, September 28th, 2009

Recounting the Rationals

When I originally posed Challenge #12, a certain Dave posted a series of comments with some explorations and partial solutions to part II (the hyperbinary sequence). Although I gave the “solution” in my last post, no solution to any problem is ever the last word—there’s always more to explore, more connections to see! It’s worth taking another post to explore some of Dave’s discoveries and conjectures, and how they connect to my last post. I’ve used different notations, made up some terms, tried to simplify things where possible, and so on, but all the ideas in this post are fundamentally Dave’s.

First things first

Dave first noticed that

h(2^k - 1) = 1

for all $k \geq 0$ . I noted this in my previous post as well, but said only that this is “apparent” from thinking about the recursive construction I described. However, it’s worth going through a proof of this more formally; it’s a good example of a proof by induction. First, let’s recall the recurrence relation that defines the hyperbinary sequence:

$\begin{align*}h(0) &= 1 \\ h(2n+1) &= h(n) && \text{(O)}\\ h(2n+2) &= h(n+1) + h(n) && \text{(E)}\end{align*}$

Now we can show that h(2^k - 1) = 1 for $k \geq 0$ . First, the base case: when k=0 , h(2^0 - 1) = h(0) = 1 ; check!

Now, let’s suppose that h(2^k - 1) = 1 for some particular $k \geq 0$ ; this is called the inductive hypothesis, which I will abbreviate as IH. we want to show that $h(2^{k+1} - 1) = 1$ as well. $2^{k+1} - 1$ is obviously odd, so we want to apply rule (O). The only trick is to get it into the right form first:

$\begin{align*}h(2^{k+1} - 1) &= h(2^{k+1} - 2 + 1) && \text{\{ arithmetic \}}\\ &= h(2(2^k - 1) + 1) && \text{\{ factor \}}\\ &= h(2^k - 1) && \text{\{ rule (O) \}} \\ &= 1 && \text{\{ IH \}}\end{align*}$

Presto! Since the thing we wanted to show is true when k=0 and is true for k+1 whenever it is true for , by induction it must be true for all $k \geq 0$ .

Second things, third things…

But Dave then went on to notice that this sort of pattern isn’t unique to 1. For example,

$h(3 \cdot 2^k - 1) = 2$

for $k \geq 0$ , and

$h(5 \cdot 2^k - 1) = h(7 \cdot 2^k - 1) = 3$

also for $k \geq 0$ . Dave conjectured that this generalizes, and indeed it does: most generally, we can say that

$h(p \cdot 2^k - 1) = h(p - 1)$

for $k \geq 0$ . That is, once a certain number occurs at position p - 1 , it will keep occurring in a regular pattern after that, at every position of the form $p \cdot 2^k - 1$ . Note that h(2^k - 1) = 1 is a special case with p = 1 .

Why is this? Intuitively, it’s because of the “copying”—the blue numbers in my previous post. Once a number occurs, it will keep getting copied, but with the distance between the copies doubling each time. But again, this is worth proving formally. I’ll let you do this one—the proof by induction is similar to the proof above!

But why do occurrences of 1 correspond to p = 1 , and occurrences of 2 to p = 3 , and occurrences of 3 to p = 5 and p = 7 , and so on? Are there any patterns to be found here? This is what Dave explored next; let’s follow.

Primary occurrences and the inverse of h

Let’s think a little more about this equation $h(p \cdot 2^k - 1) = h(p - 1)$ . Let’s suppose that is odd (if it isn’t, we can always take another factor of two out of it to combine with the 2^k ). Notice that $p \cdot 2^k - 1$ is always odd, except when k = 0 (in which case $p \cdot 2^k - 1 = p - 1$ , which is even). Moreover, we can always write any odd number in the form $p \cdot 2^k - 1$ , where is odd: just add one, and factor out as many copies of 2 as possible. For example, $11 = 12 - 1 = 3 \cdot 2^2 - 1$ .

This means that if is any odd number, we can write it in the form $q = p \cdot 2^k - 1$ , and so h(q) = h(p-1) : that is, every odd position in the hyperbinary sequence is just copied from an earlier even position. Of course, this can also be seen from the recursive construction in my previous post; but now we have really proved it! And what about the even positions? The values of the hyperbinary sequence at even positions are obtained by adding, rather than copying. If occurs at an even position, we will call it a primary occurrence of .

The nice thing about primary occurrences is that (a) there are only finitely many primary occurrences of any particular (challenge: prove this!), and (b) once we know the positions of the primary occurrences of , we know the positions of all the occurrences of : they are at positions of the form $p \cdot 2^k - 1$ , where p - 1 is a primary occurrence.

So, given , can we find all its primary occurrences? Essentially we are asking if we can compute $h^{-1}$ (by which I mean the inverse relation of ; since is not injective its inverse is obviously not a function), but leaving out non-primary occurrences since we can easily find those from primary ones. Let’s start by making a table with some small values of :

n	Primary occurrences
1	0
2	2
3	4, 6
4	8, 14
5	10, 12, 16, 30
6	32, 62
7	18, 22, 24, 28, 64, 126
8	20, 26, 128, 254
9	34, 46, 48, 60, 256, 510
10	38, 56, 512, 1022
11	36, 40, 54, 58, 66, 94, 96, 124, 1024, 2046
12	44, 50, 2048, 4094
13	42, 52, 70, 78, 112, 120, 130, 190, 192, 252, 4096, 8190
14	68, 80, 110, 122, 8192, 16382
15	72, 118, 258, 382, 384, 508, 16384, 32766
16	92, 98, 134, 158, 224, 248, 32768, 65534

Do you see any patterns? If so, can you prove them by induction? I’ll talk about a few in my next post. But I still don’t know whether there’s an effective way to compute $h^{-1}(n)$ !

« Previous in series | Next in series »

Tags: hyperbinary, induction
Posted in challenges, induction, pattern, proof, recursion, sequences, solutions | 11 Comments »

Challenge #12 solution, part III

Thursday, April 24th, 2008

And now for the solution to problem #3 from Challenge #12, which asked: how many ways are there to write a positive integer n as a sum of powers of two, with no restrictions on how many powers of two may be used?

(more…)

Posted in counting, pattern, recursion, sequences, solutions | 1 Comment »

Recounting the Rationals, part III

Thursday, January 24th, 2008

Recounting the Rationals

First, a quick recap: continuing an exposition of the paper Recounting the Rationals, we’re investigating the tree of fractions shown below (known as the Calkin-Wilf tree), which is constructed by placing 1/1 at the root node, and giving each node i/j the two children i/(i+j) (on the left) and (i+j)/j (on the right). Here are the first four levels of the tree (of course, it has infinitely many levels):

The Calkin-Wilf tree

In my last post I claimed that this tree has a number of remarkable properties; in this and subsequent posts I plan to show exactly why these properties are true, since for the most part they have relatively simple explanations—although that in no way makes them any less remarkable!

Today let’s begin by tackling the first property I claimed, namely, that every single positive rational number occurs somewhere in this tree. How can we prove this?

First, notice that given any rational in the tree, there is any easy way to tell whether it is the left or right child of its parent. (Can you figure it out before reading on?)

Since left children are always of the form i/(i+j) , they will always have a denominator greater than their numerator ( i+j > i , since j is positive); and vice versa for right children, which are of the form (i+j)/j and consequently have a numerator greater than their denominator. So, given some fraction in the tree m/n , to decide whether it is a left or right child, just compare m and n. If n is greater, it is a left child, and its parent is m/(n-m) ; otherwise, it is the right child of (m-n)/n .

For example, if we start with 5/3, we see that 5 > 3, so 5/3 must be the right child of (5-3)/3 = 2/3; 2/3, in turn, has a greater denominator, so it is the left child of 2/(3-2) = 2/1, and 2/1 is the right child of 1/1.

Moving up the Calkin-Wilf tree starting from 5/3

In fact, it is easy to see that I’ve just described a simple procedure for finding your way up the tree, starting from any positive rational in lowest terms. At each step, just take the numerator and denominator, and subtract the smaller from the larger. (They can never be equal until we get to 1/1, since we start out with something in lowest terms.) But how do we know that we will eventually reach 1/1 this way? Well, both the numerator and the denominator are always positive during this process (they start out positive, and you can’t get something negative by subtracting something smaller from something larger), and one of them gets smaller at every step. Think about this for a minute. They must eventually reach 1/1 — there’s nowhere else for them to go!

Well, if we can find a path up to 1/1 from any reduced positive rational, every such rational must be in the tree in the first place! You may also note that since we have no choice at each step, there is exactly one path from any rational up to the root of the tree — which means that each reduced rational occurs in only one place in the tree; there are no duplicates.

Now, technically, one thing we haven’t shown is that there aren’t any unreduced rationals which sneakily sneak in along with the reduced ones; but that’s not too hard to show, and I’ll talk about that next time.

There are several other interesting things going on here — for example, the path from any reduced rational up to the root of the tree corresponds directly to using the Euclidean Algorithm to prove that the rational is, in fact, reduced! And if you interpret the lefts and rights in the path as zeros and ones in binary… but I’m getting ahead of myself, that’s for a later post. =)

« Previous in series | Next in series »

Posted in number theory, pattern, proof, recursion | 8 Comments »

Recounting the Rationals, part II (fractions grow on trees!)

Monday, January 7th, 2008

Recounting the Rationals

Recounting the Rationals, part I
Recounting the Rationals, part II (fractions grow on trees!)
Recounting the Rationals, part III
Recounting the Rationals, part IV
Recounting the Rationals, part IVb: the Euclidean Algorithm
Challenge #12: sums of powers of two
Challenge #12 solution, part II
More hyperbinary fun
Hyperbinary conjecture seeking proof for a good time, long walks on the beach
The hyperbinary sequence and the Calkin-Wilf tree

Today I’d like to continue my exposition of the paper “Recounting the Rationals”, which I introduced in a previous post. Recall that our goal is to come up with a “nice” list of the positive rational numbers — where by a “nice” list we mean one which:

is easy to describe,
includes every rational number,
exactly once,
in lowest terms,
at a finite index.

Sounds like a pretty tall order! But it’s possible, as Calkin and Wilf show. So, without further ado… did you know that fractions grow on trees? Sure they do! Here’s one:

This is a tree of fractions defined by the following simple rules:

The fraction at the top (the “root”) of the tree is 1/1.
Each fraction in the tree has two “children” (that is, fractions underneath it connected by “branches”): to the left is ; to the right is .

For example, starting at the top of the tree, we have 1/1 = i/j , so rule 2 says that the left child should be 1/(1+1) = 1/2 , and the right child should be (1+1)/1 = 2/1 . Likewise, the children of 1/2 are 1/(1+2) = 1/3 and (1+2)/2 = 3/2 , and so on.

Pretty simple, right? The picture above only shows the first four levels of the tree, but it’s clear how to continue extending the tree downwards as far as you’d like (for example, the first two rationals on the next level are 1/5 and 5/4). Now, guess what?

Every positive rational number occurs somewhere in this tree.
There are no duplicates: each rational occurs exactly once.
Every rational in the tree is in lowest terms.
If you list out the rationals in this tree in order by level (that is, 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4…), the denominator of each rational in the list is equal to the numerator of the next.
The nth integer in the list of denominators (1, 2, 1, 3, 2, 3, 1, 4, 3, 5, …) is the number of hyperbinary representations of n, that is, the number of ways to write n as a sum of powers of two, where at most two copies of each power of two are allowed.

Wow! What an amazing tree. And all that just from those two simple rules! It should be clear that this is an answer to our original goal: just listing the rationals in the tree level-by-level gives us a list of the positive rationals with all the properties we were hoping for. But there’s a lot more interesting stuff here as well. Next time I’ll start talking about why each of these properties is true — but in the meantime, you may want to try figuring some of them out for yourself! They are all consequences of the two simple rules we used to define the tree.

(Hint for #1, #2, and #3: rule 2 tells us how to move down the tree, but with a little cleverness, you should be able to figure out how to move up the tree as well. For example, assuming that 43/19 occurs somewhere in the tree, rule 2 tells us that 43/62 and 62/19 are below it; but can you figure out what fraction must be above it?)

« Previous in series | Next in series »

Posted in infinity, number theory, pattern, recursion, sequences | 19 Comments »

The Math Less Traveled

Archive for the ‘recursion’ Category

The hyperbinary sequence and the Calkin-Wilf tree

Recounting the Rationals

The Calkin-Wilf Tree

Labelling the CW-tree

Solving the $\phi(n)$ mystery

Computing primary occurrences

Further Reading

More hyperbinary fun

Recounting the Rationals

First things first

Second things, third things…

Primary occurrences and the inverse of h

Challenge #12 solution, part III

Recounting the Rationals, part III

Recounting the Rationals

Recounting the Rationals, part II (fractions grow on trees!)

Recounting the Rationals

Pages

Archives

Categories

Archive for the ‘recursion’ Category

The hyperbinary sequence and the Calkin-Wilf tree

Recounting the Rationals

The Calkin-Wilf Tree

Labelling the CW-tree

Solving the mystery

Computing primary occurrences

Further Reading

More hyperbinary fun

Recounting the Rationals

First things first

Second things, third things…

Primary occurrences and the inverse of h

Challenge #12 solution, part III

Recounting the Rationals, part III

Recounting the Rationals

Recounting the Rationals, part II (fractions grow on trees!)

Recounting the Rationals

Solving the $\phi(n)$ mystery