OBM 1996 Problem 3

Let $f(n)$ be the smallest number of 1s needed to represent the positive integer $n$ using only 1s, $+$ signs, $\times$ signs and brackets $(,)$ . For example, you could represent 80 with 13 1s as follows: $(1+1+1+1+1)(1+1+1+1)(1+1+1+1)$ . Show that $3 \log(n) \leq \log(3)f(n) \leq 5 \log(n)$ for $n > 1$ .