Count the Ways

The theory of expressing integers as sums of squares is old and well understood. Let me remind the reader of the basic ideas and then apply them to our specific case. My source is Beiler's excellent "Recreations in the Theory of Numbers." Does anybody have a good link?

A good tool in this matter (although not the most sophisticated one) are the Gaussian integers $\mathbb{Z}[i]$ . Here are some basic facts on $\mathbb{Z}[i]$ : (a) It's a unique factorization domain; (b) the units are $1,-1,i,-i$ , and (c) the primes are the elements $z=x+iy$ where $x^2+y^2$ is an integer prime (such as $1+i$ or $2-3i$ ) as well as the integer primes that are congruent to 3 modulo 4 (we will call those the 3-primes).

For a given positive integer $n$ , the representations $n=x^2+y^2$ , where $x$ and $y$ are integers, correspond to the divisors $z=x+iy$ of the Gaussian integer $n$ with $x^2+y^2=n$ . It is sensible to restrict ourselves to the case $x>0,y\geq 0$ , thus picking exactly one representative in each class of associate divisors. Let's denote the number of such representations by $g(n)$ . For example, $g(3)=0, g(4)=1,g(5)=2$ , $g(25)=g(50)=3$ , and $g(65)=4$ .

Let's write

$n=2^{a}3^{a_1}7^{a_2}...5^{b_1}13^{b_2}...,$

grouping together first the 3-primes with exponents $a_k$ and then the 1-primes with exponents $b_k$ . We know that $g(n)>0$ if and only if all the $a_k$ are even; from now on, let us assume that this is the case. It is not hard to see that $g(n)=(b_1 +1)(b_2 +1)...$ .

In this problem, we are counting the representations $n=x^2+y^2$ somewhat differently, though, requiring that $x\geq y>0$ ; let's denote the number of such representations by $f(n)$ . If $g(n)$ is even, then $f(n)=\frac{g(n)}{2}$ since we want $x \geq y$ . But we have to think carefully about the case when $g(n)$ is odd, meaning that all the $b_k$ are even. If $n$ is a perfect square, meaning that $a$ is even as well, then we have the representation $n=m^2+0$ that contributes to $g(n)$ but not to $f(n)$ . If $\frac{n}{2}$ is a perfect square, meaning that $a$ is odd, then we have the representation $n=m^2+m^2$ that contributes to $g(n)$ as well as $f(n)$ . Thus we have

$f(n)=\frac{1}{2}\Big(-(-1)^a+(b_1 +1)(b_2+1)...\Big)$ if all the $b_k$ are even, and

$f(n)=\frac{1}{2}\Big((b_1 +1)(b_2+1)...\Big)$ otherwise

For example, $f(25)=1$ for $25=16+9$ and $f(50)=2$ for $50=49+1=25+25$ .

Now, finally, we can get to the specifics of our problem: we need to find the smallest $n$ with $f(n)=11$ . In our solution, all the $a_k$ will be 0, $a$ will be 0 or 1, and the $b_k$ will be nonascending; if any of these requirements is not met, we can easily construct a smaller solution of the equation $f(n)=11$ . Considering the three cases of our formula for $f(n)$ , this means that $g(n)=(b_1+1)(b_2+1)...$ must be 21, 22, or 23. In the case of $g(n)=21$ , with the factorizations $21=21=7\times 3$ , we must have $a=1$ and $b_1=20$ or $b_1=6$ . With $5^{20}>>5^6\times 13^2$ , the smallest solution in this case is $2\times 5^6\times 13^2 = 5281250$ . In the two other cases, 22 and 23, all the solutions will contain a factor of $5^{10}=9765625$ , producing larger numbers. Thus the solution is $N=\boxed{5281250}$ .

I hate not being able to write solutions by myself but presenting video links. Nevertheless, once you watch this 30 minutes video by 3B1B the solution will pop on your mind.

https://oeis.org/A016032

$Mathematica$ code

n = 1; While[Length@PowersRepresentations[n++, 2, 2] != 11]; n - 1

Read the following three references

(1) L.E. Dickson, History of the Theory of Numbers, Vol. II, "Diophantine Analysis", Ch. VI, "Sum of two squares", p. 227.

(2) WolframAlpha, Sum of Squares function.

(3)https://www.primepuzzles.net/puzzles/puzz_062.htm

Using WolframAlpha script:

"PowersRepresentations[(13^2)(5^6),2,2]" gave 11 ways but with X>Y and Y= 0 entry as follows:

{{0, 1625}, {57, 1624}, {180, 1615}, {400, 1575}, {455, 1560}, {572, 1521}, {625, 1500}, {825, 1400}, {975, 1300}, {1020, 1265}, {1113, 1184}}

Modifying and multiplying by 2

"PowersRepresentations[2(13^2)(5^6),2,2]" removed 0, but with one X= Y and gave 11 ways as follows:

{{71, 2297}, {245, 2285}, {325, 2275}, {575, 2225}, {875, 2125}, {949, 2093}, {1105, 2015}, {1175, 1975}, {1435, 1795}, {1567, 1681}, {1625, 1625}}

Answer=2 (13^2) (5^6)=5281250

Next larger number, 13*(5^10) with, all X>Y in 11 ways is given by:

PowersRepresentations[13(5^10),2,2]

{{230, 11265}, {625, 11250}, {2550, 10975}, {3375, 10750}, {3750, 10625}, {4545, 10310}, {5521, 9822}, {6250, 9375}, {6575, 9150}, {6943, 8874}, {7250, 8625}}