## Index

## Introduction

I’ll consider the problem of the complexity of natural numbers , where the complexity of is defined as the minimal number of occurences of in arithmetical formulas (strings) which reprezent , and which consist only of copies of three characters (I decided to use the reversed Łukasiewicz notation, so that no parentheses are needed). I’ll provide a pedantic definition below but first let me present the minimal formulas for the ten smallest natural numbers:

The above equalities, of the type, will be proved later; at this time we can only claim the respective inequalities (of course claim for is obvious).

## Ł-strings

Natural numbers will be represented by the so-called Ł-strings (and later I will show HOW natural numbers are represented by Ł-strings–it will be very easy). The Ł-strings are defined as follows:

- is an Ł-string;
- if are Ł-strings then the concatenation is an Ł-string;
- if are Ł-strings then the concatenation is an Ł-string;
- all Ł-strings are obtained by a finite application of the above three rules (i.e. Ł-strings form the smallest set of strings of characters which satisfies the three rules above).

Now the value is defined simply as , i.e.

\[ \mathit{val}(”X”)\ :=\ X\]

E.g.

\[ \mathit{val}(”111++”)\ :=\ 111++\ =\ 3\]

If this definition of value is too shockingly simple for you then you may accept the following equivalent inductive form of it, which is comfortingly longer:

## Complexity

First we define the complexity of a Ł-strings (as the number of appearances of 1):

for arbitrary Ł-strings (in the last two formulas above we have mixed operations on the left, but the same twice, i.e. , on the right).

Finally, the complexity of an arbitrary natural number is defined as follows:

\[ \mathit{rn}(n)\ :=\ \min_{\qquad ”X”\ :\ \mathit{val}(”X”)=n}\ \mathit{RN}(”X”) \]

## Upper bounds

It’s easy to prove (by induction) that:

\[ \forall_{n\in \mathbb N}\quad\mathit{rn}(n)\ \ \le\ \ n \]

Moreover, now , i.e.

\[ \forall_{a\ n\in \mathbb N}\quad\mathit{rn}(a\ n\ +)\ \ \le\ \ \mathit{rn}(a)\ n\ + \]

which is a simple generalization of the previous inequality. Easy induction allows us also to show that:

\[ \forall_{a\ n\in\mathbb N}\quad\mathit{rn}(a^n)\ \ \le\ \ \mathit{rn}(a)\ n\ \bullet \]

e.g. fora we obtain:

\[ \forall_{n\in\mathbb N}\quad\mathit{rn}(3^n)\ \ \le\ \ 3\ n\ \bullet \]

We will see later that the last inequality actually can be replaced by equality, so that:

- etc.

The selection of was especially good, as we will see soon. The goodness of natural number in the given context is value:

\[ \lambda(a) := \frac{\log(a)}{\mathit{rn}(a)} \]

or , i.e. equivalently:

\[ \beta(a) := a^\frac 1{\mathit{rn}(a)} \]

For instance,

\[ \beta(2) = 8^{\frac 16} < 9^{\frac 16} = \beta(3) \] hence in this sense integer is better than integer . In general, let , where . Then, by our earlier inequality:

\[ \mathit{rn}(x)\ \ \le\ \ \mathit{rn}(a)\ \frac{\log(x)}{\log(a)}\ \bullet \]

i.e.

\[ \frac{\mathit{rn}(x)}{\log(x)}\ \ \le\ \ \frac{\mathit{rn}(a)}{\log(a)}\ \ =\ \ \frac 1{\lambda(a)} \]

We are interested in as low upper bound as possible. Thus we are especially interested in natural numbers for which is as large as possible; it is the largest for and for the powers of . More about it later.