论文标题
整数复杂性上的上限
Upper Bounds on Integer Complexity
论文作者
论文摘要
将$ || n || $定义为$ n $的\ emph {复杂性}，这是使用添加和乘法的任意组合编写$ n $所需的$ 1 $ s的最小数量。 John Selfridge显示了$ || n || \ geq 3 \ log_3 n $用于所有$ n $。理查德·盖（Richard Guy）指出了$ || n ||的微不足道的上限\ leq 3 \ log_2 n $用于所有$ n> 1 $，通过在基本2中编写$ n $。几乎所有$ n $的上限都是Juan Arias de Reyna和Jan van de Lune提供的。本文为所有$ n $提供了第一个非平凡的上限。特别是，对于所有$ n> 1 $，我们有$ || n || \ leq a \ log n $其中$ a = \ frac {41} {\ log 55296} $。
Define $||n||$ to be the \emph{complexity} of $n$, which is the smallest number of $1$s needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $||n|| \geq 3\log_3 n$ for all $n$. Richard Guy noted the trivial upper bound that $||n|| \leq 3\log_2 n$ for all $n>1$ by writing $n$ in base 2. An upper bound for almost all $n$ was provided by Juan Arias de Reyna and Jan Van de Lune. This paper provides the first non-trivial upper bound for all $n$. In particular, for all $n>1$ we have $||n|| \leq A \log n$ where $A = \frac{41}{\log 55296}$.
