I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e.
$$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$
with $P(x,y), Q(x,y) \in \mathbb{Z}_+[x,y]$.
Note that when a Diophantine function
$$f(n) = m \Leftrightarrow (\exists k) P(n,m,k) = Q(n,m,k)$$
(which is not of the desired form) and $k$ is bounded – i.e. there is a fixed primitive-recursive function $K(n,m)$ with $P(n,m,k) = Q(n,m,k) \Rightarrow k < K(n,m)$ – one can equivalently write
$$f(n) = m \Leftrightarrow \prod_{i=0}^{K(n,m)}(P(n,m,i) - Q(n,m,i)) = 0$$
which is of the desired form. (Maybe even for arbitrary computable functions $K(n,m)$?)
So the question is: Are there primitive-recursive functions with
$$f(n) = m \Leftrightarrow (\exists k) P(n,m,k) = Q(n,m,k)$$
where the variable $k$ is not bounded?
Let $f(n)=2^n$. And assume there is nonzero $R(x,y)=P(x,y)-Q(x,y)\in\mathbb Z[x,y]$ with $R(n,2^n)=0$ for all $n\in\mathbb N$. Write $R(x,y)=\sum_{k=0}^K R_k(x)y^k$ with $R_k\in\mathbb Z[x]$ and $R_K\ne 0$. Then there exist $C, x_0$ with $|R_k(x)|<C\cdot (\frac 32)^x$ for all $x>x_0$ and all $k$. Then for $x>x_0$, $y>1$, $$\left|\frac{R(x,y)-R_K(x)y^K}{y^K}\right|<KC(\tfrac32)^xy^{-1}$$ So if $y=2^x$ and $x_0<x\in \mathbb N$, we conclude $$ |R_K(x)|<KC(\tfrac 34)^x.$$ Especially, the polynomial $R_K$ is bounded, hence constant, and this constant must be zero, contradiction.