# derivation of Hartley function

We want to show that the Hartley function $\log_{2}(n)$ is the only function mapping natural numbers to real numbers that

1. 1.

$H(mn)=H(m)+H(n)$ (),

2. 2.

$H(m)\leq H(m+1)$ (monotonicity), and

3. 3.

$H(2)=1$ (normalization).

Let $f$ be a function on positive integers that satisfies the above three properties. Using the additive property, it is easy to see that the value of $f(1)$ must be zero. So we want to show that $f(n)=\log_{2}(n)$ for all integers $n\geq 2$.

From the additive property, we can show that for any integer $n$ and $k$,

 $f(n^{k})=kf(n).$ (1)

Let $a>2$ be an integer. Let $t$ be any positive integer. There is a unique integer $s$ determined by

 $a^{s}\leq 2^{t}

Therefore,

 $s\log_{2}a\leq t<(s+1)\log_{2}a$

and

 $\frac{s}{t}\leq\frac{1}{\log_{2}a}<\frac{s+1}{t}.$

On the other hand, by monotonicity,

 $f(a^{s})\leq f(2^{t})\leq f(a^{s+1}).$

Using Equation (1) and $f(2)=1$, we get

 $sf(a)\leq t\leq(s+1)f(a),$

and

 $\frac{s}{t}\leq\frac{1}{f(a)}\leq\frac{s+1}{t}.$

Hence,

 $\Big{|}\frac{1}{f(a)}-\frac{1}{\log_{2}(a)}\Big{|}\leq\frac{1}{t}.$

Since $t$ can be arbitrarily large, the difference on the left hand of the above inequality must be zero,

 $f(a)=\log_{2}(a).$
Title derivation of Hartley function DerivationOfHartleyFunction 2013-03-22 14:32:15 2013-03-22 14:32:15 Mathprof (13753) Mathprof (13753) 11 Mathprof (13753) Derivation msc 94A17