Republic of Mathematics blog

Spotting patterns and finding explanations: Dijkstra’s fusc function

Posted by: Gary Ernest Davis on: May 18, 2011

Edsger Wybe Dijkstra

Edsger Dijkstra named the integer valued function, fusc, of a non-negative integer variable, as follows:

\textrm{fusc}(0)=0,

\textrm{fusc}(1)=1,

\textrm{fusc}(2n)=\textrm{fusc}(n) and

\textrm{fusc}(2n+1)=\textrm{fusc}(n)+\textrm{fusc}(n+1)

Dijkstra’s writings on fusc can be found at the Edgar W. Dijkstra Archive (EWD 578).

The values of fusc can be computed in any decent programming language (one that has a built-in routine for recognizing odd and even integers – otherwise one has to define such a routine, or include it in the definition of fusc).

Here is a simple Mathematicaâ„¢ definition that allows us to compute fusc easily:

fusc[0] = 0;
fusc[1] = 1;
fusc[n_] := If[Mod[n, 2] == 0, fusc[n/2], fusc[(n – 1)/2] + fusc[(n + 1)/2]]

Here are the first 100 values of fusc:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 11, 9, 16, 7

and a plot of \textrm{fusc}(n) versus n for 0\leq n \leq 1000:

Spotting a pattern

Among other properties of fusc, Dijstrka noticed that \textrm{fusc}(n) is a multiple of 2 exactly when n is a multiple of 3.

For example, we see that for multiples of 3 up to 99, the value of fusc is a multiple of 2:

n = multiple of 3 fusc(n)
0 0
3 2
6 2
9 4
12 2
15 4
18 4
21 8
24 2
27 8
30 4
33 6
36 4
39 10
42 8
45 12
48 2
51 12
54 8
57 10
60 4
63 6
66 6
69 14
72 4
75 18
78 10
81 14
84 8
87 18
90 12
93 16
96 2
99 16

Equally, for values of n up to  100 that are not multiples of 3, \textrm{fusc}(n) is not a multiple of 2.

Explaining a pattern

This empirical observation requires explanation.

Mathematics thrives on spotting and explaining patterns, especially unexpected patterns, for which there is no immediate reason why they should hold.

To begin looking for a reason for this empirical observation let’s assume that n is a multiple of 3.

n is either even or odd, so let’s assume first that it is even.

Then n=6p for some non-negative integer p.

This gives us \textrm{fusc}(n)=\textrm{fusc}(6p)=\textrm{fusc}(6p/2)=\textrm{fusc}(3p).

Now when p\geq 1, 3p is a smaller multiple of 3 than is 6p, so if we assume, inductively, that for all smaller multiples of 3 we already know the value of fusc is a multiple of 2, then we know that \textrm{fusc}(n) is also a multiple of 2.

What if n\geq 1 is a multiple of 3 and is odd?

Then =6p+3 for some non-negative integer p, so \textrm{fusc}(n)=\textrm{fusc}(\frac{n-1}{2})+\textrm{fusc}(\frac{n+1}{2}) =\textrm{fusc}(3p+1)+\textrm{fusc}(3p+2)

Now, 3p+1\textrm{ and } 3p+2 are smaller than n, so we can assume we already know their fusc values, but because these numbers are not multiples of 3, we can assume that we already know their fusc values are not multiples of 2.

In other words, we already know that \textrm{fusc}(3p+1) is odd and \textrm{fusc}(3p+2) is odd, so their sum is even, and therefore \textrm{fusc}(n) is even.

This reasoning tells us:

If n is a multiple of 3 then \textrm{fusc}(n) is a multiple of 2 ………… (*)

What if n is not a multiple of 3?

Can we reason, as the evidence suggests, that \textrm{func}(n) is not a multiple of 2?

If n \geq 1 is not a multiple of 3 then n=3p+1 or n=3p+2 for some non-negative integer p.

We first consider the case n=3p+1.

n is either even or odd, so let’s assume first that it is even.

In this case p=2k+1 is odd so \textrm{fusc}(n)=\textrm{fusc}(n/2)=\textrm{fusc}(3k+2).

Because 3k+2 is smaller than n and is also not a multiple of 3, we can assume that we already know \textrm{fusc}(3k+2) is not a multiple of 2.

Therefore, in this case, \textrm{fusc}(n) is not a multiple of 2.

Now consider the case where n is odd.

In this case p=2k is even so \textrm{fusc}(n)=\textrm{fusc}(6k+1)=\textrm{fusc}(3k)+\textrm{fusc}(3k+1).

In this sum we can assume we already know the values of \textrm{fusc}(3k) and \textrm{fusc}(3k+1) and that \textrm{fusc}(3k) is even while \textrm{fusc}(3k+1) is odd.

Therefore \textrm{fusc}(3k)+\textrm{fusc}(3k+1) =\textrm{fusc}(n) is odd.

This deals with the case when n=3p+1. The case n=3p+2 is dealt with similarly.

So we have established:

If n is a not a multiple of 3 then \textrm{fusc}(n) is not  a multiple of 2 ………… (*)

and combining (*) and (**) we have:

\textrm{fusc}(n) is  a multiple of 2 exactly when n is a multiple of 3 ………… (***)

The basis of this reasoning is induction. Because we calculate fusc recursively we can assume, when calculating, \textrm{fusc}(n) that we already know properties of \textrm{fusc}(m) for values m\leq n.

The induction needs a starting point, just as does the calculation of values of fusc, so we need to check these assumed properties are true for n=0,1 (which they are).

Explorations

Dijkstra raised the question of when \textrm{fusc}(n) is divisible by 3. Such divisibility questions do not have clear and simple answers, yet lead into deeper and interesting explorations.

The first few integers n for which \textrm{fusc}(n)=3 are 5, 7, 10, 14, 20, 28, 40, 56, 80, 112, 160, 224, 320, 448, 640, 896, 1280, 1792, 2560, 3584

Show \textrm{fusc}(n)=3 exactly when n=5\times 2^k \textrm{ or } n=7\times 2^k.

5 Responses to "Spotting patterns and finding explanations: Dijkstra’s fusc function"

Very cool stuff. Thanks for introducing me to the “fusc” function–I teach recursion and induction in my Math Research class, and I’m always looking for new material.

I, too, find that the best way to get students to the core ideas of recursion and induction is by making them get their hands dirty by experimenting and playing around with sequences, as you’ve done here. Another great feature is the potential for students to create their one “fusc-like” sequences!

I love the plot to 1000. Very fractal!

You might want to look at the plot up to 10000 at http://twitpic.com/4zggtk

You can get a lot more insight into these properties if you look at the relationship between fusc and the Calkin-Wilf tree and the hyperbinary representations of integers. http://mathlesstraveled.com/tag/hyperbinary/ has a lot of good stuff.

You are right Joshua. In fact my plan was to write about the Cakin-Wilf tree and the stuff on Dijkstra’s func sidetracked me. I figured it was a good example of how one can argue inductively, and I deliberately kept the induction informal. I’m hoping no one gets too upset at that. Thanks for your comments and the reference. Very helpful.

Leave a Reply