2015/11/24 by Christopher Shriver, Christopher E. Shriver, Shriver, Christopher E. · 1 citation
Computer Science · Mathematics · #11A67 #11B75 #60J10 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #math.CO #math.NT #msc:11A67 #msc:11B75 #msc:60J10 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1511.07842
18 pages, 3 figures
openalex publication_date 2015/11/24 · arxiv created 2017/01/11 · arxiv updated 2017/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The complexity f(n) of an integer was introduced in 1953 by Mahler & Popken: it is defined as the smallest number of 1's needed in conjunction with arbitrarily many +, * and parentheses to write an integer n (for example, f(6) ≤ 5 since 6 = (1+1)(1+1+1)). The best known bounds are 3 log3n ≤ f(n) ≤ 3.635 log3n. The lower bound is due to Selfridge (with equality for powers of 3); the upper bound was recently proven by Arias de Reyna & Van de Lune, and holds on a set of natural density one. We use Markov chain methods to analyze a large class of algorithms, including one found by David Bevan that improves the upper bound to f(n) ≤ 3.52 log3n on a set of logarithmic density one.