Integer complexity and well-ordering
Harry Altman · The Michigan Mathematical Journal · 2015
Define n 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 n ≥ 3 log 3 n for all n.Define the defect of n, denoted δ(n), to be n -3 log 3 n.In this paper, we consider the set D := {δ(n) : n ≥ 1} of all defects.We show that as a subset of the real numbers, the set D is well-ordered, of order type ω ω .More specifically, for k ≥ 1 an integer, D ∩ [0, k) has order type ω k .We also consider some other sets related to D and show that these too are well-ordered and have order type ω ω .