Assume strictly monotone increasing function; such that $f:N^{+}\to N^{+}$, $h$ for all $n\in N^{+}$, $$f(f(f(n)))=f(f(n))\cdot f(n)\cdot n^{2015}$$

Prove or disprove:$f(n)=n^{13}$

Put $n=1,f(1)=m$ $$f(f(m))=mf(m)$$ Put $n=m$, $$f(f(f(m)))=f(f(m))f(m)m^{2015}\Longrightarrow f(mf(m))=m^{2016}(f(m))^2$$ What about following?

  • 9
    $\begingroup$ It seems likely to me that this is from some contest. I added the relevant tag because that will attract users who have a lot of experience with this kind of problems. $\endgroup$ Jun 3, 2015 at 7:08
  • 1
    $\begingroup$ @abandon, $f(n)=n^{13}$ is a solution - just substitute and check it. We need prove that there are no other solutions? $\endgroup$ Jun 3, 2015 at 10:06
  • 5
    $\begingroup$ Where is this question from? A Chinese competition? $\endgroup$ Jun 5, 2015 at 20:57
  • 1
    $\begingroup$ Why people are reluctant to prove statements by assuming they're true I'll never know... $\endgroup$
    – Zach466920
    Jun 7, 2015 at 0:59
  • 4
    $\begingroup$ Well, the strictly increasing bit definitely matters - otherwise, we can just construct $f$ piecemeal by, at each step, choosing the smallest $n$ we've not yet defined $f(n)$ for, and defining $f(n)$ to be, say, the $n^{th}$ prime and $f(f(n))$ to be some arbitrary number factoring into only the first $n$ primes, and then use the equation for all higher iterates. Using prime factorizations, you can find that the trajectories $f^{k}(n)$ never intersect under this process, so it works indefinitely. This $f$ is probably not strictly increasing though. $\endgroup$ Jun 7, 2015 at 2:31

3 Answers 3


Let us denote by $f^{[k]}(n)$ the $k$th iterate of $f$. I cannot prove the claim, but I can prove that for all integers $n>1$ we have $$ \lim_{k\to\infty}\frac{\log f^{[k+1]}(n)}{\log f^{[k]}(n)}=13. $$ This is some kind of asymptotic evidence in favor of $f(n)=n^{13}$ being the only solution - alas, anything but conclusive.

This is seen as follows. We first prove that for all $k\ge3$ we have $$ f^{[k]}(n)=f^{[2]}(n)^{A_k} f(n)^{B_k} n^{C_k}\qquad(*) $$ for the sequence of vectors of positive integer determined by the recurrence relations $$ \left(\begin{array}{r} A_2\\B_2\\C_2\end{array}\right)=\left(\begin{array}{r} 1\\0\\0\end{array}\right),\qquad \left(\begin{array}{r} A_{k+1}\\B_{k+1}\\C_{k+1}\end{array}\right)=M\left(\begin{array}{r} A_k\\B_k\\C_k\end{array}\right), $$ where $M$ is the $3\times3$ matrix $$ M=\left(\begin{array}{crr} 1&1&0\\1&0&1\\2015&0&0\end{array}\right). $$ The proof follows from the given functional equation of $f$ by induction on $k$. The case $k=3$ is exactly the functional equation. The inductive step follows from the induction hypothesis by substituting $f(n)$ in place of $n$ and again applying the given functional equation.

The eigenvalues of $M$ are $\lambda_1=13$ and $\lambda_{2,3}=-6+i\sqrt{119}$. The key is that of these $\lambda_1$ has the largest absolute value. Furthermore, if we write the vector $$ (A_2,B_2,C_2)^T=x_1e_1+x_2e_2+x_3e_3 $$ in terms of unit eigenvectors $e_1,e_2,e_3$ belonging to the respective eigenvalues, we see that $x_1\neq0$.

For any $k\ge3$ we then have $$ (A_k,B_k,C_k)^T=\lambda_1^{k-2}x_1e_1+\lambda_2^{k-2}x_2e_2+\lambda_3^{k-2}x_3e_3. $$ For very large values of $k$ the first component dominates, and consequently $$ \lim_{k\to\infty}\frac{A_{k+1}}{A_k}=\lim_{k\to\infty}\frac{B_{k+1}}{B_k}=\lim_{k\to\infty}\frac{C_{k+1}}{C_k}=13. $$ It takes a while to see these limits if you calculate them. For some numerical support I fired up my Mathematica. The entrywise ratios of $M^{129}$ and $M^{128}$ are all in the interval $(12.9,13.2)$.

The claim follows from this by taking logarithms from $(*)$.

I don't know if this helps. It does seem to me that we should concentrate on large values of $n$ and asymptotics first. If only we could prove that $f$ must be a homomorphism of multiplicative monoids. Then it being strictly increasing would force it to a power function, and we know the exponent. If we know that $f$ is a power function the exponent can be determined without resorting to the above asymptotic gymnastics.

  • $\begingroup$ Used exponential model is not single and gives a simple proof. $\endgroup$ Jan 28, 2020 at 4:34


