I didn't understand $ia_i$ is trivial, but that is cleared/ thanks. But isn't it so there is a simpler solution with fact $T(T(x))=x$ has max. $gr(T)^2$ solutions, hence $T^n(x)=x$ has also a finite number of solutions... edit: it works with polonomials, but not in other way and I saw.

$i|a_i$ because of cycles. And your solution is nonsense because $T$ isn't polymomial.

You mean you don't understand that $i \mid a_i$, i.e. $i$ divides $a_i$. This follows from the fact that if for some $a$ we have $T^i(a) = a$, but not $T^j(a) = a$ for any $0<j<i$, then the orbit of $a$ is given by $i$ distinct numbers $a,T(a),\ldots,T^{i-1}(a)$, and since orbits are clearly disjoint, it means $a_i$, which counts all elements of all such orbits, is divisible by $i$. As for your second assertion, the concept $\deg T$ is ill-used, since $T$ is not specified to be a polynomial function.

Let $b_i$ be the number of primitive solutions to $T^i(x)=x$. Clearly $i | b_i$, since $b_i$ is the number of elements of $i$-cycles of $T$. And $P(n) = \sum_{d|n} b_d$. There are two ways to finish (1) We see that if $q$ is prime, $P(nq) = \sum_{d|n} b_d + \sum_{e} b_e$, where the second sum runs over divisors of $nq$ with maximal $v_q$. Therefore $q | P(nq)-P(n)$, and from this, $q | P(n)-a_0$, where $a_0$ is the constant term of $P$. Then the polynomial $P-a_0$ is always divisible by all primes, contradiction since this implies $P$ is constant. (2) Mobius Inversion. We get $n | b_n = \sum_{d|n} P(d)\mu(n/d)$ and we can finish easily.

Suppose to the contrary. Define $\text{ord}(x)$ to be the smallest integer $d$ such that $T^d(x) = x$. Let $a_n$ denote the number of positive integers $x$ such that $\text{ord}(x) = n$. Let $d = \text{ord}(x)$. Now, if $T^n(x) = x$ for some $n \in \mathbb{N}$, let $n = dq+r$, with $r \in [0,d)$. Then \[ x = T^n(x) = T^{dq+r}(x) = T^r(T^{dq}(x)) = T^r(x) \]. Since this is impossible for $r \in (0, d)$ (minimality of $d$), we must have $r = 0$, i.e. $d|n$. Note also that whenever $d|n$, $T^n(x) = x$. Now, $P(n)$ counts the number of integers $x$ with $T^n(x) = x$. Since $d|n$, therefore $P(n)$ must be obtained by adding the number of integers $x$, for which $\text{ord}(x)$ is in the set of divisors of $n$. Therefore, $P(n) = \sum_{d|n}a_d$. Observe that $d|a_d$. This is because whenever $\text{ord}(x) = d$, we also have $\text{ord}(T^i(x)) = d$ $\forall i \in [1, d)$. To see why, note that $T^{i+d}(x) = T^i(x)$. If there is a smaller integer $d'$ such that $T^{d'+i}(x) = T^i(x)$, we may apply $T$ iterated $d-i$ times on either side to obtain \[ T^{d+d'}(x) = T^d(x) \Longleftrightarrow T^{d'}(x) = x \], a contradiction. Furthermore, note that we can split these numbers into the aforementioned kind of cycles. To prove that these cycles are disjoint, suppose to the contrary. Then, for some $y$ not in the cycle corresponding to $x$, we must have $\text{ord}(x) = \text{ord}(y) = d$ and $T^i(x) = T^j(y)$ for some $i, j \in [0, d)$. Applying $T$ iterated $d-j$ times on either side, we have \[T^{d+i-j}(x) = T^d(y) \implies T^{d+i-j}(x) = y\], contradicting our assumption. Since $a_d$ counts the number of such integers and since these can be split into cycles of length $d$, we must have $d|a_d$. Now, let $p, q$ be distinct primes $\in \mathbb{P}$. Then, \[P(pq) = a_1+a_p+a_q+a_{pq} \equiv a_1+a_q \equiv P(q) \pmod{p} \] But, $P(pq) \equiv P(0) \pmod{p}$. Therefore, \[ P(q) \equiv P(0) \pmod{p} \implies p|P(q)-P(0) \]Since $P$ is non-constant, there exists $q$ such that $P(q) \neq P(0)$ (otherwise, there would exist infinitely many roots to $P(x)-P(0)$). Now, choosing $p$ arbitrarily large, we have a contradiction, since $P(q)-P(0)$ cannot have arbitrarily large prime divisors.

