Reference : Integer Complexity: Breaking the θ(n2) barrier
E-prints/Working papers : Already available on another site
Engineering, computing & technology : Computer science
Integer Complexity: Breaking the θ(n2) barrier
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]
Updated October 23, 2014
[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
This paper was previously available at since 2008. As on October 2014, it is no longer available there due to unknown reasons.

File(s) associated to this reference

Fulltext file(s):

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

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.