Some statistics on complexity of numbers

The sequence A025280 in the Encyclopedia of Integer Sequences gives the “complexity of n: number of 1’s required to build n using [addition, multiplication, and exponentiation]”. Let’s call this the “exponential complexity” and denote it by c_e(n).

I’ll abbreviate sums of 1s by the numbers they sum to. So the complexity of 4 is 4 (you can write it as 1+1+1+1, which I’ll abbreviate as 4, or (1+1) \times (1+1), which I’ll abbreviate as $2+2$. But the complexity of 6 is 5 (it’s 2 \times 3) and so the complexity of 7 is 6 (it’s (2 \times 3) + 1). 36 has complexity 7, since it’s (2 \times 3)^2.

There are some variants of it: A005245 doesn’t allow exponentiation, and A091334 allows subtraction. (This is a practical difference: 15 = 3 \times 5, and 15 has complexity 8 if subtraction isn’t allowed, but 15 = 4^2 - 1 gives a complexity of 7 if subtraction is allowed. Not allowing subtraction makes computation easier, though — by only allowing addition, multiplication, and exponentiation we compute everything in terms of small numbers.  Call the version in terms of addition and multiplication only c_m(n), for “multiplicative complexity”.

R. K. Guy, in Some suspiciously simple sequences, suggests that the complexity of n is bounded above by some mutliple of log n.

Can we get some asymptotic trend? The following code in R produces the multiplicative and exponential complexities of the integers from 1 up to 10000. (R is probably not the ideal language for this, since it’s essentially a number-theoretic problem, but I want to make boxplots later.)

n = 10^4;
commul=rep(0,n); commul[1]=1; commul[2]=2;
 for(i in 2:n){m=i;
 m = min(m, commul[1:floor(i/2)] + commul[(i - 1):(i - floor(i/2))]);
 for(j in 2:sqrt(i)) {
 if (i%%j == 0) {m = min(m,commul[j]+commul[i/j]) };
 commul[i]=m}
 }
comexp=rep(0,n); comexp[1]=1; comexp[2]=2;
 for(i in 3:n){m=i;
 m = min(m, comexp[1:floor(i/2)] + comexp[(i - 1):(i - floor(i/2))]);
 for(j in 2:sqrt(i)) {
 if (i%%j == 0) {m = min(m,comexp[j]+comexp[i/j]) };
 for(j in 2:log(i,2)) {
 base = log(i,j);
 if (abs(base-round(base)) comexp[i]=m}
 }

We know the complexity of an integer i is bounded above by i. First we run over the pairs (1, i-1), (2, i-2), \ldots, (\lfloor i/2 \rfloor, \lceil i/2 \rceil) and compute the sums of their complexities; then we find factors of i by trial division and do the same for products; then we check to see if i is a perfect square, cube, and so on up to log_2 ith power.

So we end up with the multiplicative complexity and the exponential complexity of each integer. And we can plot them:

(Multiplicative complexity is in black; exponential complexity is in red.)

Indeed they both seem to grow logarithmically. As you’d expect exponential complexities are smaller, and there are some quite noticeable downward spikes at large powers: for example the exponential complexity of 4096 is 9 (it’s 4^(2 \times 3)) while its multiplicative complexity is 24 (as 4 \times 4 \times 4 \times 4 \times 4 \times 4). If you divide out the logarithms — that is, plotting n against c_m(n)/\log n or c_e(n)/\log n – all the black points lie between two horizontal line (around 2.8 and 3.6), and all the red points appear to lie below some horizontal line as well. There can’t be a horizontal line that all the red points lie above, other than the x-axis — if n has multiplicative complexity bounded above by c log n, then 2^n will have exponential complexity bounded above by 2 + (c \log n). But powers and numbers very near them will be sparse, so perhaps almost all integers have exponential complexity above some logarithmic bound.

We can then make a boxplot for the numbers c_m(2)/log(2), c_m(3)/log(3), \ldots, c_m(1000)/log(1000); one for c_m(1001)/log(1001), \ldots, c_m(2000)/log(2000); and so on, in groups of 1000. We can do the same for the exponential complexities.


Is there some limiting distribution? Can we say, for example, that in the limit half of integers have multiplicative complexity less than 3.1 times their natural logarithm?  I don’t know.

Advertisements

One thought on “Some statistics on complexity of numbers

  1. I’ve been looking into the upper bound on this sequence (whose function I will call A(n)) on my own. Using big-O notation (described at end), I have been able to prove that it is O(log(n)^2), but I have not been able to get that down to O(log(n)), although I have not shown that to be impossible.
    To get it to O(log(n)^2), I express an as 2^0+2^1+2^2…2^log2(n), committing certain terms, effectively representing it as a binary number. Because n can be achieved by ommiting terms from the above sequence, we know that
    A(n)<=(2+0)+(2+1)+(2+2)…+(2+log2(n)).
    A(n)<=2*log2(n)+(0+1+2…log2(n))
    A(n)0, b such that
    for all x>b
    f(x)<=k*g(x)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s