Write $T$ in cycle notation and let $c_n \ge 0$ denote the number of cycles of length $n$. Then the point is that \[ P(n) = \sum_{d \mid n} d c_d. \]By shifting $P$ by a constant we may assume $c_1 = 0$. Now we contend $c_q = 0$ for every prime $q$, which implies $P(q) = 0$ for all primes $q$, hence $P \equiv 0$. First, note that by selecting $p$ prime we get \[ P(0) \equiv P(p) = c_1 + pc_p \equiv c_1 \equiv 0 \pmod p \]whence $P(0) = 0$, since $p$ was any prime. Now observe \[ P(pq) = c_1 + p \cdot c_p + q \cdot c_q + pq \cdot c_{pq} \implies 0 \equiv P(0) \equiv P(pq) \equiv q c_q \pmod p \]whence $c_q \equiv 0 \pmod p$ for all $p \neq q$, hence $c_q = 0$.

Take $p$ a prime and $x_0$ such that $T^p(x_0)=x_0$. We infer that either $x$ is a fixed point or the orbit of $x_0$ within $T$ is of length $p$. As a general observation that will be used later, if $T^n(x_0)=x_0$ then $T^n (T(x_0))=T(x_0)$, so all the values from the orbit of $x_0$ satisfy $T^n(x)=x$. On a set $R$ whose elements all have finite orbits length we can define the relation $a \sim b\Leftrightarrow a=T^i (b)$ for some nonnegative integer $i$. It is easy to see that $\sim$ is an equivalence relation and that the class of an element $a$ is exactly the orbit of $a$. This in turn implies that if the length of the orbits of all the elements are divisible by a number $k$, then $k$ divides $|R|$ because each class has a multiple of $k$ elements and the classes partition $R$. Take $p,q$ distinct primes and look at the set $M=\{x\in \mathbb{Z}| T^{pq}(x)=x\}$. The length of the orbit of an element in $M$ can only take values in the set $\{1,p,q,pq\}$. The set $N$ of elements from $M$ with orders $1$ and $q$ is actually the set of solutions to $T^q(x)=x$, hence its cardinality is $P(q)$. The set $M-N$ has only elements of orders $p$ and $pq$, so, by the previous paragraph, the total number of elements in $M-N$ is divisible by $p$. We conclude that $P(pq)=|M|=|N|+|M-N|=P(q)+p\alpha$, so $p$ divides $P(pq)-P(q)$, or equivalently $P(0)-P(q)$. Taking $p$ very large we conclude that $P(0)=P(q)$. But this happens for an infinite number of primes $q$, hence $P$ is constant, contradiction.

Please check my solution

It seems to be correct

Note that $\sum_{d\mid n} P(d) \mu (n/d)$ gives the number of solutions $x$ such that $T^n(x)=x$ but $T^m(x)\neq x$ for $m<n$. Clearly, this number must be divisible by $n$, so we have $n\mid \sum_{d\mid n} P(d)\mu (n/d)$. Let $p$ and $q$ be primes and $n>1$ an arbitrary integer. Then $q\mid p^nq\mid P(p^nq)-P(p^n)-P(p^{n-1}q)+P(p^{n-1})$. Since $q\mid P(p^nq)-P(p^{n-1}q)$, we get $q\mid P(p^n)-P(p^{n-1})$. Repeating this for all primes $q$, we get $P(p^n)=P(p^{n-1})$. Since this holds for all integers $n>1$, we get $P(x)$ attains the same value for infinitely integers $x$, and thus $P$ must be constant, contradiction.

