If $f:\mathbb N\to\mathbb N$ such that $f\big(f(x)\big)=3x$, then find $f(2013)$.

Question

If $f:\mathbb N\to\mathbb N$ such that $f\big(f(x)\big)=3x$, then what is the value of $f(2013)$?

Answer 1

We can probably assume that $f$ is a strictly increasing function.

We know $f(f(1))=3$ so what is then $f(1)$? It can't be $3$ and can't be $1$, so we must have $f(1)=2$ and $f(2)=3$. We also need $6=f(f(2))=f(3)$, so $f(3)=6$. And so on. $9=f(f(3))=f(6)$, $18=f(9)$, $54=f(18)$...

From $f(3)=6$ and $f(6)=9$ we can derive that $f(4)=7$ and $f(5)=8$.

From that $f(7)=12$ and $f(8)=15$.

From that $f(12)=21$ and we know $18=f(9)<f(10)<f(11)<f(12)=21$ so we know that $f(10)=19$ and $f(11)=20$.

You can probably work your way up.

We also know $2013=3\cdot11\cdot61$ so we need $2013=f(f(11\cdot61))$ and so $f(2013)=3f(11\cdot61)$

But I expect there is an easier solution :)

Answer 2

We can define two functions $g$ and $h$ this way: $$g(0)=h(0)=0$$ $$g(3k)=3g(k)$$ $$g(3k+1)=3k+2$$ $$g(3k+2)=9k+3$$ $$h(3k)=3h(k)$$ $$h(3k+1)=9k+6$$ $$h(3k+2)=3k+1$$

You can easily check that $g$ and $h$ satisfy the condition of the problem, and that $g(2013)=6030$ and that $h(2013)=2010$, so we can't guess the value of $f(2013)$ with that only condition.

This idea can be generalized: Let $A$ be the set of natural numbers that are not multiple of $3$. Let $\{B,C\}$ any partition of $A$ (that is, $B\cup C=A$ and $B\cap C=\emptyset)$ with the only condition of that both sets are infinite. Take for example: squares and not squares, primes and not primes, etc. Since $B$ and $C$ are infinite and countable there is a bijection $\sigma$ from $B$ to $C$. In fact there are infinitely many of such bijections.

Now define: $f(0)=0$, $f(3k)=3f(k)$, $f(k)=\sigma(k)$ if $k\in B$ and $f(k)=3\sigma^{-1}(k)$ if $k\in C$. Let's prove that $f(f(x))=3x$ for all $x$ by induction. This is clearly satisfied for $x=0$.

Then, for each $x>0$ we have three possibilities:

• if $x$ is a multiple of $3$, then $x=3k$, so $f(f(x))=f(f(3k))=f(3f(k))=3f(f(k))=3\cdot3k=3x$ by the induction hypothesis. Note that $k<x$.
• if $x\in B$, then $f(f(x))=f(\sigma(x))=3\sigma^{-1}(\sigma(x))=3x$
• if $x\in C$, then $f(f(x))=f(3\sigma^{-1}(x))=3f(\sigma^{-1}(x))=3\sigma(\sigma^{-1}(x))=3x$

c.q.d.

It is clear that the concrete value of $f(2013)$ strongly depends on the chosen partition and on the chosen bijection for that partition.

In fact, I suspect that $f(2013)$ can be any multiple of $3$.

Answer 3

In what follows, I will construct a function $f$ (which is not increasing!) that satisfies $f(f(x)) = 3x$ for $x \in \mathbb N$ and $f(x) = 4026$.

How about we split up the multiplication by 3 into a multiplication b y 2 and one by 1.5? To that end, we'd need to detect if we've already multiplied our argument by 2 and then multiply it by 1.5.

So how can we detect that?

If we are given an odd number, then clearly we need to multiply by 2 because we have not already. If we take the simple function

$$ f_1(x) = \begin{cases} 2*x & \text{if $x$ is not divisible by 2}\\ x + x/2 & \text{otherwise} \end{cases} $$ Then this function shows the following behaviour (output from a script):

