Checking if a number if expressible as $x^2+y^4$

Question

I was solving this question http://www.spoj.com/problems/HS08PAUL/, which asks number of integers in range $[1,n]$ which are expressible in form $x^2+y^4$, $x$ and $y$ being integers.

A simple implementive solution passes (loop $x$ for $1\leq x\leq\sqrt{n}$ and then $y$ till $x^2+y^4\leq n$, but I was wondering if there is some mathematical theorem governing such numbers.

More specifically: given an integer $n$, do there exist integers $x$ and $y$ such that $x^2+y^4=n$?

Answer 1

Every perfect square is $0$ or $1$ modulo $4$. So $x^2+y^4\equiv0,1,2$ mod $4$ and this implies if $n\equiv3$ mod $4$ then there is no soloution.

Answer 2

Since $x^2+y^4=x^2+(y^2)^2$, Fermat's Theorem on sums of two squares could be used with two caveats:

1. It applies only to odd $n$.
2. It would give only a necessary condition.

Moreover, since to apply it you have to factor $n$, it is probably a worse computational method.