Numbers with integer complexity close to the lower bound

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Abstract: Define

| n |

to be the complexity of

n

, 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 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 present a method for classifying all

n

with

d e l t a (n) < r

for a given

r

. From this, we derive several consequences. We prove that

| 2^{m} 3^{k} | = 2 m + 3 k

for

m l e 21

with

m

and

k

not both zero, and present a method that can, with more computation, potentially prove the same for larger

m

. Furthermore, defining

A_{r} (x)

to be the number of

n

with

d e l t a (n) < r

and

n l e x

, we prove that

A_{r} (x) = T h e t a_{r} ((l o g x)^{l f l o o r r f l o o r + 1})

, allowing us to conclude that the values of

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

can be arbitrarily large.

Recommendations

Cited in

(13)

This page was built for publication: Numbers with integer complexity close to the lower bound