$h(n) = \dfrac{f(f(f(n)))}{f(f(n))\cdot f(n)} = n^{2015} $

Suppose $f(n) = n^{k}$:

$\dfrac{n^{k^3}}{n^{k^2 + k}} = n^{2015} $

$k^3 - k^2 - k - 2015 = 0$

which has solutions of $\{13, -6 \pm i \sqrt{119} \}$. The complex solutions oscillate, so $k = 13$. Clearly, $h(n)$ is unique and of the form $n^k$, and there's only one mapping from $f$ to $h$, so $f(n$) is unique.

EDIT: Regarding solutions not of the form $n^k$, define $g(n) = f(f(n))$

$f(g(n)) = g(f(n)) = g(n) \cdot f(n) \cdot n^{2015} $

We have to deal with the $n^{2015}$ term as it is of the form $n^k$. Suppose that $f(n) = \dfrac{l(n)}{n^{a}}$ and $g(n) = \dfrac{m(n)}{n^{b}}$ where $a+b = 2015$ and $l$ and $m$ are non-power series solutions by hypothesis:

$\dfrac{l\left(\dfrac{m(n)}{n^b}\right)}{n^a} = \dfrac{m(n)}{n^{b}} \cdot \dfrac{l(n)}{n^{a}} \cdot n^{2015}$

$l\left(\dfrac{m(n)}{n^b}\right) = m(n) \cdot l(n) \cdot n^{2015 - b}$

but $f(g(n)) = g(f(n))$, so

$\dfrac{m(l(n))}{n^b} = m(n) \cdot l(n) \cdot n^{2015 - b}$

$m(l(n)) = l(n) \cdot m(n) \cdot n^{2015} $

Which is what we started with. Therefore, both $f(g(n))$ and $g(f(n))$ must produce $n^{2015}$, but neither $f(n)$ nor $g(n)$ may contain $n^{\pm q}$ by hypothesis and then redundancy.

  • 7
    $\begingroup$ What about solutions not in the form $n^k$? $\endgroup$
    – Teoc
    Jun 8, 2015 at 22:32
  • 4
    $\begingroup$ I'm afraid I'm joining in Lenin's criticisim.The part about non-monomial solutions is anything but convincing. For starters, what are the functions $l(n)$ and $m(n)$ and the parameters $a,b$. They are not uniquely determined by $f(n)$! Also, I don't see how you jumped to the conclusion that $b=2015$. Are you assuming that $f(n)$ is a polynomial or something? As much as I want to see you find a solution that's a huge gap right there. $\endgroup$ Jun 11, 2015 at 4:28
  • 2
    $\begingroup$ What do you mean by "both $f(g(n))$ and $g(f(n))$ must produce $n^{2015}$"? What do you mean when you say that neither $f(n)$ nor $g(n)$ may contain $n^{\pm q}$? I honestly don't have a clue. $\endgroup$ Jun 11, 2015 at 16:52
  • 3
    $\begingroup$ @user121330, I see the positive contribution of the first part of your answer: You show that among the power maps the 13th power is the unique one satisfying the functional equation. I don't understand why the complex solutions oscilate and I don't understand why this implies $k=13$. I understand that a complex exponent will yield no map from $\Bbb{N}$ to $\Bbb{N}$. From the second part of your answer I understand nothing. What are you proving? What are the assumptions? I recommend restrict yourself to the positive contributions and explain that you show uniqueness in the case of power maps. $\endgroup$
    – san
    Jun 11, 2015 at 21:49
  • 1
    $\begingroup$ For example, if $$f(3):=2^{13}+1,\ f(2^{13}+1)=2^{169}+1,\ f(2^{169}+1)=(2^{13}+1)(2^{169}+1)3^{2015},$$ $$f((2^{13}+1)(2^{169}+1)3^{2015})=(2^{13}+1)(2^{169}+1)3^{2015}(2^{169}+1)(2^{13}+1)^{2015},...,$$ what are the functions $l$ and $m$ an 3 or on $2^{13}+1$? $\endgroup$
    – san
    Jun 12, 2015 at 0:37

No, there are many such functions. For convenience (to avoid writing $\mathbb{N}^+$ too much) my intervals will only consist of natural numbers, so I'll write $[a, b]$ to mean $\mathbb{N}^+ \cap [a, b]$ and $(a, b)$ to mean $\mathbb{N}^+ \cap (a, b)$ below.

Consider any $f$ defined as follows: first let $f(1) = 1$ and $f(n) = n^{13}$ for $n$ of the form $n = 2^{13^k}$ ($k \geq 0$), so clearly $f$ satisfies the functional equation for $n = 1, 2^{13^k}$. We'll now inductively define $f$ on $A_k = [2^{13^k}, 2^{13^{k+1}}]$ for each $k \geq 0$, so that $f$ is strictly increasing on $A_k$. Note that since we already have $f(2^{13^k}) = 2^{13^{k+1}}$ and $f(2^{13^{k+1}}) = 2^{13^{k+2}}$, $f$ being strictly increasing will imply $f^{-1}(A_{k+1}) = A_k$.

