Since it's a strictly increasing arithmetic progression, it can be written as $f(n)=3+d(n-1)=dn+(3-d)$ for some $d>0$

I've got a different answer from @above so idk if its right but anyway.... Let $f(3) = c$. Obviously since $f$ is strictly increasing, $c \ge 5$. Now, we have that $f(1), f(f(1)), f(f(f(1))) = 3, c, f(c)$ are in AP $\implies f(c) = 2c-3$. But since $f$ is strictly increasing, we have that $f(n+k) \ge f(n) + k$ and since $f(3) = c$, $f(c) \ge 2c-3$ and equality only holds when $f(3+k) = c+k$ and so we have determined all values of $f$ from $3$ to $c$. Next, since $c, f(c), f(f(c)) = c, 2c-3, f(2c-3)$ are in AP, we have that $f(2c-3) = 3c-6$ and so once again we get that the function must increase by exactly one again. Repeating this again and again, we have that $f(n) = n+c-3$ for all $n \ge 3$. Since we're given that $f(1) = 3$, $f(2)$ can be any value from $4$ to $c-1$. So, the solution to this is: $f(n) = \begin{cases} 3 & n=1 \\ k & n=2 \\ c+n-3 & n \ge 3 \end{cases} $ where $c,k \in \mathbb{N}^2$ such that $3 < k < c$ and $c \ge 5$, which indeed works

@above your solution is correct. We have that the only peruvian function is: $$f(n) = \begin{cases} 3 & n=1 \\ k & n=2 \\ n+c-3 & n \geq 3 \end{cases}$$where $ 3< k < c$ and $c \geq 5$. First of we notice that $a_n=f^{n}(1)=f^{n-1}(3)$, where $f^{n}$ is the function iterated $n$ times over and over again. Now we notice by induction that $f^{n+1}(3)=(n+1)f(3)-3n$, this we easily verify because we have to have that $f^n(3)-f^{n-1}(3)=f^{n-1}(3)-f^{n-2}(3)$, where $n \geq 2$. We can say for $f^n(3)-f^{n-1}(3)=f^{n-1}(3)-f^{n-2}(3)$, that this represents the number of naturals in the interval $[f^{n-2}(3),f^{n-1}(3)]$ is equivalent to the number of naturals in the interval $[f^{n-1}(3),f^{n}(3)]$, we know that there exists a bijection between the two intervals, i.e. a correspondance. That means that we have that our function is of the form, whenever $n \geq 3$, $f(n)=n+g$, where $g$ is constant natural number. Since we have that $f^3(3)-f^2(3)=f^2(3)-f(3)=c-3$, we easily get that $g=c-3$. Now let's see about $f(2)=k$, we need to have that $f(2) > 3$ but at the same thime it must be $f(2) < f(3)=c$, meaning that $3 < k <c$, from this we must have that $k \geq 4$, this implies that $c \geq 5$.

Oh, I took $f$ as polynomial, @below thanks.

Jalil_Huseynov wrote: @above and @2above , I got diffent answer, did I make any mistake? We have that $a_1=f(1)=3, a_2=f(3)=3+d, a_3=f(3+d)=3+2d,..., a_{n+1}=f(3+(n-1)d)=3+nd$. Since $a-b\mid f(a)-f(b)$ we get $a_n-1\mid a_{n+1}-3 \implies 2+(n-1)d\mid nd\implies 2+(n-1)d\mid d-2$. Obviously if $d\ne 2$ sending $n$ to infinity gives contradiction, so $d=2$. Hence, $f(n)=n+2$ for all odd $n$. But since $f$ is strictly increasing, $f(n)=n+2$ for all $n\in\mathbb{N}$. So only such function is $f(n)=n+2$. $a-b | f(a)-f(b)$ generally only applies when $f$ is a polynomial, and here $f$ can be any function $\mathbb{N} \rightarrow \mathbb{N}$. Therefore you cannot use $a-b | f(a)-f(b)$.