Vol. 8, No. 3, 2019

Download this article
Download this article For screen
For printing
Recent Issues
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
 
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Author Index
To Appear
 
Other MSP Journals
This article is available for purchase or by subscription. See below.
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).

PDF Access Denied

We have not been able to recognize your IP address 3.225.221.130 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

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