1 | initial version |
There is a known formula for number of representations as the sum of two squares - see Wikipedia. Employing it you can have summation $r_2(c^2$) just over $c$, which will give you a dramatic speed-up.
2 | No.2 Revision |
There is a known formula for the number of representations as the sum of two squares - see Wikipedia. Employing it it, you can have summation $r_2(c^2$) just over $c$, which will give you a dramatic speed-up.
3 | No.3 Revision |
There is a known formula for the number of representations as the sum of two squares - see Wikipedia. Employing it, you can have summation $r_2(c^2$) just over $c$, which will give a dramatic speed-up.
ADDED. Since this question concerns squares of positive integers, the formula for $r_2(n)$ needs to be a bit re-worked:
# number of representations of n as an ordered sum of two squares of positive integers
def r2_positive(n):
r = 1
for p,k in factor(n):
if p%4==1:
r *= k+1
elif p%4==3 and k%2:
return 0
return r - int(is_square(n))
Then you can get the desired count as
sum( r2_positive(c^2) for c in range(1,1000) )