Liebeck’s sequence: a solution

In the puzzle we called “Liebeck’s sequence”, we asked the following.

Let a_1, \, a_2, \ldots be a sequence of positive integers such that for all n \geq 1, a_{n+1} > a_n and a_{a_n} = 3n. Find a_{100}.

The answer is: More or less 175.

This is a wonderful problem, in the sense that the more time you spend with it the more structure you see. I will show you how I think about it, but I am not claiming my way of thinking is the only one possible, and I am sure there are more elegant ways of doing it.

First of all, I do not like the notation, so let us change it. Let us write instead of a_n, f(n). In this new notation, the problem is: for every n \in \mathbb{N}, find f(n) if you know that f(n) \in \mathbb{Z}, f(n)>0, f(n+1)> f(n) for all n \in \mathbb{N} and f(f(n)):=f^2(n)=3n. In particular, compute f(100). Just to keep you on tenter-hooks (and what other sort is there?) I’ll tell you that offhand I know that f(100) is about 180.

I am going to go through everything in great detail, and even formulate a lemma, but do not be deceived: the problem requires nothing but clear thinking.

First of all we need to work out what is f(1). It cannot be 1, because then we would have 3=f(f(1))=f(1)=1 and as 3 \neq 1 this possibility has to be rejected. There is nothing to tell us that f(1) cannot be 2. But can it be 3? Well, if f(1)=3, then 3=f(f(1))=f(3), so both f(1) and f(3) are 3, which cannot be as f(3) must be strictly larger than f(1). A similar argument shows that f(1) cannot be larger than 3, so the only choice therefore is f(1)=2. Note how cunning this problem is: not only does it have a solution, but it has a unique solution!

Now we can step forward. If f(1)=2, what is f(2)? Well,

f(2)=f(f(1))=3.

What is f(3)?

f(3)=f(f(2))=6.

There does not seem to be any way of finding f(4) at this stage… So let us see what else we can find.

f(6)=f(f(3))=9.

Aha! If f(3)=6, and f(6)=9, we must have by the conditions of the problem (strict monotonicity of f(n)) that f(4)=7 and f(5)=8.

If we want f(100), it seems too boring to just go on computing values of f till we hit it, so we need to organise our computations.

First of all, the condition f(f(n))=3n shows that powers of 3 are privileged. In fact, if n=3^m, i.e. a power of 3, it looks as if it should be easy to compute f(n). We have f(1)=2, f(3)=6, f(6)=3^2=9, f(9)=18, and sooner or later you will get that

f(3^m)=2\cdot 3^m.

Note also that f(2\cdot 3^m)=3^{m+1}.

Of course luck would have that 100 is not at all divisible by 3. To do more we need to look for a way of organising our computations so that a pattern is seen. Overkill? No: everything worth doing is worth doing well. As Longfellow says,

In the elder days of Art,
Builders wrought with greatest care
Each minute and unseen part;
For the Gods see everywhere.

Worth remembering next time you hand your homework.

Have a look at the diagram below. Here an arrow between, say, f(2)=3 and f(3)=6 just means that f(f(2))=6, which we know. I have computed quite a bit, using the same logic of going forward a bit and then filling in the gaps. I have only done a couple of rows: the diagram is of course infinite (oh, the joy of being a mathematician!) but there is no need to go on.

This diagram, which we will call D, has a remarkable structure. A row in which neighbouring values of f differ by 3 is followed by a row in which they differ by 1. Let us formalise this in a lemma.

Lemma: In D, every row the arguments of f go either from 3^m to 2\cdot 3^m or from 2\cdot 3^m to 3^{m+1} for some integer m \geq 0. If two numbers k, l, are in a row in which the arguments go between 3^m and and 2\cdot 3^m, then f(k)-f(l)=k-l; and if the arguments go between 2 \cdot 3^m and 3^{m+1}, then f(k)-f(l)=3(k-l).

Check that this implies that f(11)=f(9)+2=20.

So now the strategy for finding f(100) is clear: find the row in which 100 is and use the lemma.

OK, the denouement is obvious: 100 is in the row in which the arguments go from 81=3^4 to 162=2\times 3^4, so

f(100)=f(81)+(100-81) =162+19=181.

Now let us put a different hat on. Suppose we are applied mathematicians. Can we do slightly worse than above by doing much less work? Yes, we can. Before that a digression, about Steve Smale and Marianne Anderson. Steve Smale, one of the greatest mathematicians of the XXth century, once said: “Applied Mathematics is Bad Mathematics”, which is both bizarre and wrong. It is bizarre because he himself has done quite a lot of great applied mathematics: mathematical economics; work on the simplex method; flocking recently. Marian Anderson, the American singer with a voice of unbelievable quality and range (try to find her singing Bach’s Jesus schläft, was soll ich hoffen) was reproached for singing spirituals. She answered: “There are only two types of music, good and bad.” Smale’s dictum is wrong because the boundaries of Pure and Applied mathematics are certainly not congruent to the boundaries between good and bad mathematics. There is lots of self-indulgent and badly motivated pure mathematics, and there are absolute gems of applied mathematics, for example almost every paper of J. B. Keller. And applied mathematics is a way of thinking.

In the Liebeck problem an applied mathematician would not have done any of the above calculations. She would have said: hang on, f(f(n))=3n. So if say f(n)=\alpha n, this means that \alpha^2=3, so \alpha=\sqrt{3}. So as a first approximation, f(100) \approx \sqrt{3}100 \approx 173, so the ball-park figure is 175. Which is not bad for a one-liner.

I would like to end with a problem which I do not know how to solve. The prize DoF offers is £20 for a student or a pint for a member of staff. Same prize for suggesting better follow-up problems.

Problem: (for a good applied mathematician): estimate |f(n)-\sqrt{3}n|.

Postscript.

While feeding the jackdaws, I became uneasy with the answer we’d got for f(100) and realised something remarkable. We deduced that

f(100)=f(81)+(100-81).

But by our formula for powers of 3, f(81)=2\times 81, so

f(100)=2\times 81+100-81 = 100+81=181.

So it looks as if “sometimes” to compute f(n) the only computation you have to make is to work out the power of 3 that is closest to n and smaller than it, and then add to that power of 3 the number n itself! No need to compute any fs. For example, f(12)=21=12+9. But this does not always work: f(7) =12 \neq 7+3.  Two questions arise. (a) Work out the exact rule (hint: use our lemma). (b) We had to go through a lot of computations to get to this simple (additive!) formula. Is there an easier way, that does not use the diagram D and all the computations it involves?   I do not know an answer to (b), but I would be surprised if it were “No”.

(MG)

Advertisements
This entry was posted in Puzzles. Bookmark the permalink.

One Response to Liebeck’s sequence: a solution

  1. Pingback: Liebeck’s sequence: an applied mathematician writes | Degree of Freedom

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s