Integer complexity: algorithms and computational results

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 g e 0

, we have

| 3^{k} n | = | n | + 3 k

. 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

d e l t a (n) := | n | - 3 l o g_{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^{e} l l | = 2 k + 3 e l l

for

k l e 48

and arbitrary

e l l

(excluding the case

k = e l l = 0

), providing more evidence for the conjecture that

| 2^{k} 3^{e} l l | = 2 k + 3 e l l

whenever

k

and

e l l

are not both zero. An implementation of these algorithms in Haskell is available.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Integer complexity: algorithms and computational results