  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) \leq 5$ since $6 = (1+1)(1+1+1)$). The best known bounds are $$
3 \log_{3}{n} \leq f(n) \leq 3.635 \log_{3}{n}.$$ 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) \leq 3.52
\log_{3}{n}$$ on a set of logarithmic density one.
