Ask Your Question

Revision history [back]

click to hide/show revision 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.

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.

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) )