By same number of prime factors, I'm guessing same number of prime factors with multiplicity. Is that the correct way to interpret it? For example, 12 has 3 prime factors, right? @above, thanks for the edit. understood it now.

$1+x+\frac{x^2}{2}+\frac{x^3}{6}\hdots$ but the coefficients are not integers. This non-solution is the power series for $e^x $ which satisfies.

let $m=n$ in the original state ment to get $ Q(m^2),Q(m)$ have the same number of prime devisors so $Q(m^{2^n}),Q(m)$ have the same number of prime devisors so from $n=m^{2^t-1}$ we get if $p|Q(m)$ then $p|Q(m^{2^t-1})$ and vice versa , so the sequance $Q(m^{j_1 j_2 ... j_r})$ has the primes of $Q(m)$ ,where $j_t =2^{k_t}-1$ for some $k_t$... let $Q(m)=p_1^{a_1} p_2^{a_2}...p_n^{a_n}$ and let $f(m)= v_2( (p_1 -1)(p_2 -1)...(p_n-1))$ assume , $m>(some- thing -really- big)$ now lets take care of $v_{p_i}(Q(m^{j_1 j_2 ... j_r}))$ lets we must have there is $i$ such that the below doesnt hold : $p_i^{a_i+1}|m^{j_1 j_2 j_3 ... j_r} - m$ now lets give $Q$ some form if there is a polynomial $A$ such that $A(x)^2|Q(x)$ just consider $\frac{Q}{A}$ instead of $Q$ now we have the $0$ root is there atmost once ... if $Q(x)=ax$ we are done , now we take cases if $0$ is not a root of $Q$ then clearly $(p_i,m)=1$ for this just take$ m\in P$ so clearly we must have $ p_i ^{a_i}(p_i -1)|j_1 j_2 ... j_r -1$ , let $v_2(j_i +1)>f(m)$ now take $r=2k$ and we just need go for the odd part of $ p_i ^{a_i}(p_i -1)$ lets have $j_i=2^q -1$ for a prime $q$ now we wantso we want to work with ($s=2^q-1$ $(s^k-1)(s^k+1)$ now take $q=(p_i-1)\phi(p_i-1)c+1$ and pick a good $k$ , di this for each $p_i$ and after using CRT, for finding the right $q$ and the weak form of dirichelet , we are done ... if $Q(0)=0$ just take out the $m$ from $Q(m)$ and let $m$ be a big prime , the same conclusion from above works ... . .

Basically same as @above: Let $Q(x)= x^dR(x)$ where $x \not| R(x)$. Take $p > R(0)$, therefore $p \not| R(p^e)$ for all positive integers $e$. See that $R(p), R(p^2), R(p^{2^2}), ... $ all have the same number of prime divisors. Assume $e$ is an integer such that $R(p)$ and $R(p^e)$ have the same number of prime divisors. Hence all primes $q$ that divide $R(p^{e-1})$ must also divide $R(p)$. But $R(p^{e-1})$ has at least as many prime divisors as $R(p)$, hence these two numbers share the same set of prime divisors. By up-down induction, we see that all $R(p^s)$ share the same prime divisors with $R(p)$ for all $s$.

for example). Hence $Q(x)=Ax^d$, which clearly work.

