Proposed by Maxim Li This was also ELSMO #3

Progress but like this problem is troll anyway so uh yeah Also @2above the problem originally states the function is $\mathbb{N} \rightarrow \mathbb{N}$

LaTeX code: Find all pairs of positive integers $(a,b)$ for which there exists a function $f:\mathbb{N}\to \mathbb{N}$ satisfying $$f^{f(n)}(n) = an+b$$ for all positive integers $n.$

I'm not sure if the construction I have is well-defined. Please tell me if it doesn't work. CANBANKAN wrote: Find all ordered pairs of integers $(a,b)$ such that there exists a function $f$ satisfying $$f^{f(n)}(n)=an+b$$ For all $n\in \mathbb{N}$. The answer is all pairs $(a,b)$ such that $a\neq 1$. First, we must prove that there is no such function $f$ when $a$ is $1$ and $b$ is a positive integer. The idea here is similar to IMOC 2017 A7: Define the sequence $a_k := f^k(1)$ for $k\ge 0$. For any $0\le i < b$, consider the least $t$ in the sequence such that $t\equiv i \pmod b$. If we let $I_x$ be the non-negative integer such that $a_{I_x} = x$ for any $x$ in the sequence (note that this is unique since $f$ is injective), then we have $I_{m+b}=I_m+f(m)$ for all $m$ in the sequence. Thus, $$I_{t+nb}=I_t+\sum_{j=0}^{n-1}f(t+jb) >\frac{n^2}{2}$$for all non-negative integer $n$. This means that there are at most $\sim b\sqrt{2n}$ numbers in the first $n$ terms of the sequence, a contradiction. Now, we'll move on to the construction for the case where $a>1$. Define generators to be numbers not in the form $an+b$ for some $n\in\mathbb{N}$. Note that, in contrast to the previous case, there are infinitely many generators. In fact, there are at least $\frac{n-1}{2}$ generators with values no more than $n$ for any $n\in\mathbb{N}$. The main idea is that we want to construct infinitely many sequences $\{a_i\}_{i\ge 0}$ that are a partition of positive integers and satisfies the equation $f(a_k)=a_{k+1}$. For each sequence, we will sequentially choose the value for each term with the following condition: whenever we write the value for $a_k$ (with $k>0$), we will "register" the index $a_k+k-1$. Note that, according to the given equation, the value at this index must be equal to $a(a_{k-1})+b$. To ensure that all generators will be chosen, $a_0$ will be the smallest unchosen generator. Now, for $a_k$ with $k>0$, we will consider two cases: If the index number $k$ is not registered, let $a_k$ be the smallest unchosen generator which is at least $1521$ times greater than $at+b$ for any number $t$ that is already written in the current sequence and at least $59319$ times greater than all registered indexes. After this, we must register the index $a_k+k-1$ and write $a(a_{k-1})+b$ at this index per our condition then, as we have just written a new value, also register the index $a_k+k+a(a_{k-1})+b-2$. If the index number $k$ is already registered, then by this point, the value of $a_k$ must already be written and the index $a_k+k-1$ must already be registered. Again, write $a(a_{k-1})+b$ at this index per our condition then, as we have just written a new value, also register the index $a_k+k+a(a_{k-1})+b-2$. This will be well-defined if we never register the same index twice. To ensure this, we prove the stronger condition: we never register the same or consecutive indexes. This is clearly true when we define $a_0$. Now, as we define $a_k$ for any $k>0$, if $k$ has never been registered, then the condition for the value of $a_k$ ensures that the new registered indexes are far greater than previously registered ones. On the other hand, if $k$ has been registered, then, as we haven't break the condition yet, ${k-1}$ must not be registered and thus $a_{k-1}$ was the "largest generator" we've chosen so far. The condition then implies that $a_k+k+a(a_{k-1})+b-2$ must be far greater than $a_{k-1}+k+a(a_{k-2})+b-3$, which was previously the largest registered indexes. Thus, the sequence is well-defined and we are done with creating a single sequence. To show that we can create infinitely many sequences (which would imply that all generators, and thus all natural numbers, are included), it suffices to prove that there are infinitely many generators left after finitely many steps. Indeed, for any large $N$, only at most $\sim \log_{1521}(N)$ generators no more than $N$ can be chosen, meaning that after creating $s$ sequences, there will be at least $\sim \frac{N-1}{2}-s\log_{1521}(N)$ generators no more than $N$ that haven't been chosen yet. Done.