Reference : Integer Complexity: Breaking the θ(n2) barrier
E-prints/Working papers : Already available on another site
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/18508
Integer Complexity: Breaking the θ(n2) barrier
English
Venkatesh, Srinivas Vivek mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
B. R., Shankar [National Institute of Technology Karnataka, Surathkal, India > Department of Mathematical and Computational Sciences]
2008
Updated October 23, 2014
2
No
[en] Integer complexity ; Number theory ; Running time
[en] The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and the parentheses. The running time of the algorithm currently used to compute
$f(n)$ is $\Theta(n^{2})$. In this paper we present an algorithm with $\Theta(n^{\log_{2}3})$ as its running time. We also present a proof of the theorem: the largest solutions of $f(m)=3k,\,3k\pm1$ are, respectively, $m=3^{k},\,3^{k}\pm3^{k-1}$.
Researchers ; Professionals ; Students ; General public
http://hdl.handle.net/10993/18508
This paper was previously available at www.waset.org since 2008. As on October 2014, it is no longer available there due to unknown reasons.
www.waset.org

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
intcomp-orbilu.pdfAuthor preprint217.13 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.