Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
Looking modulo $16$ $x^2$ is either $0,1,4,9$ and $y^4$ is either $0,1$ so $x^2 + y^4$ is either $0,1,2,4,5,9,10$ modulo $16$ which might be helpful. –  dinoboy Dec 14 '12 at 16:44

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.