Counting sums of squares

In the process of writing the previous post, I ran across the Landau-Ramanujan theorem. It turned out to not be what I needed, but it’s an interesting result.

What portion of the numbers less than N can be written as the sum of the squares of two non-negative integers? Edmund Landau discovered in 1908, and Srinivasa Ramanujan independently rediscovered in 1913, that the proportion is asymptotically

c / (log N)^1/2

where c, the Landau-Ramanujan constant, equals 0.76422….

Let’s see how the number of squares less than 1000 compares to the estimate given by the theorem.

from math import sqrt, log

N = 1000
c = 0.76422
print("Predicted: ", c / sqrt(log(N)))

sumsq = N*[0]
for i in range(N):
    for j in range(N):
        n = i**2 + j**2
        if n < N:
            sumsq[n] = 1
            
print("Exact: ", sum(sumsq)/N)

The predicted proportion is 0.291 and the exact proportion is 0.330.

The script takes O(N²) time to run, so we'd need to do something more clever if we wanted to investigate very large N.