Integer complexity: The integer defect

Abstract

Define $\Vert n\Vert$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\Vert n\Vert \ge 3{\log }_{3}n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $\delta (n)$, to be the difference $\Vert n\Vert -3{\log }_{3}n$. Meanwhile, in the study of addition chains, it is common to consider $s(n)$, the number of small steps of $n$, defined as $\ell (n)-\lfloor {\log }_{2}n\rfloor$, an integer quantity. So here we analogously define $D(n)$, the integer defect of $n$, an integer version of $\delta (n)$ analogous to $s(n)$. Note that $D(n)$ is not the same as $\lceil \delta (n)\rceil$. We show that $D(n)$ has additional meaning in terms of the defect well-ordering considered in [3], in that $D(n)$ indicates which powers of $\omega$ the quantity $\delta (n)$ lies between when one restricts to $n$ with $\Vert n\Vert$ lying in a specified congruence class modulo $3$. We also determine all numbers $n$ with $D(n)\le 1$, and use this to generalize a result of Rawsthorne [18].

25 pages, 6 tables

References in corpus (3)

• Algorithms for determining integer complexity
• Integer complexity: algorithms and computational results
• On algorithms to calculate integer complexity