For $n \geq 1$, let $S(n)$ denote the set of all integers at most $n$, which can be written as a sum of two perfect squares, and let $s(n) = |S(n)|$.

How fast does $s(n)$ grow as $n \to \infty$?

It is easy to see that $\sqrt{n} \leq s(n)$ for all $n \geq 1$. (This follows from the fact that all perfect squares $\leq n$ are in $S(n)$, together with the fact that for $n \geq 2$, we have $2 \in S(n)$.)

Also, we know that $\lim_{n \to \infty} \frac{s(n)}{n} = 0$. This follows from the fact that the set of all integers which are the sum of two perfect squares $S = \cup_{n=1}^\infty S(n)$ has 0 upper density; in other words, the probability that a "random" positive integer is a sum of two squares is 0. Going back to the first sentence of this paragraph, we have that $s(n)$ grows slower than any linear function.

I presume that to answer the above question, we probably want to use the following well-known characterization due, I think, to Euler (see page 5) of the set of all integers which are the sum of two squares.

Theorem: Let $n \geq 1$. Then $n \in S(n)$ (i.e. $n$ can be written as a sum of two squares) iff for all primes $p$, if $p \equiv 3 \mod 4$, then the exponent of $p$ in the prime factorization of $n$ is even.


See William J. LeVeque, Topics in Number Theory, available both volumes in one

it is $$ \frac{C \; n}{\sqrt {\log n} \; \; } $$ The constant $C$ is known, it is a certain infinite product.

Using the natural logarithm,

$$ C \approx 0.7642 $$


If we determine $s(n)$ exactly for $n \leq 12$ or so, we can plug in the sequence $s(1), s(2), s(3), \ldots s(12)$ into OEIS. Indeed, the numbers $\leq 12$ that are a sum of two squares are

$$1, 2, 4, 5, 8, 9, 10.$$

So we have the following table of values of $s(n)$: \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline s(1) & s(2) & s(3) & s(4)& s(5) & s(6) & s(7) & s(8) & s(9) & s(10) & s(11) & s(12) \\ \hline 1 & 2& 2 & 3 & 4 & 4 & 4 & 5 & 6 & 7 & 7 & 7 \\ \hline \end{array}

So plugging in 1,2,2,3,4,4,4,5,6,7,7,7 into OEIS, we find the sequence $\{s(n)\}_1^\infty$ there. Clicking the linked article by Daniel Shanks gives this article, which recalls the following asymptotic formula proved by Landau (which Will Jagy gave):

$$s(x) \sim \frac{bx}{\sqrt{\log x}},$$

where $\log x$ is the natural logarithm and

$$b = (2 \prod_q (1 - q^{-2}))^{-1/2},$$ where the product is over all primes $q$ of the form $4m +3$.

In the above linked article (the top of page 76), Daniel Shanks goes on to state an even better approximation of $s(n)$ (which uses "big O" notation):

$$s(x) = \frac{bx}{\sqrt{\log x}}\left[1 + \frac{c}{\log x} + O\left(\frac{1}{\log^2 x} \right) \right], $$

where $b \approx .7642$ and $c \approx .5819$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.