Wednesday, April 29, 2009

Generalization of the Four Fours Problem

A common middle school and early high school puzzle is the “four fours problem.” The problem is to find a way to represent a given natural number using four fours. Thus, for example one might represent 9 by 4+4+(4/4) or represent 15 as 4*4-(4/4) and so on. The problem as generally phrased leaves deliberately open what operations are allowed. Thus, there may be clever solutions involving factorials or square roots. When I was in 9th grade I antagonized one teacher by solving problems of this sort using more obscure number theoretic functions such as, σ(n), the sum of the positive divisors of a number. Since σ(4)=7, σ(σ(4))=σ(7)=8 and σ(σ(σ(4)))=15, many of these problems become more or less trivial if one is allowed to use this function. Similarly, one cute puzzle is to represent π using four fours; the only solutions I am aware of all involve either inverse trigonometric functions or even more esoteric functions such as the gamma function or the Riemann zeta function. A similar game involves rolling 4 dice and then everyone trying to find a way to represent the number 24 with the numbers on all four dice (variants exist involving drawing cards from a deck as well). One can however ask a more well-defined question: Given, some set of n, ks and and some fixed set of allowed operations can we represent a given m? Or, for a given m, can we produce easy bounds on how many ks we need to represent m? How small can we choose n if we want to be able to represent all m less than some given x using up to n ks?

Assume for a moment that are allowed operations are addition, multiplication, subtraction and division. Define gk(n) to be the minimum number of ks we need to represent n . Thus, for example g1(6)=5 since 6=(1+1)*(1+1+1) and it t is not hard to show that we in fact require 5 1s for 6. Now, for any given k we may write 1 as k/k and may write k=1+1+1…+1 Thus, we have gk(n) ≤ 2 g1(n) and g1(x) ≤ kg1(n). It is thus natural to just think about g1(n). However, even this is a very difficult function to work with. So it is natural to try to understand g1(n) by thinking about the slightly easier function f(n) which is exactly the same as g1(n) but we only allow multiplication and addition as operations.

For the remainder of this post we are going to work with f(n) which is the minimum number of 1s needed to represent n where we can only use multiplication and addition. What can we say about f(n)? It is not hard to show that for all x, f(n) ≤ 1 + 3log2n. To see this, observe that f(1)=1, f(2)=2 and for any given n if we can represent n with k 1s then we can represent 2n and 2n+1 with at most k+3 1s since We have 2n=(1+1)*n and 2n+1=(1+1)*n+1. Thus, f(2n) ≤ f(n)+3, f(2n+1) ≤ f(n)+3 and so the desired result follows by induction. It is also not hard to prove that f(n) ≥ 3log3 n. Despite the highly elementary nature of these bounds, substantially better bounds on f are difficult to come by. Richard Guy’s “Unsolved Problems in Number Theory” last updated as of 2003 does not give substantially better bounds.

There are many questions about representations of these forms that are still unsolved. For example, it is conjectured that if p is prime f(p)=1+f(p-1). That is, if p is a prime the most efficient representation comes from taking a representation of p-1 and then adding 1. For example, f(1)=7 from the representation 7=(1+1)*(1+1+1+1+1) and f(11)=8 which we get from 11=(1+1)*(1+1+1+1+1)+1. Better bounds on f and similar functions turn out to be related to open problems in complexity theory including the P=NP problem. Entry F26 in Guy’s aforementioned book which gives a summary of what is known about this and related problems along with a bibliography. These simple questions about the behavior of f are good examples of why number theory is such an interesting area of mathematics. One can ask very simple, naïve questions which are unsolved. Moreover, those questions often turn out to be related to deep, difficult mathematics.

16 comments:

Etienne Vouga said...

For how large a p has this conjecture been verified? I would look at primes p = a*b+1, with a, b large primes.

Joshua said...

I don't know how far it has been checked up to. In general, calculating values of isn't easy since you need to calculate all the previous values of f. I remember that this was at one pointed verified up to 10^6 but that was a long time ago (mid 90s). I don't know what direct numeric work has been done since then.

Direct calculation is a bit unpleasant. Using recursion isn't easy unless one duplicates a lot of work. The best method I'm aware of is to just go through and calculate every value of f under the value you care about. This takes exponential time.

