# Find the number of functions $f(x)$ with $f(f(n)) = n+2022$ for every nonnegative integer n.

Find the number of functions $$f(x)$$ from nonnegative integers to nonnegative integers so that $$f(f(n)) = n+2022$$ for every nonnegative integer n.

Let $$a_0 = f(0)$$ and let $$a_n = f(a_{n-1})$$ for $$n\ge 1$$. Then $$a_{n} - a_{n-2} = 2022$$ for every $$n\ge 2$$. The characteristic equation of the corresponding homogeneous recurrence is $$x^2 - 1,$$ which has roots $$\pm 1.$$ Also, $$b_n = 1011 n + b$$ satisfies the inhomogeneous recurrence $$b_n - b_{n-2} = 2022$$ for any integer $$b$$. So $$a_n = A(-1)^n + 1011 n + B$$ for some integers $$A,B$$ and all $$n$$. We must ensure that $$a_n$$ is always nonnegative. We must have $$a_0\ge 0\Rightarrow A \ge -B.$$ Also, $$a_1\ge 0\Rightarrow -A +1011 + B \ge 0, a_2\ge 0\Rightarrow A +2022 + B\ge 0.$$ In general, for all $$n=2k+1> 0$$, $$B\ge A-1011 n$$ and for all $$n=2k\ge 0, A\ge -B-1011n$$. To satisfy both of these inequalities, it suffices to have $$B\ge A-1011$$ and $$A\ge -B\Rightarrow B\ge -B-1011\Rightarrow 2B\ge -1011.$$ So $$B$$ is at least $$-505.$$ Though I'm not sure how to determine what $$f(n)$$ can be. Clearly $$f(n) = n+1011$$ solves the functional equation and $$f(0)$$ cannot be zero, so it must be positive. If there exists $$n$$ so that $$f(n) = n$$, then we get $$n=n+2022$$ by plugging this n into the given equation, which is a contradiction. Hence $$f$$ has no fixed points.

$$f(f(n))=n+2022\tag0$$ $$f(f(f(n))=f(n+2022)$$ $$f(n+2022)=f(n)+2022\tag1$$ Thus specifying $$f(n)$$ for $$n\in[0,2021]$$ fixes $$f$$.
Now write the nonnegative integers in a zero-indexed infinite matrix with $$2022$$ columns so that $$n$$ has – and is treated as equal to – the coordinates $$(\lfloor n/2022\rfloor,n\bmod2022)$$. Then if $$f$$ sends $$(q+d,r)$$ to $$(q,s)$$ where $$d\ge1$$ (a backwards jump), by $$(1)$$ it must also send $$(d-1,r)$$ to $$(-1,s)$$ which is absurd. As a corollary $$f$$ cannot send $$(q,r)$$ to $$(q+d,s)$$ with $$d\ge2$$ (a long forwards jump), since by $$(0)$$ $$(q+d,s)$$ must be sent to $$(q+1,r)$$, a backwards jump.
Therefore a number $$(0,r)=r\in[0,2021]$$ can only be sent by $$f$$ to $$(0,s)$$ or $$(1,s)$$; $$s\ne r$$ since $$f$$ would then have a fixed point by $$(0)$$, which is inconsistent with $$(1)$$. If $$f((0,r))=(0,s)$$, columns $$r$$ and $$s$$ of the infinite matrix are completely defined; if $$f((0,r))=(1,s)$$, $$(1)$$ implies $$f((0,s))=(0,r)$$ with the same end result as before.
The final result is that all admissible functions $$f$$ are specified by a pairing of residue classes modulo $$2022$$ and then, for each pair $$(r,s)$$, whether $$f((0,r))=(0,s)$$ or the other way round. The number of such $$f$$ is thus $$\frac{2022!}{1011!}$$ A similar argument shows that for $$f^{(p)}(n)=n+pq$$ the number of such functions is $$\frac{(pq)!}{q!}$$
• Below is my understanding of how you got $2022!/1011!$. Correct me if I'm wrong. first choose a number $s$ for $0$ in $2021$ ways and one of the pairs $(0,s)$ or $(1,s)$ in 2 ways. Then remove the residues $0$ and $s\neq 0$, leaving $2020$ residues. Of the remaining residues, pick the smallest one and choose the pair $(0,s)$ or $(1,s)$ for this residue in $2\cdot 2019$ ways. Continue the process, obtaining $2^{1011} \cdot 2021!!$ ways. Sep 25, 2022 at 14:53
• @user33096 Permute the first $2022$ nonnegative integers any way you like ($2022!$ ways). This naturally splits into $1011$ ordered pairs, and these pairs may be permuted in $1011!$ ways without changing $f$. The quotient gives the answer. Sep 25, 2022 at 14:59
• @user33096 Yes. Suppose the permutation is $(a_1,a_2,a_3,a_4,\dots,a_{2022})$. Then the pairs are just length-2 chunks $(a_1,a_2)(a_3,a_4)(a_5,a_6)\dots$ The first element in each pair becomes the $(0,r)$ in my construction and the second becomes $(0,s)$, with $f((0,r))=(0,s)$. Sep 25, 2022 at 15:38