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'm looking for some help disproving an answer provided on a StackOverflow question I posted about computing the number of double square combinations for a given integer.

The original question is from the Facebook Hacker Cup

Source: Facebook Hacker Cup Qualification Round 2011

A double-square number is an integer $X$ which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because $10 = 3^2 + 1^2$. Given $X$, how can we determine the number of ways in which it can be written as the sum of two squares? For example, $10$ can only be written as $3^2 + 1^2$ (we don't count $1^2 + 3^2$ as being different). On the other hand, $25$ can be written as $5^2 + 0^2$ or as $4^2 + 3^2$.

You need to solve this problem for $0 \leq X \leq 2,147,483,647$.

Examples:

$10 \Rightarrow 1$

$25 \Rightarrow 2$

$3 \Rightarrow 0$

$0 \Rightarrow 1$

$1 \Rightarrow 1$

In response to my original question about optimizing this for F#, I got the following response which I'm unable to confirm solves the given problem correctly.

Source: StackOverflow answer by Alexandre C.

Again, the number of integer solutions of $x^2 + y^2 = k$ is four times the number of prime divisors of $k$ which are equal to $1 \bmod 4$.

Knowing this, writing a program which gives the number of solutions is easy: compute prime numbers up to $46341$ once and for all.

Given $k$, compute the prime divisors of $k$ by using the above list (test up to $\sqrt{k}$). Count the ones which are equal to $1 \bmod 4$, and sum. Multiply answer by $4$.

When I go through this algorithm for $25$, I get $8$ which is not correct.

  1. For each prime factor (pf) of $25$ (5,5 are prime factors of $25%)
    • if pf % 4 = 1 (true for both 5's), add 1 to count
  2. return 4 * count (count would be 2 here).

So for $25$, this would be 8

share|improve this question
add comment

4 Answers

up vote 13 down vote accepted

This is worked out in detail in many an introductory textbook on Number Theory. Here is a summary of the treatment in An Introduction to the Theory of Numbers (5th Edition) by Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery (Wiley, 1991, section 3.6).

Theorem (Fermat) Let $n$ be a positive integer, and write $n$ in the form $$n = 2^{\alpha}\prod_{p\equiv 1\pmod{4}} p^{\beta} \prod_{q\equiv 3 \pmod{4}} q^{\gamma}.$$ with $p$ and $q$ primes. Then $n$ can be expressed as a sum of two squares if and only if all the exponents $\gamma$ are even.

Now, define the following:

  • $R(n)$: the number of ordered pairs $(x,y)$ of integers such that $x^2+y^2=n$.
  • $r(n)$: the number of ordered pairs $(x,y)$ such that $\gcd(x,y)=1$ and $x^2+y^2=n$ (called "proper representations of $n$");
  • $P(n)$: the number of representations of $n$ by the form $x^2+y^2$ with $\gcd(x,y)=1$, $x\gt 0$ and $y\geq 0$;
  • $N(n)$: the number of solutions to the congruence $s^2\equiv -1\pmod{n}$.

Theorem. A positive integer $n$ is properly represented by the form $x^2+y^2$ if and only if $-4$ is a square modulo $4n$.

In particular, since $-4$ is a square modulo $8$ but not modulo $16$, $n$ may be divisible by $2$ but not by $4$. If $p$ is an odd prime of the form $4k+1$, then $-4$ is a square modulo $p$, and by Hensel's Lemma it lifts to a solution modulo $p^k$ for an y $k$; so $n$ may be divisible by arbitrary powers of primes of the form $4k+1$. On the other hand, if $p$ is a prime that divides $n$ and is congruent to $3$ modulo $4$, then $-4$ is not a square modulo $p$. So we get:

Theorem. A positive integer $n$ is properly representable as a sum of two squares if and only if the prime factors of $n$ are all of the form $4k+1$, except for the prime $2$ which may occur to at most the first power.

Now suppose that $n$ is positive and $n=x^2+y^2$ is an arbitrary representation. Set $g=\gcd(x,y)$; then $g^2|n$, so $n = g^2m$, $\gcd(\frac{x}{g},\frac{y}{g}) = 1$, so $m$ is properly represented as the sum of the squares of $\frac{x}{g}$ and $\frac{y}{g}$. Note that $g$ may have prime factors congruent to $3$ modulo $4$, which divide $n$ to an even power, and the power of $2$ that divides $n$ may be arbitrary as well.

Theorem. Suppose that $n\gt 0$. Then $P(n)=N(n)$, $r(n) = 4N(n)$ and $R(n)=\sum r\left(\frac{n}{d^2}\right)$, where the sum is taken over all positive $d$ such that $d^2|n$.

Theorem. Let $n$ be a positive integer and write $$ n = 2^{\alpha}\prod_{p}p^{\beta}\prod_q q^{\gamma}$$ where $p$ runs over prime divisors of $n$ congruent to $1$ modulo $4$ in the first product, and $q$ runs over prime divisors of $n$ of the form $4k+3$ in the second. If $\alpha=0$ or $1$, and all $\gamma$ are $0$, then $r(n) = 2^{t+2}$, where $t$ is the number of primes $p$ of the form $4k+1$ that divide $n$ (counted with multiplicity); otherwise, $r(n)=0$. If all the $\gamma$ are even, then $R(n) = 4\prod_p(\beta+1)$. Otherwise, $R(n)=0$.

share|improve this answer
    
I know that this probably answers the question posed by the Title, but how does it relate to whether the proposed formula (in the original Stack Overflow answer) accurately answers the Hacker cup question. For instance, in your impressive explanation here do you cover the fact that the originally proposed formula doesn't count the match of 5^2 + 0^2 for 25? –  Jacob Jan 14 '11 at 18:07
2  
@Jacob: Given that by the time I started writing this answer you had already established that the quoted answer was counting something other than what you asked the count for, why should the "impressive answer" (and here you were complaining about flippancy...) cover the ground that has been settled already? –  Arturo Magidin Jan 14 '11 at 18:17
    
@Jacob: It does prove it wrong! With this answer, you know that the other answer will give you wrong count... –  Aryabhata Jan 14 '11 at 18:45
    
Your answer really is impressive, I wasn't being flippant. It's exactly the kind of thing I was looking for and can hardly understand. I wanted more information about whether I was missing something or the formula really did miss possible combinations. Thanks for the help. –  Jacob Jan 14 '11 at 19:02
    
Here is the right solution: press Help button –  Orient Jul 5 at 4:31
add comment

$25$ has two prime divisors: $5$ and $5$, and you have to count them both because they are both congruent to $1$ modulo $4$. Now multiply by $4$. You have $8$.

This counts the decompositions $$\begin{array}{cc} 3^2+4^2,& 3^2+(-4)^2, \\ (-3)^2+4^2, & (-3)^2+(-4)^2, \\ 4^2+3^2, & 4^2+(-3)^2, \\ (-4)^2+3^2, & (-4)^2+(-3)^2 \end{array} $$

As you can see, multiplying by $4$ at the end is done to cater for signs: if you are only interested in "positive" decompositions, then don't do that. Also, this counts $a^2+b^2$ as different from $b^2+a^2$. If you don't want that, well, you have to substract the number $N$ of decompositions of the form $a^2+a^2$ (which is easy to compute...) divide by $2$, and then add $N$ back.

Finally, if you want to know why this works, well, there are very few better things than to consult an introduction to number theory!

share|improve this answer
1  
Aside from your flippant last sentence (you just gave 3 paragraphs of relevant "why this works"), this is very helpful. You've shown that his given algorithm doesn't solve the actual problem. –  Jacob Jan 14 '11 at 16:14
4  
@Jacpob: There is nothing flippant in recommending that you read a textbook on number theory: that is precisely what textbooks are for! Notice that I did not explain in the least why this works: I just gave an example where it works. To actually explain why it works, also known as proving the statement, well, you need to set up a minimum of basic number theory to even start (and that is usually done best in... you guessed! introductory textbooks to number theory) –  Mariano Suárez-Alvarez Jan 14 '11 at 17:30
4  
@Jacob: we are talking about mathematics: my exhibiting all 8 ways to write 25 as a sum of non-zero integers is not an explanation of why it is true that the number of ways in which you can write an integer as a sum of two non-zero squares is what it is. $$ $$I am sorry if you feel that directing you to a textbook is... whatever it is you feel: essentially everything I know I learnt from textbooks, so I simply cannot imagine what the problem with my last sentence is. I know for a fact that there is no possible way I could come up with an explanation of the why better than what you'll –  Mariano Suárez-Alvarez Jan 14 '11 at 18:22
1  
(cont.) find in any of the standard introductory texts. I also do not think the site is well-adapted to us producing such explanations, nor even that it is desirable that we would do that. –  Mariano Suárez-Alvarez Jan 14 '11 at 18:23
1  
@Jacob I don't think that you understand what a mathematician means when he says "understand why something is true". I cannot detect even a hint at such an explanation in Mariano's answer. To address your question "if you took away that last sentence, would it detract from your overall answer?", it would leave an answer consisting of a single example and of a formula with no explanation. As it is, the answer also contains pointers to where to learn more. If you are not interested, then why don't you just ignore the last sentence, instead of asking for its deletion?... –  Alex B. Jan 15 '11 at 0:48
show 6 more comments

A simpler way to look at this would be to consider the factorization of $\displaystyle n$ in Gaussian Integers: $\displaystyle \mathbb{Z}[i] = \{a + bi \ \ | \ a \in \mathbb{Z}, \ b \in \mathbb{Z}\}$.

It is well known that that

  • Gaussian integers have unique factorization property (upto units $\displaystyle \pm 1, \pm i$).
  • Primes (of $\displaystyle \mathbb{Z}$) of the form $\displaystyle 4k+3$ are also primes in $\displaystyle \mathbb{Z}[i]$.
  • Primes (of $\displaystyle \mathbb{Z}$) of the form $\displaystyle 4k+1$ factorize into $\displaystyle w w'$ for a prime $\displaystyle w$ (in $\displaystyle \mathbb{Z}[i]$) and $\displaystyle w'$ is the conjugate of $\displaystyle w$. In fact, if $\displaystyle w = a+ib$, then the prime is of the form $\displaystyle a^2 + b^2$.
  • $\displaystyle 2 = (1+i)(1-i)$ and $\displaystyle 1+i$ is prime.

Now if $\displaystyle n = x^2 + y^2$ then $\displaystyle n = (x+iy)(x-iy)$, which corresponds to factorization of $\displaystyle n$ in $\displaystyle \mathbb{Z}[i]$, which you can get from the prime factorization of $\displaystyle n$ in $\mathbb{Z}[i]$ by choosing a subset of primes to multiply, to get $\displaystyle x + iy$. The conjugates of those primes go toward $\displaystyle x-iy$. The remaining need to be a perfect square to distribute once each into $\displaystyle x+iy$ and $\displaystyle x-iy$. Note this implies that primes of the form $\displaystyle 4k+3$ (which are also primes in $\displaystyle \mathbb{Z}[i]$) need to have an even power in the factorization.

So it basically amounts to finding out the different factorizations of the perfect squares which are factors of $\displaystyle n$ (after ignoring primes of the form $\displaystyle 4k+3$).

Note: It is the units which gives the multiple of $4$, if you count $(x,y), (y,x), (-x,y),(y,-x)$.

(Of course, this is not a formal proof...)

Hope the helps.

share|improve this answer
add comment

For a completely unambiguous counterexample, consider $k=15$: it has one prime factor (5) that is congruent to 1 modulo 4, but it cannot be written as a sum of two squares. The reason (as mentioned in both Moron's and Arturo's answers) is that a number cannot be written as a sum of two squares unless all its prime factors that are congruent to 3 modulo 4 are raised to even powers.

share|improve this answer
add comment

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.