2019•Moscow Journal of Combinatorics and Number TheoryOpen access

Integer complexity: the integer defect

Harry Altman

Open full text 3 citations

Abstract

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\|\ge 3\log_3 n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $δ(n)$, to be the difference $\|n\|-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 $δ(n)$ analogous to $s(n)$. Note that $D(n)$ is not the same as $\lceil δ(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 $ω$ 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)\le 1$, and use this to generalize a result of Rawsthorne [18].

Open-access reader

About this research paper

What this paper is about

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\|\ge 3\log_3 n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $δ(n)$, to be the difference $\|n\|-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 $δ(n)$ analogous to $s(n)$. Note that $D(n)$ is not the same as $\lceil δ(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 $ω$ 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)\le 1$, and use this to generalize a result of Rawsthorne [18].

Why it matters

OpenAlex reports 3 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

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\|\ge 3\log_3 n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $δ(n)$, to be the difference $\|n\|-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 $δ(n)$ analogous to $s(n)$. Note that $D(n)$ is not the same as $\lceil δ(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 $ω$ 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)\le 1$, and use this to generalize a result of Rawsthorne [18].

Key concepts: Integer (computer science), Combinatorics, Mathematics, Congruence (geometry), Omega, Modulo, Multiplication (music), Class (philosophy)

Related papers

Back to paper searchBrowse research topicsOriginal source
Integer complexity: the integer defect — Research Paper | ScholarLens