Integer Complexity: Exploring an Interesting Notion

[SSequence]

Not a question as such, but an interesting notion that I came upon (maybe some other people would find it interesting too). It seems to have been introduced in 1950's and seems a good amount of work has been done on it.
For example:
12=(1+1+1)*(1+1+1+1)
So the complexity of 12 is 7 since it can be represented by a minimum of seven 1's in an arithmetic expression (that only uses 1's). Similarly:
6=(1+1+1)*(1+1)
So the complexity of 6 is 5 since it can be represented by a minimum of five 1's in an arithmetic expression (that only uses 1's).

============================

I don't know how well this notion is known. I guess it would depend on interest/knowledge of specific area (e.g. someone with interest/knowledge of combinatorics would have more likely heard of it).

 

[Drakkith]

Isn't this just the sum of the prime factors of each number?

 

[suremarc]

Isn't this just the sum of the prime factors of each number?

The sum of the prime factors of $2^{82,589,933}-1$ is $2^{82,589,933}-1$, but its complexity is at most $2*82,589,933+1$ or $165,179,867$.
I suppose OP could have given more illuminative examples, though

 

[mfb]

What exactly is allowed in the arithmetic expression? Addition and multiplication obviously, I guess subtraction and division as well. Something else?
There is some complexity in choosing that expression on its own.

If you allow all common mathematical symbols then numbers have a bounded complexity, because it's possible to express all of them with a suitably long combination of square roots and similar things using a fixed set of "1".

 

[Delta2]

The sum of the prime factors of $2^{82,589,933}-1$ is $2^{82,589,933}-1$, but its complexity is at most $2*82,589,933+1$ or $165,179,867$.
I suppose OP could have given more illuminative examples, though

Is this the largest known prime number of the form $2^n-1$?

 

[SSequence]

What exactly is allowed in the arithmetic expression? Addition and multiplication obviously, I guess subtraction and division as well. Something else?
There is some complexity in choosing that expression on its own.

As I have been able to understood the definition, valid arithmetic expressions with the following five alphabet (base symbols):
{ ( , ) , *, +,1 }

So for a given number $n \in \mathbb{N}^+$, we would write all the expressions which evaluate to the value $n$ and count the number of $1$'s in each of those expressions. There will be one or more expressions containing the smallest number of $1$'s. That would be the (integer) complexity of $n$.

==============================

Good point w.r.t. minus and division. I am wondering how much things would change with allowing minus and division.

If you allow all common mathematical symbols then numbers have a bounded complexity, because it's possible to express all of them with a suitably long combination of square roots and similar things using a fixed set of "1".

I didn't understand this. Any example?

===============================

With regards, to more non-trivial examples, here are few I found in a paper (in the introduction part). I am just copying the examples (and assuming these are expressions with minimal number of 1's):
$75025 = (1 + 2^2)(1 + 2^2)(1 + 2(1 + 2^2)(1 + 2^2)(2^2.3(1 + 2^2)))$

complexity=1+4+1+4+1+2+5+5+7+1+4=35

and:
$2^{27}−1 = 134217727 = (1 + 2·3)(1 + 2^3·3^2)(1 + 2^9·3^3(1 + 2·3^2))$

complexity=1+5+1+6+6+1+18+9+1+2+6=56

 

[suremarc]

Upon inspection, it felt to me as if the lowest possible complexity should be proportional to $\log n$. I assumed the best possible case was $2^n$ with a complexity of 2n. Actually, this has been solved according to the Wikipedia article, which gives upper and lower bounds that are proportional to $\log n$. Turns out the lower bound is $3n\log_3(2)\approx 1.89n$, which is just shy of $2n$. Neat stuff.

Is this the largest known prime number of the form $2^n-1$?

Affirmative.

If you allow all common mathematical symbols then numbers have a bounded complexity, because it's possible to express all of them with a suitably long combination of square roots and similar things using a fixed set of "1".

After thinking about it, I don’t know if this is true. Addition, subtraction, multiplication, addition, and exponentiation are all binary operations, so you can only express a finite amount of numbers using them. And the square root can be applied only a finite amount of times if the codomain is restricted to the integers, so I think adjoining a square root would not change this.
If the complexity were bounded, there would have to be some $k$ for which there are infinitely many numbers with complexity $k$.

 

[mfb]

I didn't understand this. Any example?

If I would have rememberd the exact method I would have posted it. Anyway, I found it again:

$$n = \frac{-2}{\ln(4)} \ln\left( \frac{\sqrt{\sqrt{\dots\sqrt{4}}}}{ln(4)} \right)$$
where you need n square roots and 2 and 4 can be expressed with 1s in the trivial way. This is coming from the challenge to express natural numbers with 4 "4", you can probably convert this to use 2 instead of 4 to reduce the number of "1"s. Anyway, it's a finite set if square roots and logarithms are allowed.

@suremarc: There are more common mathematical symbols and no one required the expression to operate purely in the integers.

I don't understand why the author chose such a confusing notation for 75025.
75025 = 5*5*(1+2*2*2*3*5*5*5).
Writing 5 as 1+2² does nothing to make things simpler and writing identical factors in different places isn't going to help either.

 

[SSequence]

For the sake of reference, here is the paper I copied the examples from: https://arxiv.org/abs/1404.1850
(the examples can be found at the beginning of second page)

 

[Stephen Tashi]

So the domain and co-domain of the complexity function $C$ is the set of positive integers and (among other properties) it satisfies
1) $C(1) = 1$
2) $C(x + y) \le C(x) + C(y)$
3) $C(xy) \le C(x) + C(y)$

Does it satisfy any interesting inequalities of the form $C(x) \ge$ ...? or $C(x+y) \ge$...? or $C(xy) \ge$...?

 

[mfb]

https://oeis.org/A005245

There is the trivial $C(x) \geq 3 floor(\log_3(x))$ with equality for powers of 3.

I don't have a tool to explore this numerically, but I could imagine that C(xy)>C(x) is not always true. Good candidates would be x=(3ⁿ+1)/2 and y=2 (with n>4).
Edit: C(1486)=22, C(743)=22
743 is a prime, instead of multiplying it by 2 we write 1486 as 1485+1 and 1485 = 3³*(1+2*3³) has a nice composition.
This is the only counterexample up to 1600 that I found looking for a factor 2.

Edit: How could I forget that.
C(x)=min(C(z)+C(y)|z+y=x $\lor$ z*y=x)

 

[suremarc]

Edit: How could I forget that.
C(x)=min(C(z)+C(y)|z+y=x ∨ z*y=x)

I wrote this down too, but don’t know how to get anything useful out of it.

 

[mfb]

It's a fast method to calculate C(x) for all x from 1 to N.