Improved Algorithms for Integer Complexity

08/20/2023

∙

by   Qizheng He, et al.

∙

0

∙

share

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(Npolylog 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).