Upper Bounds on Integer Complexity

Abstract: 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 | | g e q 3 l o g_{3} n

for all

n

. Richard Guy noted the trivial upper bound that

| | n | | l e q 3 l o g_{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 | | l e q A l o g n

where

A = f r a c 41 l o g 55296

.

This page was built for publication: Upper Bounds on Integer Complexity