As part of a number theory hobby project, I'm looking for a computational way to enumerate all integers $n$ which can be written as a sum of two integer squares in three or more ways. The range of $n$ will likely get quite large ( up to $\approx 2^{64}$) so I'm looking for methods that let me specify a search range for $n$, say $11\cdot10^{13}$ to $12\cdot10^{14}$, and return any values such as
$$1193162282546 = 1043815^2+321889^2 = 1066211^2+237395^2 = 1076911^2+182825^2$$
My first thought of solving this problem is rather brute force:
Enumerating $every$ sum of two squares within a range $n_0..n_1$ by iterating over
$n=a^2+b^2$ in a double loop over $1\le a \le\sqrt{n_1-1} $ and $\sqrt{n_0^2-a^2}\le b \le \sqrt{n_1^2-a^2}$ , then sorting the list and scanning it for duplicate values of 3 or more values.
I think this will work, but it may be very inefficient, with the vast majority of the computation thrown out.
The puzzle for you: Is there a better computational method?
Best Answer
Since you do not require relatively prime $x,y$ in $x^2 + y^2 = n,$ this has a very simple characterization, using the prime factorization of $n:$
(A) the exponent of 2 is irrelevant
(B) if $q \equiv 3 \pmod 4,$ the exponent must be even, otherwise this prime is also irrelevant as far as the count of $x^2 + y^2$ expressions
(C) there must either be $p^{4 + k}$ with $k \geq 0, \; \; p \equiv 1 \pmod 4,$ or $p_1^{1 + k_1} p_2^{2 + k_2}$ with $k_1, k_2 \geq 0, \; \; p_1, p_2 \equiv 1 \pmod 4,$ where we do not care whether $p_1$ or $p_2$ is larger, or $p_1^{1 + k_1} p_2^{1 + k_2} p_3^{1 + k_3}$ with $k_1, k_2, k_3 \geq 0, \; \; p_1, p_2, p_3 \equiv 1 \pmod 4.$ Here $p_1, p_2, p_3$ are distinct.
Right, so three distinct good primes does it, or one and another squared or better, or one to the fourth power or more.
EEEDDDIITTT: given your anti-factoring stance, the best way to do this is to spray things. Make a list of primes $1 \pmod 4$ up to an appropriate bound. Use that to make a list up to $1.2 \cdot 10^{15}$ of the successful numbers of type (C). Save that, and multiply by arbitrary $q^2$ with $q \equiv 3 \pmod 4$ and arbitrary $2^k,$ and keep the result if it is not too large.
I decided to run a little program, odd numbers up to $1 + 13^4$ that were expressible in at least three ways as $x^2 + y^2$ with $0 \leq x \leq y,$ and were not divisible by any prime $q \equiv 3 \pmod 4.$ Note that multiplying by 2 or by such $q^2$ does not change the number of representations. However, I found the numbers with at least three representations first, then i said only print out iff odd and not divisible by any $q \equiv 3 \pmod 4,$ and finally find the prime factorization for each and print that. So this little table experimentally confirms the patterns in part (C) above; I did not build those in.
---------------------------