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,

42=44-\dfrac4{\sqrt 4}.

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

103=\dfrac{44}{.\overline 4}+4.

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 4!= 24, 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

f(n)=\lfloor\sqrt n\rfloor.

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

5=\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor \sqrt{(4!)!}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor.

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

4=\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor \sqrt{9!}\right\rfloor}\right\rfloor}\right\rfloor,

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 n Conjecture:  Suppose n>2 and p>1 are given.  Then using the factorial function and the function

f(n)=\lfloor n^{1/p}\rfloor,

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 n from n^2, and n^2 from n^4, 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 p.

The Possibility Lemma:  Suppose p>1 is given.  Then for any positive integer k>1, there exist positive integers q,m such that

k=f(f(f\cdots f(m!)),

where the function f is composed q times.

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

For example, for k=42, the smallest m is 218 with q=8, so that

42=f(f(f(f(f(f(f(f(218!)))))))).

But for k=43, we get

43=\left\lfloor\sqrt{\left\lfloor \sqrt{10!}\right\rfloor}\right\rfloor.

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

I won’t go into all the details here — but it took a little work to optimize the algorithms.  As an example, the smallest m needed to generate k=48,\!500 is m=890,\!827, 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 m is found each time.

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

OneFour5000

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

OneFour40000

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 m for 49,998 is 470,324, and the m 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.

OneFour100.png

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 m for some k?  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 p=3 generates the following graph, so it seems that there may be similar behavior for various p.

OneFour5000p3

I plan to keep working on this little puzzle — although I think a proof of or counterexample to the One n 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….

Number Searches II

This week I’ll talk about the solution to the final puzzle from last week — so if you haven’t tried it yet and want to, now’s the time!

For reference, here’s the puzzle:

Day031Fig4

The hints were that all circled numbers in the grid were four digits long, and that every number in the grid was used at least once.  The object was to determine two bases:  the base used to write the numbers in the list, and the base used for the circled numbers in the grid.  Then the rest is easy!

To start, I chose the bases first.  My first attempt was to use 41 and 19, although this didn’t quite work out (for reasons we’ll soon see).  I didn’t want the numbers in the list to be too long, so I chose bases which weren’t too far apart.  The bases happened to be prime numbers — but later on I saw that this information really doesn’t help the solver at all.  No harm done, though.

Now the main issue was that I wanted the numbers both in the list and the grid to use only the digits 0–9.  So next I used a brute-force loop to check all numbers up to 10,000,000 which only used the digits 0–9 in base 41.  Of these, I checked which used only the digits 0–9 in base 19.  There were only 2640 numbers — not very many, actually, out of 10,000,000.  (I used Mathematica here, since using Python in the Sage platform would have been far too slow.  Also, it is very easy in Mathematica to convert numbers from one base to another using the functions “IntegerDigits” and “FromDigits.”)

But what was I going to do with these numbers?  I decided I wanted a solution strategy which didn’t use the ending 0 again — I had used this device twice already.  I thought that if I looked for numbers which were off by just 100 in base 41 in the grid — and made sure the solver had enough clues to determine the corresponding numbers in the list — well, I’d be making progress.

Let’s look at the puzzle for a moment, so you see what’s at play here.  Notice that the largest number is roughly three or four times the smallest (3 x 1 = 3 in any base larger than 3!).  But there are two small numbers close to each other — 14940 and 14965 — they can’t begin with 0, naturally, and there is only one number you can circle in the grid beginning with a 1.  So they must at least start with a 2.  But they can’t start with a 3 or greater, or else the largest numbers would have to start with at least a 9 — and 7 is the largest number in the grid.  Therefore the two smaller numbers must start with a 2, and the three largest must begin with a 7.

And you’ll notice that there are the two numbers 7034 and 7134 in the grid — off by 100.  But here was my problem — when I looked at my list of numbers which used only the digits 0–9 in both bases 19 and 41, I couldn’t find any which were 100 apart in base 41.

Then I realized why.  In base 41, 100 represents 412 = 1681.  And the base 19 digits of 1681 are 4, 12, and 9.  See the problem?  There’s no way to be off by 12 in the base 19 list using only the digits 0–9!

So I needed to find a base whose square could be written in base 19 using single digits.  It turns out that 41 wasn’t too far off….432 = 52619.  And if you notice, 45311 and 45837 are off by exactly 526.  Recall that since these are the largest numbers, they must be the ones beginning with a 7.  (Note that the other four-digit number in the grid, 7042, is between 7034 and 7134, and so must correspond to 45334.)

What does this mean algebraically?  Let’s denote by L the base used in the number list, and  let G be the base used in the grid.  To say that being off by 100G in the grid is the same as being off by 526L in the list is to say that

G2 = 5 L2 + 2 L + 6.

So this is one relationship between G and L.

Now there are two ways to proceed.  You might try to figure out another relationship between G and L using 7042 and 45334.  Note that 7042 is in fact G – 2 more than 7034 (observe that a carry is involved), and 45334 is 23 more that 45311.  This would mean that

G – 2 = 2 L + 3.

Alternatively, note that the smallest two numbers must be represented by 2154 and 2164 in the grid (2407 is too big, since the numbers are only 25 apart in base L).  But 2154 and 2164 are just 10 apart in base G, so

G = 2 L + 5,

which you’ll note is equivalent to the previous equation.

But we now have two equations in two unknowns — just substitute for G into the quadratic, rearrange terms and simplify, and you’ll end up with the quadratic equation

L2 – 18 L – 19 = 0.

It’s not hard to see (just factor!) that the only positive root of this equation is L = 19.  This means that

G = 2 x 19 + 5 = 43.

So we’re just about done!  I’ll leave it to you to do all the conversions from one base to the other.  But once we know the bases, the rest is easy.

Of course there was no way I could have created this puzzle without a computer — finding numbers which can be written with the digits 0–9 in two different bases is just too difficult to do by hand (at least for me).  But even when this was done, it  was not a trivial task.  I pored over the numbers, looking for ones with the “right” digits.  Since I wanted the largest numbers to begin with 7, I avoided 8’s and 9’s in the corners.  I thought the solver needed some entry point without having to go down too many dead ends.

And then, well, the numbers had to fit.  Since the corners are common to so many entries, I had to look for numbers which started and ended with suitable digits.  This took some creative juggling!

Finally, I wanted to make sure that there were numbers differing by 100 and 10 in the grid. Again, the solver needed an entry point into the puzzle.  Just writing a computer program to look at every single possibility could be done — but then why spend all the effort making a puzzle which can, in large part, be solved by hand?  Just randomly picking numbers and writing them in bases 19 and 43 would certainly have been possible, but far from interesting.

If you feel adventurous enough to create your own Number Search puzzle, please comment.  I’d love to see what others might do with this idea!

Number Searches I

It’s been some time since there have been any puzzles to solve.  I’ve created something new (well, as far as I know) just for my blog.  I hope you enjoy it!

Many puzzle magazines have puzzles where you need to find words or numbers hidden in a grid. They may be placed in a straight line horizontally, vertically, or diagonally, and may be written either backwards or forwards. Here’s one for you — find the numbers at the right in the grid on the left.

Day031Fig1

Looks like there’s not enough room? Well, there’s a twist in this puzzle. The numbers are written in base 10 on the right, but in the grid, they’re represented in a different base, which you need to determine. Now this is a bit trickier, so I’ll give you two hints. First, the base is a prime number. And second, all the numbers in the grid are used in the completed puzzle. We’ll work out the solution next — so if you want to try to solve it on your own, now’s the time.

Impossible?  Seems like it — until you notice where the 0’s are in the grid.  Since numbers don’t begin with a 0, and since you’re given that every number in the grid must be used — that means that some numbers end in a 0, meaning they’re a multiple of the base.  And since you’re given that the base is prime, that suggests looking at the prime factorizations of the numbers on the right.

You can look at some python code to find prime factorizations of numbers — both recursive and iterative versions.

112 24 . 7
373 prime
3181 prime
8533 7 . 23 . 53
11,665 5 . 2333
14,420 22 . 5 . 7 . 103
1,354,097 29 . 53 . 881

This table shows the prime factorizations of the numbers to be found in the grid.

So what do you notice?  Since at least two of the numbers end in 0 in the grid, at least two of the numbers must share a common prime factor.  The only prime factors that any numbers have in common are 2, 5, 7, and 53.

But note that there are the digits 8 and 9 in the grid — which means that the base must be at least 10.  This eliminates all possibilities except 53.

Alternatively, you can notice that any number on the right can be expressed using at most four digits in the “mystery” base.  Since 344 is only 1,336,336, the base must be at least 35.  This would also eliminate all options except 53.

Once you know the base, the rest is fairly straightforward — once you know how to write numbers in base 53!  Luckily, I’ve also written some python code to perform this task for you, as well.  It’s the usual algorithm — find the highest power of 53 less than the number (using logarithms), find the corresponding digit, subtract, and repeat.  You’re welcome to take out your pocket calculator, write your own code, or just use mine.  But there’s no avoiding this task.

Whatever the method, you should have come up with the following results in base 53, listed in increasing order: 26, 72, 171, 320, 485, 574, and 9530.  Below you’ll see the completed puzzle.

Day031Fig2

Where did this idea come from?  It’s never possible to say exactly where an idea “comes from.”  I was thinking about taking an ordinary puzzle and adding a new twist.  The idea of using different bases popped into mind.

Then the challenge was to create a puzzle that had some interesting feature — like the 0’s.  I knew that one way to solve the puzzle would be to write a computer program which would take all the numbers in the list, and write them in different bases starting (in this case) at 35.  Then see which lists could be found in the grid.  Not so very interesting.

But with the hint and two zeroes in the grid, well, I felt I was making some progress — and I hope you’ll agree….

Now I needed to come up with another puzzle or two — which were related to the example, but which didn’t simply require going through the same steps.  Maybe only one zero instead of two?  How was that much different?  I pondered for a few minutes, and came up with the following.

In the following Number Search puzzle, find the numbers on the right in the grid on the left (written in some prime base).  Fill in all the missing numbers (which are all single digits) in the grid, and find the missing number in the list on the right (which is in increasing order).  You know that every number in the grid is used in the completed puzzle, and that the missing number on the right does not end in 0 when circled in the grid.  Good luck!

Day031Fig3

Although likely a challenge if you’ve never done a puzzle like this before, I thought it must be possible to introduce still another level of difficulty for the truly dedicated solver.  So here’s another.

In the following Number Search puzzle, find the numbers on the right in the grid on the left.  The catch?  The numbers on the right are not written in base 10 (although they are all written in the same base), and the numbers to circle in the grid are also not in base 10 (although, again, they are all in the same base).  Your task to find both bases and solve the puzzle!

Day031Fig4

The bases are prime (but I don’t think that will actually help at all).  A few other hints:  as in a usual search puzzle, you can’t count “1011” and “1101” as two different numbers — once you circle a set of numbers, you can’t use it again in the reverse order.  Of course no number in the grid begins with “0.”  And finally, all circled numbers in the grid are four digits long, and every number is used at least once.  As a further tease, you can find out the bases with just a few lines of algebra — you only need a computer/calculator to convert from one base to the other!

Next week, I’ll explain how I designed the puzzle (and in doing so, give the solution as well) — there were two big hurdles.  First, the numbers had to use only the digits 0–9 in both bases.  And second, I wanted to be sure there was some way to solve it without an exhaustive computer search.  More next week.  Happy solving!

CrossNumber Puzzles

This week, we’ll look at one of my favorite types of puzzles — CrossNumber Puzzles. These are like crossword puzzles, except that the clues describe numbers instead of words. The only rule is that no entry in a CrossNumber Puzzle can start with a “0.” You can try this one — but don’t worry if you get stuck. We’ll look at different ways you can go about solving it in just a moment.

Day003Puzzle1

How would you go about solving this puzzle? Try to look for the clues which give you the most information. For example, look at 1 Across and 3 Down. Now 1 Across is the cube of a two digit number, and its third digit is actually the first digit of the cube root. So we might want to print out a chart of all four-digit cubes of two-digit numbers:

10 1000 16 4096
11 1331 17 4913
12 1728 18 5832
13 2197 19 6859
14 2744 20 8000
15 3375 21 9261

You can see that the only possibility is that 1 Across is 4913 and 3 Down is 17.

Looking at 5 Across doesn’t help much, since there are too many possibilities.

But looking at 5 Down is a good next choice. Note that 9 Across has to start with 1 or 3 in order to fit four odd digits in the grid, but no perfect squares end in 3, and so no perfect fourth powers end in 3, either.  This means that 9 Across has to start with 1 so that 5 Down ends in 1.  To help figure out 5 Down, below is a list of four-digit fourth powers:

6 1296 8 4096
7 2401 9 6561

So 5 Down must be either 2401 or 6561. If it were 2401, then 6 Across would begin with a “0,” so that leaves 6561 as the only option for 5 Down.

I’ll leave it to you to complete the puzzle. I won’t post a solution so that you’re not tempted to peek — but if you add 2 Down and 6 Across when you’re done, you’ll get 157,991.

How can you make your own CrossNumber puzzle? Start by making a grid, and shade in some of the squares. Usually the pattern of shaded squares is symmetric, but it doesn’t have to be. Fill in some of the entries with numbers which have specific properties, like being a perfect square or cube. Or perhaps make one of the entries the product or sum of two others. The only limit is your imagination! It might help to continue reading below, since then you could print different charts and look at the numbers for something interesting. (And get another puzzle to solve, too.)

Continue reading CrossNumber Puzzles