The Amazing ‘fusc’ Function

I recently encountered a collection of related articles regarding an amazing explicit enumeration of the non-negative rational numbers. Whilst experimenting with the mathematical constructs described, I made some discoveries of my own (which I doubt are new, but I have not found them described elsewhere).

Below, are the references and links to those articles. They’re all worth a read.

The Stern–Brocot tree is a binary tree of positive rational numbers. Each rational number appears (in its simplest form) in the tree exactly once [which is amazing]. Child nodes are generated from ancestor nodes by taking mediants of the two horizontally-nearest ancestor nodes. As a result, the tree has the rationals in in-order; in particular the numbers in each row are ordered by value. The first few rows contain (without attempting to draw the tree):

1/1

1/2, 2/1

1/3, 2/3, 3/2, 3/1

1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1

(Complete sequences of mediants have the amazing property that consecutive pairs of values a/b and c/d are always such that bc-ad=1.)

The Calkin–Wilf tree is related. Again, it is a binary tree of positive rational numbers, each appearing exactly once [again, amazing]. Child nodes are generated from a much simpler rule from just the parent node: r/s has children r/(r+s) and (r+s)/s. The first few rows contain:

1/1

1/2, 2/1

1/3, 3/2, 2/3, 3/1

1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1

Notice that in the Calkin–Wilf tree, consecutive pair of values a/b and c/d in a row are always such that b=c.

One of my discoveries is: consider any row, say row N (counting from 0), of the Calkin–Wilf tree, and index them with their horizontal position 0 to 2^{N}-1. Now, consider the N-bit binary representation of the indices, and bit-reverse them (so 0001011 becomes 1101000). Now sort the values by index. The values are now in order, and as in the corresponding row of the Stern–Brocot tree. Thus, to convert between Stern–Brocot and Calkin–Wilf trees, just bit-reverse the indices within each row.

Next, here’s Dijkstra’s fusc function, also known as Stern’s diatomic series or sequence:

a_{0} = 0

a_{1} = 1

a_{2k} = a_{k}

a_{2k+1} = a_{k} + a_{k+1}

— note that this case with k = 0 implies the first rule

The sequence (a_{i})_{i \ge 0} = a_0, a_1, a_2, \ldots starts:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, …

The next amazing thing is that the sequence of ratios q_{i} = a_{i}/a_{i+1} of consecutive elements of the fusc sequence contains all the non-negative  rational numbers exactly once. The values produced are 0/1 followed by the rows of the Calkin–Wilf tree in turn and in order.

0/1, 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, …

From the references, the follow recurrence relations and other formulae were given (sometimes indirectly):

  • q_{2i} = \dfrac{q_{i}}{1+q_{i}}
    equivalently: \dfrac{1}{q_{2i}} = \dfrac{1}{q_{i}} + 1
  • q_{2i+1} = q_{i} + 1

From these, the following may be deduced:

  • q_{i} = \dfrac{q_{2i}}{1-q_{2i}}
    equivalently: \dfrac{1}{q_{i}} = \dfrac{1}{q_{2i}} - 1
  • q_{i} = q_{2i+1} - 1

Another remarkable formula given is:

  • q_{i+1} = \dfrac{1}{1 + 2 \lfloor q_{i-1} \rfloor - q_{i-1}}

Writing a_{i}/b_{i} = q_{i} (where (a_{i}, b_{i}) = 1, optionally):

  • a_{i+1} = b_{i}
  • b_{i+1} = (b_{i} - a_{i}) + 2 \lfloor a_{i} \rfloor_{b_{i}}

where I define the notation

\lfloor x \rfloor_{m} = m \lfloor x/m \rfloor

for the function that rounds down to the nearest multiple of m.

To invert the above formula, we find that we need to solve

2 \lfloor a_{i-1} \rfloor_{a_{i}} - a_{i-1} = b_{i} - a_{i}

for a_{i-1}. The solution is:

  • a_{i-1} = 2 \lceil b_{i} \rceil_{a_{i}} - (a_{i} + b_{i})
  • b_{i-1} = a_{i}

where, similarly,

\lceil x \rceil_{m} = m \lceil x/m \rceil

From which we obtain:

q_{i-1} = 2 {\left\lceil \dfrac{1}{q_{i}} \right\rceil} - {\dfrac{1}{q_{i}}} - 1

Given 0 < q \in {\mathbb Q}, the n such that q_{n} = q may be found by n = f(q) where:

f(1) = f(1/1) = 1

if q < 1 then f(q) = 2f \left( \dfrac{q}{1-q} \right)

if q > 1 then f(q) = 2f( q - 1 ) + 1

Yet another amazing formula is:

a_n = \displaystyle\sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} \binom{(n-1)-k}{k}_{2}

where

\dbinom {n} {k}_m = \left\{ \dbinom {n} {k} \right\}_m

where

\{k\}_m = k - \lfloor k \rfloor_m

is the m-multiple fraction part, or m-modulus or m-remainder, where

\lfloor k \rfloor_{m} = m \lfloor k/m \rfloor

is the m-floor, as defined above.

For more information, see the references below.

References

[1] Stern–Brocot tree, Wikipedia

[2] Calkin–Wilf tree, Wikipedia

[3] EWD570, Edsger W. Dijkstra, “An exercise for Dr. R. M. Burstall”

[4] EWD578, Edsger W. Dijkstra, “More about the function “fusc” (A sequel to EWD570)”

[5] Stern’s Diatomic [Sequence], Mathworld

Note that some of these references differ from each other in the indexing of sequences.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: