## 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*where

_{S}(a) + C_{S}(b)*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*is computable for any finite set

_{S}*S*of computable binary operations. We then study

*C*for various choices of

_{S}*S*. If

*S = {∗}*and

*m > 1*then

*C*is the sum of the prime factors of

_{S}(m)*m*(with repetition). A positive integer

*m*is defined to be completely multiplicative if

*C*. We show that if

_{{+,∗}}(m) = C_{{∗}}(m)*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*. We use the notations +1 and −1 to denote the binary operations

_{S}(m) ∈ O(log m)*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.

## 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

*The LaTeX code used to generate the PDF*