Suppose $n$ is a large odd integer. Let $D_1(n)$ be the number of divisors of $n$ of the form $4k+1$ and let $D_3(n)$ be the number of divisors of the form $4k+3$. I would like to compute $(D_1(n),D_3(n))$.

As Joe Silverman points out, the number of representations of $n$ as a sum of two squares of integers is $4(D_1(n)-D_3(n))$. For example, $D_1(225)=6$ and $D_3(225)=3$, so there are $4(6-3)=12$ lattice points on the circle of radius $\sqrt {225}$ centered at the origin including $(0,15)$ and $(-9,-12)$.

Is there a faster way to find $(D_1(n),D_3(n))$ than factoring $n$?

Original:

Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form 4n+1 or 4n+3. Is there any faster method to it, especially for large n?

Suppose $n$ is a large odd integer. Let $D_1(n)$ be the number of divisors of $n$ of the form $4k+1$ and let $D_3(n)$ be the number of divisors of the form $4k+3$. I would like to compute $(D_1(n),D_3(n))$.

As Joe Silverman points out, the number of representations of $n$ as a sum of two squares of integers is $4(D_1(n)-D_3(n))$. For example, $D_1(225)=6$ and $D_3(225)=3$, so there are $4(6-3)=12$ lattice points on the circle of radius $\sqrt {225}$ centered at the origin including $(0,15)$ and $(-9,-12)$.

Is there a faster way to find $(D_1(n),D_3(n))$ than factoring $n$?

Original:

Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form $4n+1$ or $4n+3$. Is there any faster method to it, especially for large $n$?

Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form 4n+1 or 4n+3. Is there any faster method to it, especially for large n?

Suppose $n$ is a large odd integer. Let $D_1(n)$ be the number of divisors of $n$ of the form $4k+1$ and let $D_3(n)$ be the number of divisors of the form $4k+3$. I would like to compute $(D_1(n),D_3(n))$.

As Joe Silverman points out, the number of representations of $n$ as a sum of two squares of integers is $4(D_1(n)-D_3(n))$. For example, $D_1(225)=6$ and $D_3(225)=3$, so there are $4(6-3)=12$ lattice points on the circle of radius $\sqrt {225}$ centered at the origin including $(0,15)$ and $(-9,-12)$.

Is there a faster way to find $(D_1(n),D_3(n))$ than factoring $n$?

Original:

Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form 4n+1 or 4n+3. Is there any faster method to it, especially for large n?