Define the order of $x\in \mathbb Z$ to be the minimum $n > 0$ such that $T^n(x) = x$ and $0$ if $n$ does not exist. Note that $a_n \leq P(n)$ is finite. Now, if we draw the graph on $\mathbb Z$ where $x\to T(x)$, then $a_n = nb_n$ where $b_n$ is the number of cycles of length $n$; in particular $n\mid a_n$. Now, clearly \[ P(n) = \sum_{d\mid n} a_d, \]so by Mobius Inversion we have \[ n\mid a_n = \sum_{d\mid n} \mu\left(\frac nd\right) P(d). \]Let $p,q$ be distinct primes. Then, \[ p\mid a_{pq} = P(1)-P(p)-P(q)+P(pq), \]i.e. $p\mid P(1)-P(q)$. Combining with $p\mid a_p = P(1)-P(p)$ we get that $p\mid P(1)-P(q)$ for all primes $q$. In particular, $q$ hits every residue mod $p$ by Dirichlet, so $P$ is constant mod $p$ for all $p$. This implies $P$ is constant on $\mathbb N$: indeed, if there existed $a,b > 0$ with $P(a)\neq P(b)$, then we could find some prime $Q$ such that $P(a)\not\equiv P(b)\pmod Q$ (take $Q > |P(a)-P(b)|$), contradiction. So, $P$ is constant on $\mathbb N$ and is a constant polynomial, contradiction. $\blacksquare$

Nice problem. Here's my solution: FTSOC assume that such a function $T$ exists. Construct an infinite directed graph, and label the vertices $1,2,3, \dots,$ such that there is an edge from $i$ to $j$ if and only if $j=T(i)$ (The graph is not necessarily simple). Let $p$ be some prime, and $f(p)$ denote the number of directed cycles of length $p$. Also, let $f(1)$ be the number of integers $x$ satisfying $T(x)=x$ (i.e. the number of loops in our graph). Then, the given condition states that $P(p)=pf(p)+f(1)$ (since each element $x$ of a cycle of length $p$ satisfies $T^p(x)=x$). Now, $$p \mid P(p)-P(0) \Rightarrow P(0) \equiv pf(p)+f(1) \equiv f(1) \pmod{p}$$Thus, $p \mid P(0)-f(1)$ for all primes $p$, which is only possible if $P(0)=f(1)$. Let $p'$ be another prime ($p' \neq p$). Then, again from the given condition, we get that $$P(pp')=f(1)+pf(p)+p'f(p')+pp'f(pp') \Rightarrow P(pp') \equiv f(1)+pf(p) \equiv P(0)+pf(p) \pmod{p'}$$But, we know that $$pp' \mid P(pp')-P(0) \Rightarrow pf(p) \equiv P(pp')-P(0) \equiv 0 \pmod{p'}$$This means that $p' \mid f(p)$ for all primes $p' \neq p$, which is only possible if $f(p)=0$. Thus, $P(p)=f(1)$ for all primes $p$. But then the polynomial $P-f(1)$ has infinitely many roots, and so it must be an identity; which contradicts the fact that $P$ is non-constant. Hence, done. $\blacksquare$

Nothing different from the above solutions, but posting for storage. Suppose for contradiction that such a function $T$ did exist. We let the order of an integer $k$ be the minimal $\ell \geq 1$ such that $T^\ell(k) = k$. Let $f(n)$ be the number of integers $k$ that have order $n$ (where $n \geq 1$). We claim that $n \mid f(n)$. Indeed, let $k$ be an integer with order $n$. Then, $k, T(k), T^2(k), \ldots, T^{n - 1}(k)$ all have order $n$ as well; hence, integers of order $n$ come in groups of $n$, proving the claim. Now, suppose $k$ satisfies $T^n(k) = k$. Trivially, the order of $k$ must divide $n$. It follows that there are \begin{align*} \sum_{d \mid n} f(d) \end{align*}integers $k$ that satisfy $T^n(k) = k$. Therefore, \begin{align*} P(n) &= \sum_{d \mid n} f(d). \end{align*} Now, fix a prime $q$, and let $p > q$ be a prime. We have \begin{align*} P(1) &= f(1) \\ P(p) &= f(1) + f(p) \\ P(q) &= f(1) + f(q) \\ P(pq) &= f(1) + f(p) + f(q) + f(pq). \end{align*}Hence, \begin{align*} f(pq) &= P(pq) - P(p) - P(q) + P(1). \end{align*}Since $p \mid pq \mid f(pq)$, we have \begin{align*} P(pq) - P(p) - P(q) + P(1) &\equiv 0 \pmod{p} \\ P(1) - P(q) &\equiv 0 \pmod{p}. \end{align*}Hence, for all primes $p > q$, we have $p \mid P(1) - P(q)$, which is enough to imply that $P(q) = P(1)$. Hence, $P(q) = P(1)$ for all primes $q$, which is enough to imply that $P$ is a constant polynomial; contradiction. $\Box$