3 * 1 = 3 == 3 = f(2) = f(f(1))
3 * 2 = 6 == 6 = f(3) = f(f(2))
3 * 3 = 9 == 9 = f(6) = f(f(3))
3 * 4 = 12 != 9 = f(6) = f(f(4))
3 * 5 = 15 == 15 = f(10) = f(f(5))
3 * 6 = 18 == 18 = f(9) = f(f(6))
3 * 7 = 21 == 21 = f(14) = f(f(7))
3 * 8 = 24 != 18 = f(12) = f(f(8))

In other words, it has the property $f_1(f_1(x)) = 3x$ if $x$ is not divisible by 4. How can we fix that? This function does a better job:

$$ f_2(x) = \begin{cases} 2*x & \text{if $x$ is not divisible by 2}\\ x + x/2 & \text{if $x$ is not divisible by 4}\\ 2*x & \text{if $x$ is not divisible by 8}\\ x + x/2 & \text{otherwise} \end{cases} $$ where the first matching condition determines the value. This function shows the following behaviour:

3 * 1 = 3 == 3 = f(2) = f(f(1))
3 * 2 = 6 == 6 = f(3) = f(f(2))
3 * 3 = 9 == 9 = f(6) = f(f(3))
3 * 4 = 12 == 12 = f(8) = f(f(4))
3 * 5 = 15 == 15 = f(10) = f(f(5))
3 * 6 = 18 == 18 = f(9) = f(f(6))
3 * 7 = 21 == 21 = f(14) = f(f(7))
3 * 8 = 24 == 24 = f(12) = f(f(8))
3 * 9 = 27 == 27 = f(18) = f(f(9))
3 * 10 = 30 == 30 = f(15) = f(f(10))
3 * 11 = 33 == 33 = f(22) = f(f(11))
3 * 12 = 36 == 36 = f(24) = f(f(12))
3 * 13 = 39 == 39 = f(26) = f(f(13))
3 * 14 = 42 == 42 = f(21) = f(f(14))
3 * 15 = 45 == 45 = f(30) = f(f(15))
3 * 16 = 48 != 36 = f(24) = f(f(16))

In other words, it handles any $x$ that is not divisible by 16 properly. It is now straightforward to construct the function $f$.

Here's some common lisp code that implements $f$ and generates the above output.

(labels
    ((fn (x)
       (flet ((indivisible-by (x y)
                (/= 0 (mod x y))))
         (do ((k 1 (1+ k)))
             ((indivisible-by x (expt 2 k))
              (if (oddp k)
                  (* 2 x)
                  (+ x (/ x 2)))))))
     (fn-bits (x) ; Same function, more intuitive
       (flet ((count-trailing-zeroes (x)
                (do ((k 0 (1+ k)))
                    ((logbitp k x) k))))
         (if (oddp (count-trailing-zeroes x))
             (+ x (/ x 2))
             (* 2 x))))
     (g (x)
       (cond
         ((= 0 x) 0)
         ((= 0 (mod x 3)) (* 3 (g (/ x 3))))
         ((= 1 (mod x 3)) (+ x 1))
         ((= 2 (mod x 3)) (- (* 3 x) 3))))
     (h (x)
       (cond
         ((= 0 x) 0)
         ((= 0 (mod x 3)) (* 3 (h (/ x 3))))
         ((= 1 (mod x 3)) (+ (* 3 x) 3))
         ((= 2 (mod x 3)) (- x 1))))
     (f (x) (fn-bits x))) ;; Choose a function to test here
  (format t "==========================================~%")
  (format t "We have f(2013) = ~a.~%~%" (f 2013))
  (loop for x from 1 to 16 do
    (let* ((fx (f x))
           (ffx (f fx))
           (3x (* 3 x))
           (proper (= 3x ffx)))
      (format t "3 * ~a = ~a ~a ~a = f(~a) = f(f(~a))~%"
              x 3x (if proper "==" "!=") ffx fx x))))

The functions $g$ and $h$ are taken from @user2425's answer for comparison.

Update: Why does the function $f$ work as expected? Consider the input $x$ in binary representation and count the number of trailing zeroes. If I call this number $N$, what $f$ does is multiply $x$ by 2 if $N$ is even and by 1.5 if $N$ is odd.

If $N$ is odd, then $x$ is multiplied by 2 and afterwards, $N$ is even. If $N(x)$ is even, then $N(x/2)$ is odd and so is $N(x+x/2)$. Consequently, $N$ is odd after a multiplication by $1.5.$