Revisiting the Four Fours

In an earlier blog entry, I discussed a generalization of the four fours problem. In that entry, we discussed the function f(n) defined to be the least number of 1s needed to represent n as a product or sum of 1s using any number of parentheses. (Thus, for example, f(6)=5 since we may write 6=(1+1)(1+1+1)). That entry inspired some discussion both in the comments thread and later by email on the general behavior of f. Harry Altman and I made some progress on the general behavior of f, that may lead to a paper.

One open problem is whether f(2^a*3^b)=2a+3b in general (ignoring a=b=0). This conjecture essentially says that the most efficient way to represent such a number is in the obvious fashion of writing (1+1) a times and writing (1+1+1) b times. Harry has shown that for any value of b if a is at most 15, this holds. Harry's proof involves a large amount of case checking but may be able to be pushed up to larger values of a. He thinks he may be able to construct a computer program that can examine the relevant case types in a systematic fashion.

My own work (with some input from Harry) has focused primarily on the global behavior of f. In the blog entry, I commented that the best known bounds on f were 3log3 n ≤ f(n) 3 ≤ log2 n for n>1 . I have reduced the upper bound to 2.65 log2 n. The remainder of this blog entry will attempt to give the general idea of the proof by sketching out the simpler result that we may take
f(n) ≤ 2.95 log2 n.

The strategy of our proof is similar to the proof that f(n) ≤ 3log2 n but more involved. We will prove this inductively on. For general n ≥ 2, let S(n) be the statement "If for 2≤ k ≤n-1, we have f(k) ≤ 2.95 log2 k, then we have f(n) ≤ 2.95 log2 n." We will show that S(n) holds for all n ≥ 1, and thus the induction holds.

First, observe, that if 2|n then S(n) since we may write n = (1+1)(n/2) and so f(n) ≤ f(n/2) + 2 ≤ 2.95log2 (n/2) +2 ≤ 2.95log2 n + 2 -2.95log2 2 ≤ 2.95log2 n. We thus may assume that n is odd. A similar remark then applies if 3|n. Now, we have either n ≡ 1 or 2 (mod 3). If n ≡ 1 (mod 3), we may write
n = (1+1)(1+1+1)((n-1)/6)+1 and so we get f(n) ≤ f((n-1)/6) + 6 and similar logic applies.

By nearly identical logic we can through arduous case checking obtain that we have S(n) unless n ≡ 7 (mod 8), n ≡ 8 (mod 9), and n ≡ 4 (mod 5). Note that the difficult cases for any modulus always occurs at n ≡ m-1 (mod m). This is not a coincidence, but discussing why that occurs would take us farther afield.

Before proceeding further, let us introduce a helpful notation. We will write [x,y](n) to mean (n-x)/y. Thus, our above results can be phrased in terms of this notation. For example, n the case that n ≡ 1 (mod 6) above, we could write f(n) ≤ f([1,6](n))+ 6. We will also use the notation [x,y]^i(n) to mean repeating the [x,y] function i times. Thus for example, [1,2]^2(11)=2. This notation makes things nicely compact. Now, let a be the largest integer such that 2^a|n+1 and let b be the largest integer such that 3^b|n+1. By the above remarks, we may assume that a ≥ 3 and b ≥ 2 and c ≥1. It does not take much work to see that we then have f(n) ≤ f([1,3]^b[0,2][1,2]^a (n)) + 3a + 4b + 2.

Now, assume that S(n) is false. We thus have 2.95 log2 n ≤ 2.95 log2 (f([1,3]^b[0,2][1,2]^a (n)) + 3a + 4b + 2 ≤ 2.95 log2 n/(2^(a+1)3^b) + 3a + 4b + 2. Canceling the 2.95log2 n on both sides and bringing the log terms over to the right hand side we obtain 2.95(a+1) + (2.95log2 3)b ≤ 3a + 4b + 2 which implies 13.5b + 19 ≤ a. Note that we did implicitly use that 5|n+1 since otherwise we would not be assured [1,3]^b[0,2][1,2]^a (n) is not negative or 0 since otherwise we would be unable to take its logarithm.

Using similar logic but reducing first by 3s before reducing by 2s we can get a similar lower bound for b in terms of a: 1.387a +2.391 ≤ b. The pair of equations has no solutions with a ≤ 3. Thus, our assumption that S(n) fails for some n is false.

The essential idea of this proof is that just as the proof for 3log2 n used the base 2 expansion, of n, we can be assured that we can in some sense reach a number with a good expansion in either 2 or 3 without expending much.

This, is of course, a toy example. With not much more effort, we can reduce the constant to 2.8, using slightly stronger inequalities and using bases 2,3 and 5. The full proof for 2.65 is more detailed but uses the same basic idea with 2,3,5,7,13 and 17. It also turns out that it helps to not think of the bases so much as the p-adic expansions, something which I hope to discuss in a later blog entry.