1$. \end{subcase} By Lemma 2.3, $ab \geq a+b$. \[C(m) \geq 3\log_3 a +3\log_3 b = 3\log_3(ab) \geq 3\log_3(a+b) = 3\log_3 m.\] \begin{subcase} Either $a=1$ or $b=1$. Without loss of generality suppose $b=1$. \end{subcase} $m = a+b$, so $m=a+1 = (m-1)+1$. Since $m \geq 4$ observe that $m > \frac{1}{3^{1/3}- 1}+1 \approx 3.26116$. Using basic algebra we simply this to $3^{1/3} > \frac{m}{m-1} = 3^{\log_3(\frac{m}{m-1})}$, then to $1/3 > \log_3\big(\frac{m}{m-1}\big) = \log_3m-\log_3(m-1)$, and then finally, \[3\log_3(m-1)+1 > 3\log_3 m\] Using this, observe that $C(m) = C(m-1)+1 \geq 3\log_3(m-1)+1 \geq 3\log_3 m $. \end{proof} \begin{corollary} Any integer of the form $3^a$ is completely multiplicative and $C(3^a)=3a$. \end{corollary} \begin{proof} \[C(3^a) \geq 3\log_3(3^a) = 3a\] \[3^a = 3*3*...*3 \text{ ($a$ times) so } C(3^a) \leq a*C(3) = 3a.\] Therefore $C(3^a)=3a$ and $3^a$ is completely multiplicative. \end{proof} Now we prove upper bounds on $C_{\{+, *\}}(m)$. \begin{thm}[Upper bound] Let $n \in Z^{+}$ and $a \in Z$. If $C(n) \leq 3\log_2 n +a$ for $n= k, k+1, \ldots, 2k-1$, then $C(n) \leq 3\log_2 n +a$ for all $n \geq k$. \end{thm} \begin{proof} The base cases $n=k, k+1, \ldots, 2k-1$ are true by the hypothesis. Inductive Step, $n \geq 2k$: If $n$ is odd, \[C(n) \leq C(n-1)+1=C(2*(\frac{n-1}{2}))+1 \leq C(2)+C(\frac{n-1}{2})+1 = C(\frac{n-1}{2})+3.\] Since $n$ is odd, $n \geq 2k +1$. Therefore, $n>\frac{n-1}{2} \geq k$, so we may apply the induction hypothesis to get \[C(\frac{n-1}{2})+3 \leq 3\log_2(\frac{n-1}{2})+a+3 = 3(\log_2(n-1)-1)+a +3= 3\log_2(n-1)+a \leq 3\log_2 n +a.\] If $n$ is even, \[C(n)= C(2 * \frac{n}{2}) \leq C(\frac{n}{2})+C(2)=C(\frac{n}{2})+2.\] Since $n>\frac{n}{2} \geq k$ we may apply the induction hypothesis to get \[C(\frac{n}{2})+2 \leq 3\log_2(\frac{n}{2})+a+2 =3(\log_2 n -1)+a+2= 3\log_2 n +a-1 \leq 3\log_2 n+a.\] \end{proof} We then for $n\geq1$ can observe $C(n) \leq 3\log_2 n+1$ by checking the hypothesis to the previous statement. Using this method we can also derive more examples of this form such as $C(n) \leq 3\log_2 n-1$ for all $n \geq 2$, and $C(n) \leq 3\log_2 n-2$ for all $n \geq 6$. Any of these examples implies the asymptotic result in the following corollary. \begin{corollary} $C(n) \in O(\log n)$. \end{corollary} \subsection{Conjectures Regarding $C_{\{+, *\}}(m)$} The following conjectures are consistent with the values of $C(m)$ for $m \leq 1000$. \begin{conj} If $m$ is of the form $2^a*3^b*5^c$ where $a, b, c \in \Z$, then $C(m)=2a+3b+5c$ and $m$ is completely multiplicative. \end{conj} This conjecture is the converse of theorem 3.1, and a generalization of Corollary 3.2.1. Corollary 3.2.1 was proved using the lower bound on $C(m)$. This method cannot be applied to 2 and 5. Using the change of base formula, we can write: \begin{align*} 3\log_3 m &=3\frac{\log_2 m }{\log_2 3}\\ &=\frac{3}{\log_2 3}\log_2 m \approx 1.89\log_2 m \end{align*} Therefore, $C(m) \geq 1.89\log_2 m $. When $m=2^a$ we can simplify this so $C(m) \geq 1.89a$. We also know $C(2^a) \leq 2a$, as $2^a$ can be written as $2*2*...*2$ $a$ times. This means \[1.89a \leq C(2^a) \leq 2a\] The small gap between $1.89a$ and $2a$ causes issues when one attempts to prove $C(2^a)=2a$. Similar issues arise when one attempts to prove $C(5^a)=5a$. Since Conjecture 3.1 implies both of these equations, it appears difficult to prove Conjecture 3.1. To state the following conjecture, we use the notation $+1$ to denote the binary operation $a+b$ restricted to the cases where $b=1$. \begin{conj} $C_{\{+, *\}} = C_{\{+1, *\}}$ \end{conj} In the positive integers less than 1000, the addition operation is only used in cases where $C(m)=C(m-1)+1$. If this is always true, as stated in this conjecture, then it would be easier to compute $C(m)$, since other ways to use addition would not need to be checked. This conjecture would be refuted if the following scenario occurs. Suppose there is a positive integer $m$ and $m = x+y$, where $1< x,y