For each positive integer $k$, let $d(k)$ be the number of positive divisors of $k$ and $\sigma(k)$ be the sum of positive divisors of $k$. Let $\mathbb N$ be the set of all positive integers. Find all functions $f: \mathbb{N} \to \mathbb N$ such that \begin{align*} f(d(n+1)) &= d(f(n)+1)\quad \text{and} \\ f(\sigma(n+1)) &= \sigma(f(n)+1) \end{align*}for all positive integers $n$.
Problem
Source: 2023 Thailand Online MO P5
Tags: number theory, Number theoretic functions, Arithmetic Functions, functional equation
laikhanhhoang_3011
13.02.2023 03:11
Lemma 1: $x=d(x+1),(*) \leftrightarrow x \in \left\{2;3 \right\}.$
Proof:
$\,$ Let $x+1=2^a.3^b.p_1^{e_1}...p_k^{e_k}.$
$\,$ Then $(*) \leftrightarrow 2^a.3^b.p_1^{e_1}...p_k^{e_k}=(a+1)(b+1)(e_1+1)(e_2+1)...(e_k+1)+1.$
$\,$ Note that, for any $ p\geq 5,$ we have: $p^k \geq 4k+1;$ $3^a \geq 2a+1$ and $2^a \geq max \left\{ 2a;a+1 \right\}.$
$\,$ If $x+1$ has a prime divisor $\geq 5,$ or $e_1 \geq 1,$ then \begin{align*}x+1 & \geq (a+1)(2b+1)(4e_1+1)...(4e_k+1) \\
& =(a+1)(b+b+1)(3e_1+e_1+1)...(4e_k+1) \\
& \geq (a+1)(b+1)(e_1+1)...(e_k+1)+3e_1 \\
& \geq (a+1)(b+1)(e_1+1)...(e_k+1)+3>d(x+1)+1,
\end{align*}$\,$ adsurb.
$\,$ So $x+1=2^a.3^b,$ $(a+1)(b+1)+1=d(x+1)+1=x+1=2^a3^b.$
$$ \Rightarrow (a+1)(b+1)+1 \geq 2a(2b+1)+1 $$$\,$ $ \leftrightarrow 2 \geq 3ab+a.$ Thus, $\left\{a;b \right\}=\left\{2;0 \right\}, \left\{0;1 \right\}.$ Or $x \in \left\{2;3 \right\}.$
q.e.d
$$\left\{\begin{matrix}f(d(n+1))=d(f(n)+1), (1)
& & \\f\left ( \sigma (n+1) \right )=\sigma \left ( f(n)+1 \right ), (2)
& & \\
\end{matrix}\right.$$$\bullet$ Let $n=3$ in $(1),$ from Claim 1, we get: $f(3)\in \left\{2;3 \right\}.$
$\bullet$ Let $n=1$ in $(2),$ we get: $\sigma\left ( f(1)+1 \right ) =f(3) \in \left\{2;3 \right\}.$
But there is no positive $x$ such that $\sigma(x)=2 \rightarrow f(3)=3 \rightarrow \sigma\left ( f(1)+1 \right ) =3 \rightarrow f(1)=1.$
Claim 1: $f(2^k-1)=2^k-1, \forall k.$
Proof:
$\,$ I'll prove this by induction, the case $n=1,2$ is already proved.
$\,$ If $f(2^k-1)=2^k-1,$ let $n \rightarrow 2^k-1$ in $(2),$ we get: $$f \left( \sigma \left(2^k \right) \right)= \sigma \left( f\left(2^k-1 \right)+1 \right)= \sigma \left( 2^k \right) \leftrightarrow f \left( 2^{k+1}-1 \right)= 2^{k+1}-1 .$$q.e.d
$\bullet$ For any $k,$ let $x \rightarrow 2^k -1$ in $(1),$ we get: $$f\left ( d\left ( 2^k \right ) \right )=d\left ( f\left ( 2^k-1 \right ) +1\right )=d\left ( 2^k \right )\leftrightarrow f(k+1)=k+1.$$Thus, $$f(n)=n, \forall n.$$
Q.E.D