__More about the function fusc__. (A sequel to EWD570)

In EWD570 I introduced the function `fusc`, given by

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

Compatible with the second part of that definition we derive from the third part `fusc`(0) = 0 . I showed there the following iterative program for the computation of `fusc`(`N`) —with `peven` and `podd` standing for "positive and even" and "positive and odd" respectively—

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

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

On my last trip through the USA, while lecturing to a Burroughs audience, my audience derived this program after it had decided —after only a few very modest hints!— that a good candidate for an invariant relation would be

P: `fusc`(`N`) = `a`*`fusc`(`n`) + `b`*`fusc`(`n`+1)

The audience arrived at this suggestion after a few simple considerations. The first observation was that

`fusc`(`N`) = `fusc`(`n`)

would be simple to initialize by means of `n`:= `N` . They quickly saw that this was too simple, and considered

`fusc`(`N`) = `a`*`fusc`(`n`)

equally trivially initialized by `n`, `a` := `N`, 1 ; it was then remarked that initialization would not be complicated by an additive term

`fusc`(`N`) = `a`*`fusc`(`n`) + `b`

as that is initialized by `n`, `a`, `b` := `N`, 1, 0 . The observation that for `n` = 0 the first term would disappear but that `fusc`(`n`+1) = 1 would then hold suggested, together with the third part of the definition for `fusc` the fully blown-up P as given above. Separating the cases

n = 2k: | fusc(N) | = a*fusc(n) + b*fusc(n+1)= a*fusc(2k) + b*fusc(2k+1)= ( a+b)*fusc(k) + b*fusc(k+1) |

n = 2k+1: | fusc(N) | = a*fusc(n) + b*fusc(n+1)= a*fusc(2k+1) + b*fusc(2k+2)= a*fusc(k) + (a+b)*fusc(k+1) |

my audience quickly derived —to its pleasant surprise!— the iterative program given above.

^{*} _{*} ^{*}

From the above program, two properties of the function `fusc` follow. The first one is that the value of the function `fusc` does not change if we invert in the binary representation of the argument all "internal" digits, i.e. all the binary digits between the most- and the least-significant ones. For instance `fusc`(19) = `fusc`(29) because, in binary 19 and 29 are 10011 and 11101 respectively. This follows from the comparison of the `a`,`b`-pairs during those two computations. After the processing of the least significant digit of the arguments, both have `a`,`b` = 1,1 . As a result of the inverted internal digits, the one computation has the role of `a` and `b` interchanged with respect to the other computation. Because the sum of the two values is a symmetric function of its arguments and, as a result of the last —i.e. most-significant— 1 in the argument that sum of `a` and `b` is delivered (in `b` ) as the final value, both computations deliver the same result.

The next property is more surprising. (At least, I think so.) Let us try to represent the pair `a`,`b` by the single value `m` , according to the convention

`a` = `fusc`(`m`+1) `b` = `fusc`(`m`)

In the case of `peven`(`n`) the operation on `a`,`b` has the form `a`, `b` := `a`+`b`, `b` or:

fusc(m+1), fusc(m) | := fusc(m+1)+fusc(m), fusc(m):= fusc(2m+1), fusc(2m) |

an operation that translates into `m`:= 2`m` . Similarly `a`, `b` := `a`, `a`+`b` translates into `m`:= 2`m`+1 . Substituting all this in our iterative program we get

`n`, `m` := `N`, 0;**do** `peven`(`n`) → `m`, `n` := 2*`m`, `n`/2

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

i.e. the `fusc`-value does not change if we write the binary digits of the argument in the reverse order. For example `fusc`(19) = `fusc`(25) because 19 and 25 are in binary 10011 and 11001 respectively. I think this second property more surprising!

^{*} _{*} ^{*}

In a way which does not admit generalization I discovered the equivalence

2|`fusc`(`n`) <=> 3|`n`

i.e. `fusc`(`n`) is even iff `n` is a multiple of 3. Inspired by a recent exercise of Don Knuth I tried to characterize the arguments `n` such that 3|`fusc`(`n`) .

With braces used to denote zero or more instances of the enclosed, the vertical bar as the BNF "or", and the question mark "?" to denote either a 0 or a 1 , the syntactical representation for such an argument (in binary) is

{0}1{?0{1}0|?1{0}1}?1{0}

I derived this by considering —as a direct derivation of my program— the finite state automaton that computes `fusc`(`N`)|**mod** 3 . It was the first time of my life that I did what others have done many times before, i.e. relating a finite state automaton to a grammar. The exercise is up till now only of modest interest; it taught me that division by a fixed factor and (simple!) syntactic analysis are processes that are very closely related to each other, and that insight I think somehow illuminating.

^{*} _{*} ^{*}

Since the distribution of EW570 it has been discovered that more mathematicians have occupied themselves with the function `fusc` —they only gave it a different name!— a fact that is not surprising in view of its properties. J.J.Seidel and F.L.Bauer have independently pointed out to me that it is no. 56 in Sloane's *Dictionary of Integer Sequences*, that refers to an article by G.de Rham, *Elemente der Mathematik*, Vol.2 (1947) pg.95 . It was fun!