Dear Uncle Colin,

Someone gave me the puzzle:

  • $ff(n) = 3n$ for all real $n$,
  • $f(n)$ is a positive integer for all positive integer $n$
  • $f(n+1) > f(n)$ for all positive integer $n$
  • What is $f(13)$?

Any ideas?

Functions? Fun? No.

Hi, FFN,

This is a fun puzzle! Here’s how I tackled it:

  • $ff(1) = 3$, so I reckon $f(1) = 2$ and $f(2)=3$

This takes a little unpicking; $f(1)$ can’t be 1, or else $ff(1) = 1$. Could it be 3, and $f(3)=3$? again, no: $f(3) > f(2) > f(1)$. So, it has to be 2, and $f(2) = 3$.

  • We know that $ff(2) = 6$ and $f(2) = 3$, so $f(3) = 6$.

  • Now $ff(3) = 9$, so $f(6) = 9$

Let’s take stock:

  • $f(1) = 2$
  • $f(2) = 3$
  • $f(3) = 6$
  • $f(6) = 9$

That means $f(4) = 7$ and $f(5) = 8$, if we want to satisfy the “increasing” condition.

  • We know $ff(4) = 12$ and $f(4) = 7$, so $f(7) = 12$.
  • Similarly, $ff(5) = 15$ and $f(5) = 8$, so $f(8) = 15$.

There’s a pattern emerging!

  • $f(1) = 2$
  • $f(2) = 3$
  • $f(3) = 6$
  • $f(4) = 7$
  • $f(5) = 8$
  • $f(6) = 9$
  • $f(7) = 12$
  • $f(8) = 15$

I reckon, loosely, it goes up in threes up to a power of 3, then up in ones until reaching double a power of three.

If that’s true, we expect $f(9) = 18$, then increases of one until we reach $n=18$.

Indeed, $ff(6)=18$, so $f(9) = 18$; $ff(7)=21$, so $f(12)=21$ (filling in 10 and 11 automatically); $ff(8) = 24$, so $f(15)=24$, which makes $f(13) = 22$.

Is there an explicit form for this? Yes, but you’re not going to like it.

Notice that $f\br{3^k} = 2\br{3^k}$ and $f\br{2\br{3^k}} = 3^{k+1}$ for integer $k$; the function is linear between those points.

If we divide $n$ by the preceding power of 3 and truncate the result, we get either 1 or 2; if it’s a 1, we’re in the part with gradient 1 and if it’s a 3, we’re in the part with gradient 3. Equivalently, we can look at the fractional part of $\log_3(n)$: the truncated result being 1 is the same as that fractional part being less than $\log_3(2)$.

So! If the fractional part of the base-three log is less than $\log_3(2)$, and the integer part of it is $k$, we’re on a segment with gradient 1 passing through $\br{3^k, 2\br{3^k}}$.

If it’s larger than $\log_3(2)$, then our segment has gradient 3 and passes through $\br{3^{k+1}, 2\br{3^{k+1}}}$.

Putting this all together gives:

$f(n) = \begin{cases} n + 3^k & {\log_3(n)-k \le \log_3(2)} \ 3n - 3^{k+1} & \floor{\log_3(n)-k> \log_3(2)}\end{cases}$,

where $k = \floor{\log_3(n)}$.

I told you you wouldn’t like it, but I hope it helps!

- Uncle Colin

* Thanks to @benjamin_leis, who first sent me the puzzle