Reference : Integer Complexity: Breaking the θ(n2) barrier
 Document type : E-prints/Working papers : Already available on another site Discipline(s) : Engineering, computing & technology : Computer science To cite this reference: http://hdl.handle.net/10993/18508
 Title : Integer Complexity: Breaking the θ(n2) barrier Language : English Author, co-author : Venkatesh, Srinivas Vivek [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] Publication date : 2008 Edition : Updated October 23, 2014 Number of pages : 2 Peer reviewed : No Keywords : [en] Integer complexity ; Number theory ; Running time Abstract : [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}$. Target : Researchers ; Professionals ; Students ; General public Permalink : http://hdl.handle.net/10993/18508 Commentary : 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. source URL : www.waset.org

File(s) associated to this reference

Fulltext file(s):

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

All documents in ORBilu are protected by a user license.