Integer complexity: representing numbers of bounded defect

DOI10.1016/J.TCS.2016.09.005zbMATH Open1371.11015arXiv1603.06122OpenAlexW2964114665MaRDI QIDQ338388FDOQ338388

Authors: Harry Altman 

Publication date: 4 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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|ge3lo{g}_{3}n$ for all $n$. Based on this, this author and Zelinsky defined the "defect" of $n$, $delta(n):=|n|-3lo{g}_{3}n$, and this author showed that the set of all defects is a well-ordered subset of the real numbers. This was accomplished by showing that for a fixed real number $r$, there is a finite set $S$ of polynomials called "low-defect polynomials" such that for any $n$ with $delta(n)<r$, $n$ has the form $f(3^{k_1},ldots,3^{k_r})3^{k_{r+1}}$ for some $finS$. However, using the polynomials produced by this method, many extraneous $n$ with $delta(n)ger$ would also be represented. In this paper we show how to remedy this and modify $S$ so as to represent precisely the $n$ with $delta(n)<r$ and remove anything extraneous. Since the same polynomial can represent both $n$ with $delta(n)<r$ and $n$ with $delta(n)ger$, this is not a matter of simply excising the appropriate polynomials, but requires "truncating" the polynomials to form new ones.

Full work available at URL: https://arxiv.org/abs/1603.06122

Recommendations

• Integer complexity: the integer defect
• Numbers with integer complexity close to the lower bound
• Integer complexity and well-ordering
• Integer complexity: experimental and analytical results. II
• Integer complexity: algorithms and computational results

zbMATH Keywords

integer complexity

Mathematics Subject Classification ID

Other number representations (11A67)

Cites Work

• Title not available (Why is that?)
• Unsolved problems in number theory
• Characterizing arithmetic read-once formulae
• Title not available (Why is that?)
• Title not available (Why is that?)
• Numbers with integer complexity close to the lower bound
• Title not available (Why is that?)
• Integer complexity and well-ordering

Cited In (7)

• Integer complexity: the integer defect
• Integer complexity: algorithms and computational results
• On algorithms to calculate integer complexity
• Integer complexity: experimental and analytical results. II
• Integer complexity and well-ordering
• Arithmetical self-similar compact sets
• Numbers with integer complexity close to the lower bound

This page was built for publication: Integer complexity: representing numbers of bounded defect

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338388)