Obviously, we'll assume that such a $(T,P)$ existed. Let $c_n$ be the number of integers such that the smallest $m$ such that $T^m(x)=x$ is $n$. We see then that \[P(n)=\sum_{d\mid n} c_d,\]so \[c_n=\sum_{d\mid n}\mu(d)P(n/d)\]by Mobius inversion.

For any two primes $p,q$, we see that \[c_{pq^n}=P(pq^n)-P(q^n)-P(pq^{n-1})+P(q^{n-1}).\]This must be divisible by $p$, and we see that $p\mid P(pq^n)-P(pq^{n-1})$, so we have \[P(q^n)\equiv P(q^{n-1})\pmod{p}\]for all primes $p$. This implies $P(q^n)=P(q^{n-1})$ for all $n$, which is clearly a contradiction, as desired. $\blacksquare$

Suppose on the contrary that such function exists, for each positive integer $n$, suppose that $T$ has $x_n$ $n-$cycles. Then the number of integer $x$ with $t^n(x)=x$ is equal to $$\sum_{d|n}nx_n=P(n)$$Let $y_n=nx_n$, by Mobius inversion formula, $$y_n=\sum_{d|n}\mu(d)P(\frac{n}{d})$$In particular for every prime $p$ and integer $\alpha$ we have $$p^{\alpha}|y_{p^\alpha}=\sum_{d|p^{\alpha}}\mu(d)P(\frac{p^{\alpha}}{d})=P(p)-P(1)$$since $\mu(p^i)=0$ for all $i\geq 2$. This implies $P(p)-P(1)=0$. Since this holds for every prime $p$, $P$ must be a constant, contradiction.

The number of solutions of T^q(X)=X is divisble by q for every prime q that's because we have a string a1,a2,..,a_q with T(a_i)=a_(i+1) and T(a_q)=a1 and we cant have a_i=a_j because then we get that something divides q (the reader should check why). Therefor the string has q different solutions to the equation which are a_i for all i multiplied by the number of such strings and therefore q divides P(q) for all q so q divides the free coeficent of P so q is infinitly big (impossible) or zero.

Suppose FTSOC that such a $T$ exists, and define the $\emph{order}$ of $x$ as the smallest $k$ such that $T^k(x)=x.$ It follows from cycle decomposition that the number of integers with order $k$ is divisible by $k$ for all $k.$ $\textbf{Claim: }$ $P(0)=P(x)$ for infinitely many primes $x.$ $\emph{Proof: }$ Divide the set of primes into two disjoint infinite sets $A$ and $B,$ and fix $p\in A,q\in B.$ Suppose $x$ is an integer satisfying $T^{pq}(x)=x.$ Then, the order of $x$ is $1,p,q,$ or $pq.$ Now observe the following. The number of integers with order $p$ or $pq$ is divisible by $p.$ The number of integers with order $1$ or $q$ is equivalent to the number of solutions to $T^{q}(x)=x,$ which is $P(q).$ Therefore, $P(pq)\equiv P(q)\pmod{p}.$ But it is well-known that $P(pq)\equiv P(0)\pmod{p},$ so we have $p\mid P(q)-P(0).$ Since we can apply the same reasoning for all $p\in A,$ we have $P(0)=P(q)$ for all $q\in B.$ $\blacksquare$ Therefore, $P$ must be constant, contradiction.

Same as everyone else: Put the function $T$ on a graph of integers, and draw an arrow between $x$ and $T(x)$. Let $f(n)$ be the number of cycles of length $n$. Clearly, the only time $T^{n}(x) = x$ is if $x$ is in a cycle of length $d$, where $d | n$. This implies \[\sum_{d|n} df(d) = P(d)\]Consider some $n$ such that $v_{p}(n) = r$, and let $m = \frac{n}{p^{r}}$. Then, consider $P(n) - P(m)$; for any $d | n$ and $d\not | m$, we must have $p | d$. Thus, using the formula for $P(n)$, it implies \[p | P(n) - P(m) \Rightarrow p | P(m) - P(0)\]However, observe that $m$ can take on any value, and $p$ can be any prime. Thus, for all $p$ and all $m$, this holds. However, for large enough $p$, we have $p > |P(m) - P(0)|$, which means $P(m) = P(0)$. This means $P$ is a constant polynomial, a contradiction.

