1

question -

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that

(a) $f(m)<f(n)$ whenever $m<n$

(b) $f(2 n)=f(n)+n$ for all $n \in \mathbb{N} ;$

(c) $n$ is a prime number whenever $f(n)$ is a prime number.

Find $f(2001)$

my try -

i know this question is already been answered Solving Olympiad functional equation but my doubt is not clear thats why i am asking again ...

now i proved that By induction,$f(n)=f(1)+n-1$ for all $n \in \mathbf{N} .$ Suppose $f(1)=m>1$ The the numbers $(m+1) !+2,(m+1) !+3, \dots,(m+1) !+$ $(m+1)$ are all composite. Take the least prime $p$ exceeding $(m+1) !+(m+1) .$ Set $n=p-m+1 .$ Then $p=f(n)$ and hence $n$ is a prime. ....

then hint says But $n>(m+1) !+2$ and hence $p>n>(m+1) !+(m+1) .$ This contradicts the minimality of p

i dont understand why $n>(m+1) !+2$ and hence $p>n>(m+1) !+(m+1) .$ ????

thankyou

Ishan
  • 1,725

1 Answers1

1

You have $p$ being the smallest prime such that

$$p \gt (m+1)! + (m+1) \tag{1}\label{eq1A}$$

Thus, you have

$$\begin{equation}\begin{aligned} n & = p - m + 1 \\ & \gt ((m+1)! + (m+1)) - m + 1 \\ & = (m+1)! + 2 \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Next, using \eqref{eq2A} and $f(1) = m$, you have

$$\begin{equation}\begin{aligned} f(n) & = f(1) + n - 1 \\ f(n) & = m + (p - m + 1) - 1 \\ f(n) & = p \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Thus, by condition (c), you have that $n$ is a prime number. However, since $m \gt 1$, you have $n = p - m + 1 \lt p$. Thus, using this & \eqref{eq2A}, you have $n$ is a prime with

$$(m+1)! + 2 \lt n \lt p \tag{4}\label{eq4A}$$

Note $p$ was defined to be the smallest prime exceeding $(m+1)! + (m+1)$, and since $(m+1)! + 2$, $(m+1)! + 3$, $\ldots$, $(m+1)! + (m+1)$ are all composite, means it's also the smallest prime exceeding $(m+1)! + 1$. However, $n$ is supposed to also be a prime but less than $p$ but more than $(m+1)! + 1$. This contradicts $p$ being the smallest prime defined in \eqref{eq1A}, showing you can't have $f(1) = m \gt 1$ and, thus, you must instead have $f(1) = 1$.

John Omielan
  • 47,976