Spotting patterns and finding explanations: Dijkstra’s fusc function

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

In: Uncategorized
Comment!

0 Shares

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