Does this work????? View as a directed graph where we draw an arrow from $x \to T(x).$ Let $c_k$ denote the number of cycles of length $k.$ Assuming there existed a $T,$ \[ P(n) = \sum_{d \mid n} d c_d. \]Then, consider $P(pq) - P(q)$ for fixed primes $p$ and $q.$ We must have $P(pq) - P(q) = pq c_{pq}.$ Let $P(x) = a_k x^k + \cdots + a_0.$ Then, \[ pq \mid P(pq) - P(q) \iff p \mid q^k(p^k-1)a_k + q^{k-1} (p^{k-1}-1) + \cdots + q(p-1) \]which gives $p \mid P(q) - a_0.$ However, since we can now fix $q$ and take $p$ very large, this cannot be true for all $(p,q),$ so $P(q) - a_0 = 0 \implies P(q) = a_0$ for all $q,$ which in turn implies that $P$ is constant, contradiction. $\blacksquare$

Let $c_i$ denote the number of cycles of length $i$. We get the following identity. \[ P(n)=\sum_{d|n} nc_n \]. We claim this is impossible. Indeed, assume that such a polynomial exists. For any prime $p$ we have $P(p)=c_1+pc_p$. So, $P(p) \equiv c_1$ (mod $p$) for every prime $p$. Thus, $P(x)=x \cdot Q(x)+c_1$ for some integer polynomial $Q$. Now, we have \[ pq \cdot Q(pq)+c_1=P(pq)=c_1+pc_p+qc_q+pqc_{pq} \]for any primes $p$ and $q$. Thus, $pq$ divides $pc_p+qc_q$ but by making $p$ sufficiently large, this identity clearly breaks down. Contradiction.

View $T$ as a directed graph in the obvious way. We only care about directed cycles. Let $C(n)$ denote the number of cycles of length $n$, so we want to have $$P(n)=\sum_{d \mid n} dC(d)$$for all $n$. In particular, $P(p)=C(1)+pC(p)$ for all primes $p$. Let $P(x)=xQ(x)+C$ for some constant $C$, so we can write $$pQ(p)-pC(p)=C(1)-C$$for all $p$, hence $C(1)-C$ has infinitely many prime divisors so it equals zero, i.e. $P(x)=xQ(x)+C(1)$. Let $p$ be an arbitrary prime. Then for all $q$, we have $$pqQ(pq)+C(1)=P(pq)=C(1)+pC(p)+qC(q)+pqC(pq),$$so $q \mid pC(p) \implies q \mid C(p)$. Thus $C(p)=0$, as $C(p)$ has infinitely many prime divisors. As such, $$P(p)=C(1)+pC(p)=0$$for all primes $p$, hence $P$ must be the zero polynomial, which is forbidden. $\blacksquare$

Consider $T$ as an arrows graph: a collection of chains and cycles. Let $a_i$ denote the number of cycles of length $i$. Assume that $P(n)$ is the number of fixed points of $T^n(x)$, then $P(n)$ can be fully characterized as \[P(n) = \sum_{d\mid n} d a_d \]where $\{a_i\}_i$ is an infinite sequence of nonnegative integers. Let $P(x) = b_n x^n + b_{n-1} x^{n-1} + \cdots b_0$. Then, note that $P(q^{k+1}) \equiv P(q^k) \pmod{q^{k+1}}$. But, $q^{k+1} \mid P(q^{k+1}) - P(0)$. Thus, $P(q^k)\equiv P(0) \pmod{q^{k+1}}$. Thus, $b_1 q^k \equiv 0 \pmod{q^{k+1}}$. By selecting $p>b$, we win. $\blacksquare$ poggers

