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 an 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.

Byinduction, 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