pmontgom@sdcrdcf.UUCP (09/03/84)
Chuck Heaton inquired about the function h defined by
h(0) = 0;
h(k) = k - h(h(k-1));
for integer k >= 0.
Let [ ] designate the greatest integer function; for example
[2.05] = [2.718] = 2 and [-3.2] = -4. Throughout this note,
the constants 0.382, 0.618, 1.618, and 2.618 represent powers of
the golden ratio (SQRT(5)+1)/2.
Lemma 1: If | k - 1.618n | < 1 where k and n are integers, then
[0.382 k] = [0.618 n]
Proof: Assume 0.382 k < s <= 0.618 n where s is an integer.
Then s = 2.618s - 1.618s > k - n. Since k, n, and s are all integers,
this implies s >= k - n + 1. Substitute to get
k - n + 1 < 0.618n
k - 1.618n < -1,
a contradiction. A similar argument works if 0.618 n < s <= 0.382 k.
Lemma 2: The function H(k) = [0.618 (k+1)] satisfies
i) H(0) = 0
ii) k - H(k) = [0.382 (k+1)] = H(H(k-1)) if k > 0
Proof: The first assertion is trivial. For the left half of the
second, observe 0.618(k+1) is irrational and hence not an integer.
Therefore [0.618 (k+1)] + [-0.618 (k+1)] = -1 and
k - H(k) = k - [0.618 (k+1)] = k + 1 + [-0.618 (k+1)]
= [k + 1 - 0.618 (k+1)] = [0.382 (k+1)]
For the right half of the second, let k = 1.618n + r where n is an integer
and 0 <= r < 1.618. Then | (k+1) - 1.618 (n+1) | = | r - 0.618 | < 1. Also
H(k-1) = [0.618k] = [n + 0.618r] = n
H(H(k-1)) = H(n) = [0.618 (n+1)] = [0.382 (k+1)] by Lemma 1.
Corollary: h(k) = [0.618(k+1)] for all k >= 0.
A definition of h(k) which avoids irrational numbers is
[SQRT(5 (k+1)**2)] - k - 1
h(k) = [ -------------------------- ] .
2
Heaton asks about the differences g(n) = h(n) - h(n-1) =
[0.618(n+1)] - [0.618n]. I leave it as an exercise for the reader to prove
the following conditions are equivalent if n > 0:
i) g(n) = 1.
ii) There is a multiple of 1.618 between n and n+1.
iii) There is no multiple of 2.618 between n and n+1.
iv) There are two multiples of 0.618 between n and n+1.
v) There are three multiples of 0.382 between n and n+1.
--
Peter Montgomery
{akgua,allegra,bli,blix,bmcg,burdvax,cbosgd,csun,hplabs,hughes,
ihnp4,ihnss,netvax,orstcs,parallax,randvax,sdcnet,sdcsvax,
slant45,trw-unix,ucla-s,ucla-vax}!sdcrdcf!pmontgom