Solved with CT17. We show that if there exists a function $T$ satisfying the problem conditions, then $P$ is constant. Notice that any $x$ satisfying $T^n(x) = x$ for some $n\ge 1$ must be in a cycle of $T$. For each positive integer $n$, let $a_n$ denote the number of cycles length $n$ of $T$. Define the order of $x$ to denote the smallest $m\ge 1$ such that $T^m(x) = x$. There are in total $n\cdot a_n$ elements of order $n$ for all positive integers $n$, and $P(n)$ consists of all the elements with order dividing $n$. Hence \[P(n) = \sum d a_d,\]where the sum is over all divisors of $n$. For any prime $p$, $P(p) = p a_p + a_1$. This implies that $P(p) \equiv P(0)\equiv a_1 \pmod p$, for all primes $p$, hence $P(0) = a_1$. This implies that $a_p = \frac{P(p) - P(0)}{p}$. For any primes $p,q$, we have $P(pq) = pq a_{pq} + p a_p + qa_q + a_1$. Take the equation mod $p$. The LHS is $P(pq) \equiv P(0) = a_1 \pmod p$, and the RHS is $qa_q + a_1 \pmod p$. Therefore, $qa_q\equiv 0\pmod p$, so $p \mid a_q \mid P(q)- P(0)$. Varying $p$, we find $P(q) - P(0)$ has infinitely many divisors, so $P(q) = P(0)$. Since this is true for all primes $q$, the polynomial $P(x) -P(0)$ has infinitely many roots, so it must be the zero polynomial, which implies $P$ is constant, as desired.

Funny problem. Suppose that such a function $P$ exists. Let $a_k$ be the number of cycles of length $k$, so $$P(n) = \sum_{d \mid n} da_d.$$Then by Mobius inversion, $$na_n = \sum_{d \mid n} \mu(d) P\left(\frac nd\right).$$For $n = p^r$ prime, this implies $p^r \mid P(p) - P(1)$ for all $r$, thus $P(p) = P(1)$ and $P$ must be constant.

Note that a fixed point of $T^n$ is precisely the numbers in cycles of length $d\mid n$. Let $c(d)$ denote the number of cycles of length $d$. Thus, we have $$\sum_{d\mid n}dc(d)=P(n).$$ We claim that this implies that $P$ is constant, which would solve the problem. \begin{claim} For any prime $p$, we have $$c(p)=\frac{P(p)-P(1)}{p}.$$\end{claim} This follows by $$c(1)+pc(p)=P(p).$$ Of course, the next thing to try is $P(pq)$. \begin{claim} For distinct primes $p$ and $q$, we have $$c(pq)=\frac{P(pq)-P(p)-P(q)+P(1)}{pq}.$$\end{claim} To prove this, use the the fact that $$c(1)+pc(p)+qc(q)+pqc(pq)=P(pq)$$combined with the previous claim. In particular, we have $$pq\mid P(pq)-P(p)-P(q)+P(1),$$which implies that $$p\mid P(pq)-P(p)-P(q)+P(1).$$Since $p\mid P(pq)-P(p)$, we have $$p\mid P(1)-P(q).$$Thus, $$P(1)\equiv P(q)\pmod{p}$$for all primes $p$ and $q$. Note that since $P(1)$ and $P(q)$ are finite, this holding for all primes $p\neq q$ implies that $P(1)=P(q)$. Thus, the polynomial reaches the same value of $P(1)$ infinitely often. By polynomial identity theorem, $P$ is constant, and we are done.

Let $a_n$ be the number of cycles in the graph of $G$. Then it's clear that $\sum_{d \mid n} d \cdot a_d = P(n)$ for all positive integer $n$. Then mobius inversion formula yields $a_n \cdot n = \sum_{d \mid n} P(d) \mu(\frac{n}{d})$. Therefore $P(pq^a) - P(q^a) - P(pq^{a-1}) + P(q^{a-1}) \equiv 0 (pq^a)$, so $p \mid P(q^a) - P(q^{a-1})$ for all primes $p, q$. But this is an evident contradiction. $\blacksquare$

Let $n$ be a positive integer and $p$ be a prime. Let $f(x)$ denote the number of numbers $z$ such that $T^x(z)=z$ holds for $f(x)$ values of $z$. Note, we have \[P(n)=\sum_{d\mid n}df(d)\]It follows that $p\mid P(np)-P(n)$ and since $p\mid P(np)-P(0)$, we have that $p\mid P(n)-P(0)$. Taking $p>|P(n)-P(0)|$ forces $P(n)=P(0)$ which is the constant polynomial, a contradiction.

