Vol. 8, No. 3, 2019

Download this article
Download this article For screen
For printing
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 n 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 n 3log3n for all n, leading this author and Zelinsky to define the defect of n, δ(n), to be the difference n 3log3n. Meanwhile, in the study of addition chains, it is common to consider s(n), the number of small steps of n, defined as (n) log2n, an integer quantity, where (n) is the length of the shortest addition chain for n. So here we analogously define D(n), the integer defect of n, an integer version of δ(n) analogous to s(n). Note that D(n) is not the same as δ(n).

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

Keywords
integer complexity, well-ordering, arithmetic formulas
Mathematical Subject Classification 2010
Primary: 11A67
Milestones
Received: 2 August 2018
Revised: 7 April 2019
Accepted: 29 April 2019
Published: 23 July 2019
Authors
Harry Altman
University of Michigan
Ann Arbor, MI
United States