(If one is going to do any computational work, there are a few other open questions worth looking at. For example, if n=(3^a)*(2^b) does that mean f(n)=3a+2b. There are also more complicated conjectures for f(2p), f(3p) and a few others.

Joshua said...

Also, I assume you meant p=2ab+1 rather than p=ab+1.

Etienne Vouga said...

I wrote a small C++ program that takes in n and computes f(i) for 1 <= i <= n; the source code is at www.evouga.com/misc/f.cpp. Basically it computes f^-1(j) for successive j until all numbers 1, ..., n are found in some preimage.

I don't think this algorithm is exponential, but it is very slow polynomial - my quick guess is n^4 - so although I can find f(10^7) = 48 in a few minutes, for significantly larger orders of magnitude we'll need a better algorithm. I haven't looked at the data yet, I'll let you know if I find anything curious.

It's clear to me that f(3^i) = 3i, but how do you prove that f(2^i) = 2i?

Joshua said...

As far as I know, f(2^i)=2i is open.

Joshua said...

Also, there seems to be a notational issue here: polynomial in n is exponential time in comp sci terminology since in comp sci one looks at the length of the input (which is log_2 n ). If one is just trying to do it polynomial in n then I think you can do it in n^2 but not sure.

sniffnoy said...

Yeah, quadratic in n, but technically exponential, looks pretty direct to me; I'll go implement that in a bit...

Is there any standard name for this function, btw?

I note f(2*3^a)=2+3a, f(4*3^a)=4+3a; presumably this is the motivation for the idea that f(2^b * 3^a)=2b+4a? (a and b not both zero). (Well, that plus the fact that it just makes intuitive sense.)

Hm, I guess that raises the question of when in general f(n^k)=kf(n), though if we don't even have it for n=2, presumably that's pretty hard; in particular as well as n=2 I have to wonder about n=5, as that's the highest n for which f(n)=n. (And it's true for n=4 if it is for n=2.) I notice by computation that f(25)=10 as expected, but I haven't written a program yet so of course I've not computed f(125)...

Also: What about the following generalization of f(p)=f(p-1)+1:
min over a+b=n of f(a)+f(b) is f(n-1)+1. That's certainly true of my computation so far; has that been much tested?

Joshua said...

Harry, you are pushing the limits of my knowledge of the problem.

I think I've heard verbally your statement about min over a+b=n but don't remember if there's any counterexample.

f(n^k)=kf(n) is I'm pretty sure false for moderate values of n. I think 7 provides a direct counterexample:

f(49)<=f(48)+1<=f(6*8)+1=5+6+1=11 but 2f(7)=12.

I don't know what happens in the case of 5^k.

I'm not aware of any special name for the function in question.

Joshua said...

Sorry, that's wrong. 1+5+6=12.

Ok. Try n=11. f(11)=8.
f(121)<=1+f(120)=1+f(5)+f(3+f(8)<=1+5+3+6=15<16=2f(11).

Ok. That one works.

sniffnoy said...

OK, computation shows that f(5^6)=29. Hm, my program doesn't currently explain how it got its results; I'll fix it to do that so we can see why this is (FWIW).

Joshua said...

Probably best to just have it record the final operator (which is I suspect in this case (5^6-1)+1. Then you can backtrack as far as you want for each piece.

sniffnoy said...

Well, since my program has to compute f(k) forall k<=n anyway, it just prints them out too (that's what tail is for), and now I've modified it so that by each one it lists the two components, so you can backtrack through the whole thing.

In this case, we get (after collecting together some of its repeated multiplications by 2s and 3s):

15625=1+15624
15624=4*3906
3906=18*217
217=1+216
216=4*54

f(54)=11 (of form 2*3^k),
f(4)=4,
f(18)=8

For a total of 1+4+8+1+4+11=29.

Joshua said...

One other point:

At least as of a few years ago it was (and I think, still is) unknown if f(n) ~ 3log_3 n. Showing that f(2^k)=2k in general would also answer that question with a no.

Joshua said...

Harry, is that the smallest power of 5 that works?

That is a good example incidentally of how irregular optimal representations can be.

In that case, the most efficient representation isn't coming from the write in base 2 trick or the write in base 3 trick.

sniffnoy said...

Yeah, I was trying them in sequence.

Joshua said...

So I've actually made what may be non-trivial progress on the problem. I'll be posting a blog entry about it in a few days.