The One Four Conjecture

I can’t remember when I first heard of the “Four Fours” puzzle.  The goal is to use four 4’s to create as many different integers as possible using basic arithmetic operations.  For example,

Which numbers are possible to obtain depends on the range of operations or functions allowed.  Using a decimal point and a bar for a repeating decimal, for example, allows expressions such as

You can read more about this puzzle on this Wikipedia page, and look at the references there for even more information.

A few years ago, I wondered about what numbers are possible using just one 4.  Of course there aren’t many if you restrict yourself to the basic arithmetic operations.  But you can write for example.

So the factorial was a way to make numbers larger, but then what about bringing those factorials back down?  The square root function does that, but then you need to convert to an integer.  So perhaps use the floor function, so that the second function you use is

Now this is a bit trickier — even small numbers are not so easy to obtain.  For example,

That’s a lot of work just to get 5….  But as I kept on exploring using Mathematica, it seemed that eventually, you could get every positive integer this way!

At first, it was really hard to believe — but the more I worked, the more plausible it became.  It soon became obvious that other numbers other than 4 were possible to begin with.  You could start with 9, for example, since then you could get 4 by

and then proceed from there.

Further, why use a square root?  Could other roots work as well?  More experimentation seemed to suggest that any root might also work.  This led me to the following:

The One Conjecture:  Suppose and are given.  Then using the factorial function and the function

all positive integers may be obtained by some composition of these functions.

This seemed really difficult to prove.  Suppose, for example — using the factorial and square root functions — it is impossible to obtain some particular integer no matter what input you start with.  Of course it is always possible to obtain from and from and so on, but you’ve got to get larger first, and that requires some use of the factorial.

It turns out, however — in a particular sense (which you’ll see in a moment) — it is always possible, for any

The Possibility Lemma:  Suppose is given.  Then for any positive integer there exist positive integers such that

where the function is composed times.

Let’s focus on the square root for now — that is,  The Possibility Lemma is only a starting point, since it turns out that most of the time, the smallest need to generate a particular is actually greater than — making an induction proof based on the Lemma impossible.

For example, for the smallest is with so that

But for we get

It seemed that the least needed to generate a given exhibited rather erratic behavior.  So my next step was to plot a graph of the least given

I won’t go into all the details here — but it took a little work to optimize the algorithms.  As an example, the smallest needed to generate is and computations with such large factorials take time.  It turns out that the trick was to compute in advance the first 1,000,000 factorials as floating point numbers.  A little accuracy is lost as result, but several checks suggested that even so, the correct value of is found each time.

So here is the plot of values for the least possible for from 1 to 5,000.

And here’s the plot for values of from 1 to 40,000.

Now here’s something interesting!  You can’t help but think “fractal behavior” here.  And why the thin bands?  Not sure yet, but they somehow correspond to square roots of factorials.  For example, the for 49,998 is 470,324, and the for 49,999 is 248,312, and the square root of 470,324! is not too far off from 248,312!.

But although it looks like there are thin bands, they are not uniformly generated.  Here’s a closeup of the previous graph in the range 49,900 to 50,000.

There doesn’t seem to be a predictable pattern as to when the jumps are made.

And it does appear that the thin bands have an upward trend.  Might it be possible that every positive integer is eventually the for some ?  Not an easy question to answer.

And this is only a beginning!  I just generated the graph up to 50,000 yesterday, so I haven’t had time to analyze it in any more detail.  Using generates the following graph, so it seems that there may be similar behavior for various

I plan to keep working on this little puzzle — although I think a proof of or counterexample to the One Conjecture is rather far off.  When I do make more progress, I’ll give you an update.  Despite the difficulty of the problem, this is a really fun puzzle to play with!  I hope you might give it a try, too….