Integer complexity: the integer defect

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. John Selfridge showed that

| n | g e 3 l o g_{3} n

for all

n

, leading this author and Zelinsky to define the defect of

n

,

d e l t a (n)

, to be the difference

| n | - 3 l o g_{3} n

. Meanwhile, in the study of addition chains, it is common to consider

s (n)

, the number of small steps of

n

, defined as

e l l (n) - l f l o o r l o g_{2} n f l o o r

, an integer quantity. So here we analogously define

D (n)

, the integer defect of

n

, an integer version of

d e l t a (n)

analogous to

s (n)

. Note that

D (n)

is not the same as

l c e i l d e l t a (n) c e i l

. We show that

D (n)

has additional meaning in terms of the defect well-ordering considered in [3], in that

D (n)

indicates which powers of

o m e g a

the quantity

d e l t a (n)

lies between when one restricts to

n

with

| n |

lying in a specified congruence class modulo

3

. We also determine all numbers

n

with

D (n) l e 1

, and use this to generalize a result of Rawsthorne [18].

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Integer complexity: the integer defect