Search

We consider a problem first proposed by Mahler and Popken in 1953 and later developed by Coppersmith, Erd\H{o}s, Guy, Isbell, Selfridge, and others. Let $f(n)$ be the complexity of $n \in \mathbb{Z^{+}}$, where $f(n)$ is defined as the least number of $1$'s needed to represent $n$ in conjunction with an arbitrary number of $+$'s, $*$'s, and parentheses. Several algorithms have been developed to calculate the complexity of all integers up to $n$. Currently, the fastest known algorithm runs in time $\mathcal{O}(n^{1.230175})$ and was given by J. Arias de Reyna and J. van de Lune in 2014. This algorithm makes use of a recursive definition given by Guy and iterates through products, $f(d) + f\left(\frac{n}{d}\right)$, for $d \ |\ n$, and sums, $f(a) + f(n - a)$, for $a$ up to some function of $n$. The rate-limiting factor is iterating through the sums. We discuss potential improvements to this algorithm via a method that provides a strong uniform bound on the number of summands that must be calculated for almost all $n$. We also develop code to run J. Arias de Reyna and J. van de Lune's analysis in higher bases and thus reduce their runtime of $\mathcal{O}(n^{1.230175})$ to $\mathcal{O}(n^{1.222911236})$. All of our code can be found online at: https://github.com/kcordwel/Integer-Complexity., Comment: 8 pages; more details were added for the complexity analysis and a link added to the code on GitHub; minor typos corrected

Given a recurrence sequence $H$, with $H_n = c_1 H_{n-1} + \dots + c_t H_{n-t}$ where $c_i \in \mathbb{N}_0$ for all $i$ and $c_1, c_t \geq 1$, the generalized Zeckendorf decomposition (gzd) of $m \in \mathbb{N}_0$ is the unique representation of $m$ using $H$ composed of blocks lexicographically less than $\sigma = (c_1, \dots, c_t)$. We prove that the gzd of $m$ uses the fewest number of summands among all representations of $m$ using $H$, for all $m$, if and only if $\sigma$ is weakly decreasing. We develop an algorithm for moving from any representation of $m$ to the gzd, the analysis of which proves that $\sigma$ weakly decreasing implies summand minimality. We prove that the gzds of numbers of the form $v_0 H_n + \dots + v_\ell H_{n-\ell}$ converge in a suitable sense as $n \to \infty$, furthermore we classify three distinct behaviors for this convergence. We use this result, together with the irreducibility of certain families of polynomials, to exhibit a representation with fewer summands than the gzd if $\sigma$ is not weakly decreasing., Comment: Version 3.0, 27 pages