# Positive Arithmetic Complexity

Define the binary operator $[k]$ as an operator that takes an integer $k$ and operates between two integers $a,b$ such that:

$$a[k]b = (...((((a)[k-1]a)[k-1]a)[k-1]...a)[k-1]a$$

(b times)

And:

$$a[0]b = a + 1$$

The positive arithmetic complexity base 10 of an integer is the length of the minimum size string consisting of binary operators, parenthesis, and integers used to represent that integer:

for example:

17 has positive arithmetic complexity 2 (since it is simplest expressed as just 17)

but:

$3^{3^{3}} = 7.625597...* 10^{12}$ has positive arithmetic complexity 5 since it can be expressed as just $3[5]2$ since:

3[5]2 = 3[4]3 = 3[3]3[3]3, now here it is crucial to notice the operator works from left to right and accumulates so therefore:

3[3]3[3]3 = (3[3]3)[3]3 = ((3[2]3)[2]3)[3]3 = ((3[1]3[1]3)[2]3)[3]3 = ((3[0]3[0]3)00)[1]3)[2]3)[3]3

Now we take the entire expression with the 0's and nest reduce the [1] (tripling the expression size) and repeat this procedure 2 times in a row with the newly expanded expression to reduce the [2] etc...

Given an arbitrary integer is it possible to compute its positive arithmetic complexity and if so, how does one compute it efficiently?

-
Your function $f(n)=$ "the positive arithmetic complexity of $n$" is a complicated one, requiring that every possible representation mechanism be tried and the smallest result of all of these be the value of the function. When you write $3^{3^3}$, are you counting that it must be written in exponent form minimally as "$3$^($3$^$3$)"? Did you count $3^{3^3}=3^{27}=3$^$27$? –  abiessu Sep 30 '13 at 17:37
I actually didn't take a look at it but: 3^27 = "3[3]27" has 6 characters which is less than the 5 characters used in "3[5]2".I am hoping there is a way to handle this as some form of convex optimization (my gut says this will become an integer programming problem). I really don't want to use brute force enumeration. –  frogeyedpeas Sep 30 '13 at 18:05
Perhaps I'm misunderstanding your notation and question. Are you saying that "$3$^$27$" (having four characters) is not a notation that you will consider valid for the purposes of this question? –  abiessu Sep 30 '13 at 18:09
That is correct, the language i am using is integers written in base 10, parenthesis, and [] operators that contain expressions within them. –  frogeyedpeas Sep 30 '13 at 18:10
I need to do it this way otherwise it is hard to quickly generalize recursive operators, i'm trying to avoid limiting myself to just powers and products but rather I want to consider any recursively defined operator over addition –  frogeyedpeas Sep 30 '13 at 18:11