__An exercise for Dr.R.M.Burstall__

Dear Rod,

because —as you know— we Dutch are a God-fearing nation, Ascension-day is here an official Holiday, and on official Holidays I don't work. Today I just fooled with figures.

In doing so I discovered a function of the natural numbers which has a nice recursive definition, viz.

`fusc`(1) = 1

`fusc`(2`n`) = `fusc`(`n`)

`fusc`(2`n`+1) = `fusc`(`n`) + `fusc`(`n`+1)

a definition which, as far as complexity is concerned, seems to lie between the Fibonacci series and the Pascal triangle.

(The function `fusc` is of a mild interest on account of the following property: with `f`1 = `fusc`(`n`1) and `f`2 = `fusc`(`n`2) the following two statements hold:

"if there exists an `N` such that `n`1 + `n`2 = 2^{N} , then `f`1 and `f`2 are relatively prime" and "if `f`1 and `f`2 are relatively prime, then there exists an `n`1 , an `n`2 , and an `N` , such that `n`1 + `n`2 = 2^{N} ." In the above recursive definition, this is no longer obvious, at least not to me; hence its name.)

Having seen your exercises concerning the derivation of an iterative program, starting with the recursive definition for the `n`-th number of the Fibonacci series, I was suddenly reminded of that exercise when I was considering an iterative program for the computation of `fusc` . It should be a rewarding exercise, as there exists a very nice iterative program:

`n`, `a`, `b` := `N`, 1, 0;**do** `n` ≠ 0 **and** `even`(`n`) → `a`, `n`:= `a` + `b`, `n`/2

▯ `odd`(`n`) → `b`, `n`:= `b` + `a`, (`n`-1)/2**od** {`b` = `fusc`(`N`)}

I wish you luck and enjoyment! Yours ever,