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.
- 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
- return $4$ * count (count would be $2$ here).
So for $25$, this would be $8$