Maybe you remember that back in January, 2003, I offered you an increasing function that met two criteria (click the problem archives to see it). This month, I will challenge you with another increasing function that meets two criteria...

Let f map positive integers to positive integers with the conditions:

i) f(n+1) > f(n)
ii) f(f(n)) = 3n

Find f(955).

First, a lemma: n < f(n) < 3n

Proof:

First, the proof that n < f(n):

if f(n) <= n for any n, then f(f(n)) <= f(n), because f is increasing, so
f(f(n)) <= n, but f(f(n)=3n, a contradiction.

Next, the proof that f(n) < 3n

If we let m=f(n), then we just showed that m < f(m), so f(n) < f(f(n))
and f(f(n))=3n, so f(n) < 3n

In particular, the lemma tells us that 1 < f(1) < 3, so f(1)=2.

Thus f(2)=3

f(3)=f(f(2))=6, and f(6)=f(f(3))=9, so f(4) and f(5) are sandwiched between 6 and 9.  Since f is strictly increasing, the values of f(4) and f(5) are "pinned down" to 7 and 8, respectively.

Now we have established the following:

f(1)=2
f(2)=3
f(3)=6
f(4)=7
f(5)=8
f(6)=9

I'm going to stop now, and start over in base 3.

f(1)=2
f(2)=10
f(10)=20
f(11)=21
f(12)=22
f(20)=100

There's a pattern here, which is:

If the first base-3 digit of x is "1" then f(x) is x with the first "1" replaced with "2".

If the first base-3 digit of x is "2" then f(x) is x with the first "2" replaced with a "1", and a "0" appended to the end of it.

This function meets the conditions, because f(x+1)>f(x) and f(f(x)) replaces the first digit of x with a different digit, then replaces the result with the original digit, and a zero is appended to the end of it during one of the steps.  In short, f(f(x))=3x.

But is this the only function that meets the conditions?

It's the only function f(x) that meets the conditions when x is a 1-digit number; we've shown that.

Let's assume it's the only function f(x) that meets the conditions when x is an n digit number, and use induction to show it's the only function that meets the conditions when x is an n+1 digit base three number.

If x is an n-digit number of the form 1ddd then f(x)=2ddd, and f(2ddd)=1ddd0, so f(1ddd0)=2ddd0

So f(x) is the only function that meets the conditions when x is an n+1 digit multiple of 3 that begins with "1".

If x is an n+1 digit multiple of 3 beginning with "1", then f(x+3)=f(x)+3. (That's true even if x+3 begins with "2" -- f(12220+3)=f(20000)=100000=22220+3=f(12220)+3)

So in order for f(x+3) > f(x+2) > f(x+1) > f(x) it must be the case that f(x+2)=f(x)+2, and f(x+1)=f(x)+1

So for all n+1 digit numbers beginning with 1, f(1dddd)=2dddd.

Finally, let's look at the n+1 digit numbers beginning with 2.

If 2dddd is an n+1 digit number, then f(1dddd)=2dddd is the only function that meets the requirements, so f(2dddd)=1dddd0, proving that f(x) is the only function that meets the conditions when x is an n+1 digit base three number.

Now, to answer the question at hand…

955 base 10 = 1022101 base 3, and

1684 base 10 = 2022101 base 3, so

f(955)=1684

lee explained it better:

We have f(f(n))=3n, so f(f(1))=3.

But f is a increasing function, so f(1)=2, f(f(1))=f(2)=3

Let f(3^k)=p_k.  So p₀ = f(3⁰) = 2.

f(p_k) = f(f(3^k)) = 3^k+1.

p_k+1 = f(3^k+1) = f(f(p_k)) = 3p_k.

By induction, f(3^k) = p_k = 2*3^k.

Also by induction, f(2*3^k) = f(p_k) = 3^k+1.

Notice that the difference f(2*3^k) - f(3^k) is equal to 2*3^k - 3^k, which is equal to 3^k.

Since f is increasing, and the difference in values of f equals the difference in the arguments to f, it follows that f increases with a slope of 1 on the interval [3^k, 2*3^k]

So f(3^k+r) = f(3^k)+r = 2*3^k+r, where k is a nonnegative integer and 0 £ r £ 3^k.

And since 2*3^k+r = f(3^k+r), it follows that

f(2*3^k+r) = f(f(3^k+r)) = 3^k+1+3r, where k is a nonnegative integer and 0 £ r £ 3^k.

As a practical matter, any positive integer can be expressed as either 3^k+r or 2*3^k+r, where k is a nonnegative integer and 0 £ r £ 3^k.

955 happens to be 3⁶ + 226, so

f(955) = f(3⁶)+226 = 2*3⁶+226 = 1684