The cost CS 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 CS(a) + CS(b) where a and b are positive integers and m = a ◦ b for some binary operation ◦ ∈ 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, CS is computable for any finite set S of computable binary operations. We then study CS for various choices of S. If S = {∗} and m > 1 then CS(m) is the sum of the prime factors of m (with repetition). A positive integer m is defined to be completely multiplicative if C{+,∗} (m) = C{∗} (m). We show that if m is completely multiplicative then m is of the form 2a ∗ 3b ∗ 5c. The converse is an open question. If S = {+, ∗} we prove logarithmic upper and lower bounds implying that CS(m) ∈ O(log m). We use the notations +1 and −1 to denote the binary operations a + b and a − b restricted to the cases where b = 1, and we conjecture that C{+,∗,−} = C{+1,∗,−1} . However, we give an example to show that C{+,∧} C{+1,∧} where ∧ represents exponentiation. Several interesting open questions are also discussed.

Author Bio

Max Norfolk wrote this paper during the summer session under the guidance of Dr. William Calhoun. He currently a junior at Danville Area High School, and is taking classes at Bloomsburg University through the ACE program. He hopes to graduate from Bloomsburg University with a degree in Computer Science. He enjoys watching movies and playing Dungeons and Dragons.

integer-cost-norfolk.tex (27 kB)
The LaTeX code used to generate the PDF