Improved Algorithms for Integer Complexity

2023/08/20 by Qizheng He, He, Qizheng
Computer Science · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #Commutative Algebra and Its Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2308.10301

openalex publication_date 2023/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The integer complexity f(n) of a positive integer n is defined as the minimum number of 1's needed to represent n, using additions, multiplications and parentheses. We present two simple and faster algorithms for computing the integer complexity: 1) A near-optimal O(N\mathoppolylog N)-time algorithm for computing the integer complexity of all n≤ N, improving the previous O(N^1.223) one [Cordwell et al., 2017]. 2) The first sublinear-time algorithm for computing the integer complexity of a single n, with running time O(n^0.6154). The previous algorithms for computing a single f(n) require computing all f(1),…,f(n).

Related

• On algorithms to calculate integer complexity
• Upper Bounds on Integer Complexity
• Integer Complexity: Experimental and Analytical Results
• Algorithms for determining integer complexity
• Integer Complexity: Experimental and Analytical Results II