1
$\begingroup$

This question already has an answer here:

I know there is a known way to count the number of solutions of $x^2 + y^2 = z$, Sum of squares. Is there an efficient way to enumerate the solutions ignoring sign and order?

$\endgroup$

marked as duplicate by kingW3, Glorfindel, Ken Duna, levap, Namaste Aug 15 '17 at 20:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

Conventionally we write $r_2(n)$ for the number of representations of $n$ as a sum of two squares where we do take signs and order into consideration.

If $n$ has no representations as $x^2+y^2$ with $x^2=0$, $y^2=0$ or $x^2=y^2$, the representations come in packets of eight, where adjusting signs and orders keeps you in the same packet so the number of representations ignoring order/signs is $r_2(n)/8$.

If $n$ is a square or twice a square, then we need to consider representations $x^2+0^2$, $0^2+y^2$ and $x^2+x^2$ etc. The answer in this case will be $(r_2(n)+4)/8$.

$\endgroup$
  • 1
    $\begingroup$ The question is about enumerating the solutions, not counting them. I want the actual solutions zero excluded. $\endgroup$ – vamsikal Aug 15 '17 at 6:16
  • 1
    $\begingroup$ @vamsikal As far as I am aware, "count" and "enumerate" are synonyms. If you want to generate or list the solutions, this is reasonably easy if one has the prime factorisation of $n$. $\endgroup$ – Lord Shark the Unknown Aug 15 '17 at 6:19
  • $\begingroup$ I want to list/generate all the solutions, and it is easy to factorize $z$, can you point me to a reference to the algorithm that generates/lists the solutions. $\endgroup$ – vamsikal Aug 15 '17 at 6:21
1
$\begingroup$

HINT.-The calculation is based on the following: every odd prime is of the form $4n\pm 1$. Those of the form $4n + 1$ and the even prime $2 = 1 + 1$ are sum of two squares but those of the form $4n-1$ are not. In addition, the sums of two squares are stable for multiplication: $$(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(ad\mp bc)^2$$ You apply this to the canonical product in your link $$n=2^{a_0}\prod p_1^{2a_i}\prod q_j^{b_j} $$ where the primes $p_i=4n_i-1$ need to be with even exponent in order you can express n as a sum of two squares.

$\endgroup$

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