An Introduction to Integer Complexity

[joshuazelinsky]

(Note: I'm in the process of copying some older math posts from Facebook over here with some slight modifications. This is one of those.)

There are a lot of times people talk about famous open mathematical problems. But less attention is paid to some of the problems that are both simple to state and aren't very famous at all. Let's talk about one of those not so famous but still simple open problems.

We're interested in the minimum number of 1s needed to write a positive integer n as a product or sum of 1s, using any number of parentheses, and we'll call that ||n||. For example, the equation 6=(1+1)(1+1+1) shows that ||6|| is at most 5, since it took 5 1s. A little playing around will convince you that you cannot write 6 using just four or fewer 1s, so it is really is the case that ||6||=5. We call ||n|| the integer complexity of n.

Now here's the problem: Does every power of 2 have a most efficient representation the obvious way? That is, is it is always true f(2^k)= 2k? For example, 8=(1+1)(1+1)(1+1) and in fact ||8||=6. Similarly, 16 = (1+1)(1+1)(1+1)(1+1), and ||16||=8. (Note that we sometimes have representations which are tied for writing it this way; for example we can also write 8 = (1+1+1+1)(1+1) but that also takes 6 ones, not fewer).

One might think that the answer should be obviously yes, so let's look for a moment at powers of 5. Does every power of 5 have the obvious representation as best? We'd expect from ||5||=5, to get that ||25||=10, and we do. The pattern continues with ||5^3||=15, and ||5^4||=20, and ||5^5||=25, but then it breaks down, ||5^6||=29. This in some sense happens because 5^6-1 has a lot of small prime factors. But it isn't obvious that something similar couldn't happen with powers of 2. This problem was as far as I'm aware, first proposed by Richard Guy. This is a problem which is dear to me and one which I'm responsible for some of the progress on with Harry Altman who has written a lot about this problem on his Dreamwidth discussing his published works on the problem. 
 

My intuition on this problem keeps jumping back and forth on whether it is true or not. Right now, I'm leaning towards it being false.