Integer complexity and well-ordering

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

. Define the defect of

n

, denoted

d e l t a (n)

, to be

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

. In this paper, we consider the set

m a t h s c r D := d e l t a (n) : n g e 1

of all defects. We show that as a subset of the real numbers, the set

m a t h s c r D

is well-ordered, of order type

o m e g a^{o} m e g a

. More specifically, for

k g e 1

an integer,

m a t h s c r D c a p [0, k)

has order type

o m e g a^{k}

. We also consider some other sets related to

m a t h s c r D

, and show that these too are well-ordered and have order type

o m e g a^{o} m e g a

.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Integer complexity and well-ordering