#### Vol. 8, No. 3, 2019

 Recent Issues Volume 8, Issue 4 Volume 8, Issue 3 Volume 8, Issue 2 Volume 8, Issue 1
 The Journal About the Journal Editorial Board Subscriptions Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN (electronic): 2640-7361 ISSN (print): 2220-5438 Previously Published To Appear founded and published with the scientific support and advice of the Moscow Institute of Physics and Technology Other MSP Journals
Integer complexity: the integer defect

### Harry Altman

Vol. 8 (2019), No. 3, 193–217
##### Abstract

Define $\parallel n\parallel$ to be the complexity of $n$, the smallest number of 1s needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\parallel n\parallel \ge 3{log}_{3}n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $\delta \left(n\right)$, to be the difference $\parallel n\parallel -3{log}_{3}n$. Meanwhile, in the study of addition chains, it is common to consider $s\left(n\right)$, the number of small steps of $n$, defined as $\ell \left(n\right)-⌊{log}_{2}n⌋$, an integer quantity, where $\ell \left(n\right)$ is the length of the shortest addition chain for $n$. So here we analogously define $D\left(n\right)$, the integer defect of $n$, an integer version of $\delta \left(n\right)$ analogous to $s\left(n\right)$. Note that $D\left(n\right)$ is not the same as $⌈\delta \left(n\right)⌉$.

We show that $D\left(n\right)$ has additional meaning in terms of the defect well-ordering we considered in 2015, in that $D\left(n\right)$ indicates which powers of $\omega$ the quantity $\delta \left(n\right)$ lies between when one restricts to $n$ with $\parallel n\parallel$ lying in a specified congruence class modulo $3$. We also determine all numbers $n$ with $D\left(n\right)\le 1$, and use this to generalize a result of Rawsthorne (1989).

##### Keywords
integer complexity, well-ordering, arithmetic formulas
Primary: 11A67