{
  "id": "1606.03635",
  "version": "v1",
  "published": "2016-06-11T21:53:48.000Z",
  "updated": "2016-06-11T21:53:48.000Z",
  "title": "Integer complexity: algorithms and computational results",
  "authors": [
    "Harry Altman"
  ],
  "comment": "33 pages, 2 figures",
  "categories": [
    "math.NT"
  ],
  "abstract": "Define $\\|n\\|$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. Define $n$ to be stable if for all $k\\ge 0$, we have $\\|3^k n\\|=\\|n\\|+3k$. In [7], this author and Zelinsky showed that for any $n$, there exists some $K=K(n)$ such that $3^K n$ is stable; however, the proof there provided no upper bound on $K(n)$ or any way of computing it. In this paper, we describe an algorithm for computing $K(n)$, and thereby also show that the set of stable numbers is a computable set. The algorithm is based on considering the defect of a number, defined by $\\delta(n):=\\|n\\|-3\\log_3 n$, building on the methods presented in [3]. As a side benefit, this algorithm also happens to allow fast evaluation of the complexities of powers of $2$; we use it to verify that $\\|2^k 3^\\ell\\|=2k+3\\ell$ for $k\\le48$ and arbitrary $\\ell$ (excluding the case $k=\\ell=0$), providing more evidence for the conjecture that $\\|2^k 3^\\ell\\|=2k+3\\ell$ whenever $k$ and $\\ell$ are not both zero. An implementation of these algorithms in Haskell is available.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-06-11T21:53:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11A67"
    ],
    "keywords": [
      "computational results",
      "integer complexity",
      "arbitrary combination",
      "upper bound",
      "smallest number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}