First, for $k = 0, 1$, let $f|(2^{13^k}, 2^{13^{k+1}})$ be any strictly increasing function from $(2^{13^k}, 2^{13^{k+1}})$ to $(2^{13^{k+1}}, 2^{13^{k+2}})$ (where there is at least one such function since the second set is larger than the first), so clearly $f$ is increasing on $[2^{13^k}, 2^{13^{k+1}}] = A_k$.

Now let $k \geq 2$. Assume we've defined $f$ on $A_0, \dots, A_{k-1}$, hence on all $n \leq 2^{13^k}$. We define $f$ on $A_k$ in two steps. First, to ensure that $f$ satisfies the functional equation, we only need to correctly set the values of $f(f(f(n)))$, i.e. to correctly set the values of $f(a)$ for $a$ in the image of $f^2$. Since our $f$ will satisfy $f^{-1}(A_{i+1}) = A_i$ for each $i$, the image of $f^2$ in $A_k$ will be exactly $f(f(A_{k-2}))$; we already know these points since we've defined $f$ on $A_{k-2}$ and $A_{k-1}$. Second, since the definition in the first step will actually guarantee that $f$ is strictly increasing on the image of $f^2$, to make $f$ strictly increasing on all of $A_k$ we only need check that that there's enough room to assign $f$-values to the remaining points.

Step 1: Defining $f$ on $f(f(A_{k-2}))$. Write $f(f(A_{k-2})) = \{a_0, \dots, a_r\}$ where $a_0 < a_1 < \cdots < a_r$, so in particular since $f(f(2^{13^{k-2}})) = 2^{13^k}$ and $f(f(2^{13^{k-1}})) = 2^{13^{k+1}}$ we have $a_0 = 2^{13^k}$ and $a_r = 2^{13^{k+1}}$. For each $a_i$ we have $a_i = f(f(m_i))$ for some $m_i \in A_{k-2}$, hence for $0 < i < r$ we define $$f(a_i) := f(f(m_i)) f(m_i) m_i^{2015} = a_i f(m_i) m_i^{2015}$$ by necessity (to satisfy the functional equation), where this already holds for $i = 0, r$. Note that $m_0 < m_2 < \cdots < m_r$ since $f^2$ is strictly increasing on $A_{k-2}$.

Step 2: Defining $f$ on $A_k \setminus f(f(A_{k-2}))$. Having now defined all $f(a_i)$, we define $f$ on each $(a_i, a_{i+1})$ to be any strictly increasing function $(a_i, a_{i+1}) \to (f(a_i), f(a_{i+1}))$. There is more than one such function since \begin{align*} f(a_{i+1}) - f(a_i) &= a_{i+1} f(m_{i+1}) m_{i+1}^{2015} - a_i f(m_i) m_i^{2015} \\ &> (a_{i+1} - a_i) f(m_i) m_i^{2015} \\ &> a_{i+1} - a_i \end{align*} which means $|(f(a_i), f(a_{i+1}))| > |(a_i, a_{i+1})|$. $f$ is now defined and strictly increasing on each $[a_i, a_{i+1}]$, so it's defined and strictly increasing on $[a_0, a_r] = A_k$.

After the induction, we've defined an $f$ which is strictly increasing on each $A_k$, hence strictly increasing on all of $\mathbb{N}^+$. The functional equation holds, since for any $n \neq 1$, we have $n \in A_k$ for some $k$, hence by our definition of $f$ at $f(f(n)) \in A_{k+2}$, $f$ satisfies the functional equation at $n$. To conclude, note that for each $k$ we made at least one choice (since $|A_k| > |A_{k-2}|$, so the set $A_k \setminus f(f(A_{k-2}))$ is nonempty). This means there are uncountably many (at least $|2^{\mathbb{N}}|$) functions $f$ which can be constructed this way, each of which is strictly increasing and satisfies the functional equation.

  • $\begingroup$ Sadly, but these ideas does not lead to additional solutions. I've tried to obtain any solution, and my answer demonstrates that $n^{13}$ is asymptotic solution and why the infinity series of deviations can not exist. $\endgroup$ Jan 28, 2020 at 3:02
  • 3
    $\begingroup$ I've looked over your solution, but it's not clear to me what you mean when you say $n^{13}$ is the "asymptotic solution", and I also don't know what you mean by the "infinity series of deviations" $\endgroup$
    – user125932
    Jan 28, 2020 at 3:06
  • $\begingroup$ The asymptotic is proved clearly, so every additional solution can be considered in the terms of deviations. Every deviation near $n$ requires monotonic correctives near $f(n),$ which can not be provided (see the tables). If $n=2,$ then $2^{13}=8192,$ but solutions of monotonity conditions are bounded with value $45.$ $\endgroup$ Jan 28, 2020 at 3:30

You must log in to answer this question.