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 trying to find the numbers of possibilities of $x^2+y^2$ that are not perfect squares for $0\le x\le m$ and $0\le y\le n$ and $x+y>0$.

I think if we calculate the numbers of possibilities of $x^2+y^2=d^2$, it will do it. Any formulas or even an algorithm?

share|improve this question
    
One should not expect an exact closed form expression. There is a pleasant formula for the number of integer solutions of $x^2+y^2=d^2$, in terms of the prime power factorization of $d$. –  André Nicolas Jan 28 '13 at 16:40
    
@AndréNicolas : thanks , please tell that formula still though i just wanted a formula for any d :) –  Maggi Iggam Jan 28 '13 at 16:44
    
@MaggiIggam Note that the formula does not take into consideration the bounds on $x$ and $y$, so it won't necessarily be exact for $d \ge \min\{m,n\}$. Nevertheless this can be turned into an algorithm with the potential to be more efficient than $O(mn)$ brute force (but much harder to implement). –  Erick Wong Jan 28 '13 at 16:54

1 Answer 1

We give a count of the number of representations of an integer as a sum of two squares, if there are no size restrictions. This does not answer the question, but is in response to a request from the OP.

Let $n$ be a positive integer, and let $$n=2^ap_1^{a_1}\cdots p_s^{a^s} q_1^{b_1} \cdots q_t^{b_t},$$ where the $p_i$ are distinct primes of the form $4k+1$, and the $q_j$ are distinct primes of the form $4k+3$.

If at least one of the $b_j$ is odd, then $n$ has no representations as a sum of the squares of two integers.

If all the $b_j$ are even, then $n$ has $N(n)$ representations as the sum of the squares of two integers (positive, negative, or $0$), where $$N(n)=4(a_1+1)(a_2+1)\cdots(a_s+1).$$

We may instead be interested in the number of essentially distinct representations, where for example the representations $2^2+3^2=13$, $3^2+2^2=13$, $(-2)^2+3^2=13$, and so on are considered to be "the same." Note that if $n=k^2$, the representation $n=k^2+0^2$ is included in the count.

If $8$ divides $N(n)$, then there are exactly $\dfrac{N(n)}{8}$ essentially distinct representations of $n$ as a sum of two squares.

If $8$ does not divide $N(n)$, then there are $\dfrac{N(n)+4}{8}$ essentially distinct representations of $n$ as a sum of two squares.

Now let $n=d^2$. If we know the prime power factorization of $d$, we can write down the prime power factorization of $d^2$, and then use the above formulas.

share|improve this answer
    
Nice elaborate answer, +1. Note that the condition "$8$ does not divide $N(n)$" means that all exponents in the factorisation of $n$ must be even, except possibly the exponent $a$ of $2$; therefore this happens if and only if either $n$ is a perfect square (in which case $n=k^2+0^2$ is one of the solutions) or $n$ is twice a perfect square (in which case $n=k^2+k^2$ is one of the solutions). In particular it is this first special case that applies concretely to the question. Note that the other special case was evoked in this question. –  Marc van Leeuwen Jan 29 '13 at 11:29

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.