I missed elementary solution presented above . So here is a convoluted solution using analytic NT. Replace $Q$ with $f$. The answer is $f(x)=cx^d$ for $c\in\mathbb{Z}^+$ and $d\in\mathbb{Z}^+\cup\{0\}$, which clearly works. We prove that these are all solution. Following standard notation, denote by $\omega(n)$ the number of distinct prime divisors of $n$. Let $d=\deg f$. The idea is the average order of $\omega(f(n))$ is less than $d\log\log n$. Thus, we will make the LHS larger than this average and cause the contradiction. We will prove the following stronger claim. Main Claim: Suppose that $f$ is nonconstant satisfying $f(n)\geq 1$ for all positive integer $n$ and $\omega(f(ab))\leq \omega(f(a)) + \omega(f(b))+C$ for some constant $C$, then $f(0)=0$. Once we have this, we can take $f(x)=x^rg(x)$ so that $g(0)\ne 0$. Then, \begin{align*} \omega(f(ab)) &= \omega(ab\cdot g(ab)) \\ &\geq \omega(ab) + \omega(g(ab)) - \omega(\gcd(g(ab),ab)) \\ &\geq \omega(ab)+\omega(g(ab)) - \omega(g(0)) \\[4pt] \omega(f(a)f(b)) &= \omega(ab\cdot g(a)g(b)) \\ &\leq \omega(ab)+\omega(g(a)g(b)) \\ &\leq \omega(ab)+\omega(g(a))+\omega(g(b)) \end{align*}Thus, if $g$ is nonconstant, then by the claim (taking $C=\omega(f(0))$), $g(0)=0$, contradiction. Hence, we restrict our attention into proving this claim. Proof of the main claim: Let $p_1 < p_2 < \hdots$ denote the list of primes dividing some entries in $f(\mathbb{Z})$, which is known to be infinite due to Schur's theorem. We first prove the following weak bound of $p_k$. Lemma: $p_k < e^{O(k)}$ for all $k$. Proof: We mimic the Erdos' proof of infinitude of prime. For each $i$, we write $f(i)=a\cdot b^{d+1}$ where $0\leq \nu_p(a)\leq d$ for any prime $p$. Considering for all $i$ which $f(i)<p_k$, then There are at most $(p_k)^{\frac{1}{d+1}}$ choices of $b$. There are at most $(d+1)^{k}$ choices of $a$. Thus, $$(p_k)^{\frac{1}{d+1}}\cdot (d+1)^k \gg (p_k)^{\frac 1d}$$which gives the desired result after rearranging. $\blacksquare$ Remark: I'm pretty sure that Chebotaraev Density Theorem provides a much stronger version of this claim, but this is enough for our purpose. Call a prime $p$ bad if it is less than $2020d$, divides $f(0)$, or the leading coefficient $c$ of $f$; call that prime good otherwise. Take $N$ very large so that $p_N$ exceeds all bad primes. For each $i$ which $p_i$ is good, we pick a residues $a_i, b_i$ such that $$p\mid f(a_ib_i) \text{ and } p\nmid f(a_i)f(b_i).$$To pick the residues, take $n_i$ which $f(n_i)\equiv 0\pmod p_i$ but $p\nmid n_i$. Suppose that for each $a$, either $f(a)$ or $f(n_i/a)$ divides $p$. This gives at least $\tfrac{p-1}{2}$ roots for $f$ in modulo $p$. As the leading coefficient of $f$ is not $0\pmod p$, this is a contradiction to Lagrange's theorem (we must have $p<2d$ so $p$ is bad). If $p_i$ is bad, then we define $a_i,b_i$ so that $p\mid f(a_ib_i)$ only. By CRT, we can pick $a,b<p_1p_2\hdots p_N$ so that $$a\equiv a_i\pmod{p_i},\ b\equiv b_i\pmod{p_i}\text{ for all } i\leq N.$$Thus, for any constant $k$, we have that $$N \leq \omega(f(a+kP))+\omega(f(b+kP)) + C \quad\text{where } P=p_1p_2\hdots p_n.$$Summing this from $k=1$ to $M-1$ (pick $M=e^{N^3}$) to get $$M(N-C) \leq \sum_{k=1}^M \omega((f(a+kP)) + \omega(f(b+kP)).$$We investigate the number of terms that $p$ divides $f(a+kP)$. If $p\leq p_N$, but $p$ is bad, then $p$ may divide $f(a+kP)$, but there are finitely many such primes (say at most $t$) of them. If $p\leq p_N$, but $p$ is good, then $p$ cannot divide $f(a+kP)$ due to our construction. If $p_N < p < \sqrt{MP}$, then we see that the leading coefficient of $g(x)=f(a+Px)$ is not zero in modulo $p$. Thus, at most $d\left\lceil \tfrac Mp\right\rceil < \tfrac{dM}{p}+d$ numbers are divisible by $p$. If $p>\sqrt{MP}$, then most terms can have at most $2d$ such divisors due to size reasons. Thus, these primes contribute at most $2dM+O_{M,N}(1)$ to the sum. Summing, we see that \begin{align*} M(N-C)&\leq 2\left(t + \sum_{p<\sqrt{MP}}\left(\frac{dM}{p} + d\right) + dM + O_{M,N}(1)\right) \\ &\leq 2\left((M\log\log(MP) + A + o_{M,N}(1) + d\sqrt{MP}) + 2dM + O_{M,N}(1)\right) \\ &\leq 2\left(M\log\log(e^{N^5}) + O(e^{N^3/2}+O(N^2))\right) \\ &\leq 2\left(5M\log N + O(e^{N^3/2+O(N^2)})\right) \end{align*}which is a contradiction if $N$ is large enough.

So we need analytic number theory also for math Olympiads in school.

This is a very much technical proof.

Just edit your previous post and write there , why making two posts ( just saying no offence ) here also you did something like that here

Aritra12 wrote: Just edit your previous post and write there , why making two posts ( just saying no offence ) here also you did something like that here Are you saying me Aritra12?

MarkBcc168 wrote: I missed elementary solution presented above . So here is a convoluted solution using analytic NT. Quote: What a miss! Brilliant.