The Cost of a Positive integer

Authors

Maxwell Norfolk, Bloomsburg UniversityFollow

Abstract

The 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 ◦ 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, C_S is computable for any finite set S of computable binary operations. We then study C_S for various choices of S. If S = {∗} and m > 1 then C_S(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 C_S(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.

Faculty Sponsor

William Calhoun

Recommended Citation

Norfolk, Maxwell (2021) "The Cost of a Positive integer," Rose-Hulman Undergraduate Mathematics Journal: Vol. 22: Iss. 1, Article 9.
Available at: https://scholar.rose-hulman.edu/rhumj/vol22/iss1/9