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.

The post Counting sums of squares first appeared on John D. Cook.