Represent $T$ as a directed graph where each edge $x\to T(x)$ is drawn. Then, $T^n(x)=x$ if and only if $x$ is in a cycle of size $d$ where $d\mid n$. Let $k$ be the number of loops. Then, for all primes $p$, $P(p)$ is the number of vertices in cycles of size $p$, plus $k$. Therefore, $P(p)\equiv k\pmod p$ for infinitely many $p$, which means that we can write $P(x)=xQ(x)+k$ for some integer polynomial $Q$. Now, fix some prime $p$ and vary $q$, then we have $P(pq)=pqa+pb+qc+k$, where $a$ is the number of cycles of size $pq$, $b$ is the number of cycles of size $p$, and $c$ is the number of cycles of size $q$. Then, $pq\mid pqa+pb+qc$ so $pq\mid pb+qc$ which implies $q\mid b$ for all $q$, which means $b=0$. This means that $P(x)=k$ for all primes which is a contradiction.

Let $c_i$ the number of integers satisfying that $T^i(x)=x$ and $T^j(x) \ne x$ for all $1 \le j <i$, then note that if $x$ works so do $T(x), T^2(x), \cdots, T^{i-1}(x)$ and since we said that they are all different we must in fact have $i \mid c_i$, now the problem condition is that $P(n)=\sum_{d \mid n} c_d$, now for some $n$ consider primes $p>n$, then: $$P(pn)=\sum_{d \mid pn} c_d=\sum_{d \mid n} c_d+\sum_{d \mid n} c_{pd}=P(n)+\sum_{d \mid n} c_{pd}$$Now each $c_{pd}$ is divisible by $p$ so we in fact have $p \mid P(pn)-P(n)$ for all $p>n$ primes, but this means $p \mid P(n)-P(0)$ ans by setting a huge prime we get $P(n)=P(0)$ for all positive integers $n$, thus $P$ is constant, contradiction!. Therefore no such function $T$ should exist thus we are done .

Assume the contrary and let the \emph{order} of $n$ be defined as the amount of numbers $x$ such that $n$ is the smallest natural number such that $T^n(x)=x$, and let it be denoted by $\text{ord}(n)$. One can easily see that \[n \mid \text{ord}(n) \text{ and } P= \text{ord} \ast 1\]And hence let $q$ be any prime and we get $\bullet$ $P(1)=\text{ord}(1)$. $\bullet$ $P(q)=\text{ord}(1)+\text{ord}(q) \implies q \mid P(0)-P(1) \iff P(0)=P(1)$. And so \begin{align*} \implies & P(qr)=\text{ord}(1)+\text{ord}(q)+\text{ord}(r)+\text{ord}(qr)\\ \implies & qr \mid P(qr)+P(1)-P(q)-P(r)\\ \implies & q \mid P(r)-P(0) \end{align*}for any two distinct primes $q$, $r$; and we easily get that $P(X) \equiv P(0)$, which is a contradiction.

You can actually prove it's zero not just for the primes.

Let, $g_T(i)$ be the number of values $x$ such that $T^i(x)=x$ and $i$ is the minimal value for which that occurs, clearly we have that $n\mid g_T(n)$, thus let $g_T(1)=k$, now let $f_T(i)$ denote the number of values such that $T^i(x)=x$, thus we get that $f_T(p^2)\equiv k\pmod p^2$ for some $g_T(p)\neq 0$, as we can't have infinetly many values where $g_T(p)=0$. Thus we get that $p^2\mid g_T(p)$, which because of infintely many primes having that property means the minimal power term that isnt the constant term must be at least $2$, and by repeating this argument we get that the minimal power term that isnt the constant term is abitrarily large which is a contradicition.

This problem is quite contrived, since we really only need to consider the cycles of $T$. Say there are $a_n$ cycles of length $n$, then we get \[\sum_{d\mid n}da_d=P(n).\]Consider this for $n$ a prime. Then $a_1+pa_p=P(p)$, so $P(0)\equiv a_1\pmod p$. This is true for all $p$, so $P(0)=a_1$. Thus we may set $a_1=0$ and $P(0)=0$ (since $a_1$ and $P(0)$ always appear in the equation). Now we will prove that for every number $n$, $a_n=0$. We will do this by strong inducting on $\Omega(n)$. So say we proved it for when $\Omega(n)=m$, now consider $\Omega(n)=m+1$. Consider a prime $p\nmid n$, using $pn$ in the big equation has the RHS divisible by $p$ and the LHS is just $na_n$ mod $p$. So $p\mid na_n$ for all $p\nmid n$, so $a_n=0$. Thus $P$ is constant, contradiction.

Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025. Reminds me of 2D Prefix Sums