Is there a natural problem on the naturals that is NP-complete? Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there any natural problems, i.e. ones that do not use some encoding and special interpretation of the digits? For example "Is n a prime?" is such a natural problem, but this one is in P. Or "Who wins the Nim game with heaps of size 3, 5, n, n?" is another problem that I consider natural, but we also know this to be in P. I am also interested in other complexity classes instead of NP.

Update: As pointed out by Emil Jeřábek, given $a,b,c\in \mathbb N,$ to determine whether $ax^2+by-c=0$ has a solution over the naturals is NP-complete. This is exactly what I had in mind as natural, except that here the input is three numbers instead of just one.

Update 2: And after more than four years waiting, Dan Brumleve has given a "better" solution - note that it's still not complete because of the randomized reduction.
Based on the discussion, I’ll repost this as an answer.

As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^2+by-c=0$ has a solution $x,y\in\mathbb N$.

(The original paper states the problem with $ax^2+by-c$, but it is not hard to see that one can reduce it to the case $a=1$.)