\documentclass[12pt]{rhumj_new} \usepackage{amsfonts} \usepackage[utf8]{inputenc} \usepackage[english]{babel} \usepackage{amsthm} \usepackage{amsfonts, amsmath, amssymb} %\usepackage[margin=1in]{geometry} \usepackage{fancyhdr} \usepackage{hyperref} \def\Z{\mathbb Z} \def\Q{\mathbb Q} \def\C{\mathbb C} \def\R{\mathbb R} \newcommand{\<}{\langle} \def\>{\rangle} %\newtheorem{definition}{Definition}[section] \newtheorem{exmp}{Example}[section] %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}{Lemma}[section] \newtheorem{conj}{Conjecture}[section] \theoremstyle{coro} \newtheorem*{coro}{Corollary 3.1.1} % custom for corolarry %\newtheorem{corollary}{Corollary}[theorem] \newtheorem{case}{Case} \newtheorem{subcase}{Case}[case] \makeatletter \renewcommand*\env@matrix[1][*\c@MaxMatrixCols c]{% \hskip -\arraycolsep \let\@ifnextchar\new@ifnextchar \array{#1}} \makeatother %\linespread{1.6} \title[The Cost of a Positive Integer]{The Cost of a Positive Integer} \author[Norfolk]{Maxwell Norfolk} \affiliation{Bloomsburg University} \email{mnorfolk03@outlook.com} \abstract{ The {\em cost} $C_S$ of a positive integer $m$ relative to a set $S$ of binary operations is defined to be the lesser of $m$ and the minimum of $C_S(a)+C_S(b)$ where $a$ and $b$ are positive integers and $m=a \circ b$ for some binary operation $\circ \in S$. The cost of a positive integer measures the complexity of expressing $m$ using the operations in $S$, and is intended to be a simplification of Kolmogrov compelexity. We show that, unlike Kolmolgorov complexity, $C_{S}$ is computable for any finite set $S$ of computable binary operations. We then study $C_{S}$ for various choices of $S$, in particular the sets: $\{*\}, \{+, *\}, \{+,\wedge\}, \{+,*,-\}$. Several interesting open questions are also discussed. } \subjclass{11A41} %please provide keywords for your article \keywords{Algorithmic information theory, Kolmogorov complexity, Number theory} \begin{document} \section{Introduction} There is an extensive literature on Kolmogorov Complexity. (See \cite{LV2019}, for example.) The Kolmogorov complexity of a string (relative to a fixed universal machine) is the length of the shortest program that produces the string as output. For reasons related to Turing's Unsolvability of the Halting Problem, the Kolmogorov complexity of a string is not computable in general. In a 2005 computer programming contest problem called {\em Cheap Integers}, Dr. William Calhoun defined the {\em cost} of a positive integer. The objective was to define a notion similar to Komogorov complexity, but simpler and computable. The original recursive definition of the cost function is $C(1)=1$ and, for $m>1$, $C(m)$ is the minimum of $C(a)+C(b)$ where $m=a+b$ or $m=ab$. Thus the cost of a positive integer measures the complexity of expressing the integer as a sum or product of smaller positive integers. Since only two operations on the finitely many smaller positive integers need to be checked, $C(m)$ can easily be computed recursively. Still, there is enough complexity to the sequence of values of $C$ to raise many interesting questions. Research on the cost function was begun in 2013 by Dr. William Calhoun and D. Golomb \cite{CG2013}. The current work answers some questions left open previously and generalizes the definition of cost so the cost may be defined relative to a set of binary operations. \subsection{Definition} \begin{defin}[The Cost of a Positive Integer] The cost function relative to a set of binary operations $S$ on $Z^+$ is defined recursively by $C_S(1)=1$ and, for $m>1$, $C_S(m)=\min(\{m\} \cup \{C_S(a)+C_S(b): m = a \circ b \mbox{ where } a,b \in \Z^+ \mbox{ and } \circ\in S \})$ \end{defin} The following lemma follows directly from Definition 1.1. \begin{lemma} For any set of binary operations $S$ and any positive integer $m$, $C_{S}(m) \leq m$. \end{lemma} First we show that the cost is well defined. \begin{thm} For any set $S$ of binary operations on $Z^+$ there is a unique function $C_S$ that satisfies Definition 1.1. \end{thm} \begin{proof} We define a sequence of sets $A_i \subseteq Z^+$ for $i=1, 2, \ldots$ so that $A_i=\{m: C_S(m)\leq i\}$. Note that for any $a,b \in Z^+$, $C_S(a)+C_S(b)\geq 2$. Thus $A_1=\{1\}$. We will see that if $i$ is least such that $m\in A_{i}$ then $C_S(m)=i$. Since $m \in A_m$ for all $m$, this means $C_S$ is defined on all of $Z^+$. Now, we will see how to find $A_{i+1}$ from $A_i$. If $m \in A_{i+1}$ then either $m \in A_i$, or $m=i+1$ or $m=a \circ b$ for some $a, b \in Z^+$ and $\circ \in S$ where $C_S(a)+C_S(b)=i+1$. In the last case, $a,b \in A_{i}$ since otherwise $C_S(a)+C_S(b) > i+1$. Therefore, the members of $A_{i+1}$ are determined by $A_i$ and $S$. Furthermore, to be consistent with Definition 1.1, we must set $C_S(m)=i+1$ for all $m\in A_{i+1} \setminus A_{i}$ since it is not possible for $C(a)+C(b)1$ then $C_*(m)$ is equal to the sum of the prime factors of $m$ (with repetition). \end{thm} \begin{proof} Base Step, $m=2: C_*(2)=2$ by Lemma 2.1. Induction Step: Let $m$ be an integer greater than 2. We suppose the statement is true for all positive integers $n$ where $15$, then $C(p)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