Given a number N how many pairs of numbers have square sum less than or equal to N?

Question

Let's define $F(N)$ as the number of pairs of distinct positive integers $(A, B)$ such that $A^2 + B^2 \leq N$

If $N=5$ the only possible such pair is $(1, 2)$, for $N=10$ the pairs are two: $(1,2)$ and $(1,3)$.

Then we have $F(13)=3$, $F(17)=4$, $F(20)=5$, $F(25)=6$ and so on for every number which is sum of two distinct non-zero squares.

Is there any closed-form formula to calculate $F(N)$?

Answer 1

The following approach gives you a possible way to work on the $F(N)$, but doesn't provide a closed formula. Consider the formal power series $$f(x) = \sum_{n=1}^\infty x^{n^2}.$$ Then your number $F(N)$ is given by the sum of the coefficients of $x^k$ for $k\le N$ in $f(x)^2$. Notice that the series can be expressed by means of the theta function: Wolfram

Answer 2

The point $(A, B)$ fits within a circle of radius $\sqrt{N}$. There are about $\pi N$ points within this circle. That includes:

• The origin $(0,0)$
• $4\lfloor\sqrt{N}\rfloor$ points $(0,\pm n)$ and $(\pm n,0)$ for $0<n\leq \sqrt{N}$
• $4\lfloor\sqrt{N/2}\rfloor$ points $(\pm m,\pm m)$ for $0<m\leq\sqrt{N/2}$
• $8M$ points $(\pm a,\pm b)$ and $(\pm b,\pm a)$.

So I estimate $$M={\pi N-1-4\sqrt{N}-4\sqrt{N/2} \over 8}$$ solutions.

EDIT: This is called the Gauss Circle Problem on Wikipedia, where $r^2$ is used instead of $N$.