Iterate the sum of two squares

Question

I am looking for an effective way to iterate over an infinite non-decreasing sequence defined by a^2+b^2 , where a , b are both positive integers. What I mean, iterations here, is that, given the existing list of entries n , the algorithm should be efficient (I hope O(log(m)) , where m=a^2+b^2 ) will find the following entry .

The beginning of this list is: 1 ^ 2 + 1 ^ 2 = 2, 1 ^ 2 + 2 ^ 2 = 5, 2 ^ 2 + 2 ^ 2 = 8, 1 ^ 2 + 3 ^ 2 = 10, 2 ^ 2 + 3 ^ 2 = 13, 1 ^ 2 + 4 ^ 2 = 17, ...

Here's the python code used to create these entries (the first 100 are correct):

 xs=[] for i in range(1, 100): for j in range(i, 100): xs.append((i**2+j**2, i, j)) xs.sort() 

I looked at the top of the list and do not see any template at all. Does anyone know an algorithm for this?

[edit] With some searching, I found the Kornakia algorithm , which requires a quadratic residue calculation. However, I still hope for something better, since we already know the previous numbers during the iteration.

Answer 1

The isSumOfSquares function returns True if n can be written as the sum of squares greater than zero and False otherwise, based on the algorithm from Edsgar Dijkstra’s 1976 book "Programming discipline: x turned down from the square root of n, decreasing when the sum of squares is too large , and y will shift up from 1, increasing when the sum of the squares is too small.

 from math import sqrt def isSumOfSquares(n): x, y = int(sqrt(n)), 1 while x >= y: if x*x + y*y < n: y = y + 1 elif x*x + y*y > n: x = x - 1 else: return True return False filter(isSumOfSquares, range(1,100)) 

This returns a list of [2, 5, 8, 10, 13, 17, 18, 20, 25, 26, 29, 32, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 65, 68, 72, 73, 74, 80, 82, 85, 89, 90, 97, 98]. I discussed a similar issue on my blog .

Answer 2

Thinking about it, I accepted two things. The first is that for any a ^ 2 + b ^ 2 a> b. This is simply because it is trivial (a, b) to be in the same place in order like (b, a), so you do not need to consider both.

The explanation is also simpler if a or b is allowed equal to 0. These cases can be easily extracted in a real algorithm.

My thinking is that you have to do something based on looking at m=a+b and stating that for a given m, the smallest sum of squares is m^2/2 (when they are equal), and the largest is (m-1)^2 with an obvious order between them. Then you can do a sort sort between them to find the next one.

I think that if you look at m=a+b , then for any given m you can create an ordered list of sums of squares for all a+b=m . The reason is that we know that the sum is maximum when a or b is 0 and minimum when a=b=m/2 . This means that we can trivially generate a series of lists of ordered sums of squares L(m) .

We also know the maximum and minimum entries in L (m), so we don’t need to start looking at these lists until we are in this range.

This will still mean potentially a lot to consider at higher values, but it is still better than a rougher approach.

I am not sure if there is a better way if you have this list, although in order to decide which one you need to choose. I think this is probably not true, although you could make some guesses based on the distribution of numbers in lists, but I cannot think of a way to formalize them in a good way.

To give a clearer example of things, then

 List Lowest value Highest value L(0) 0 (0,0) 0 (0,0) L(1) 1 (1,0) 1 (1,0) L(2) 2 (1,1) 4 (2,0) L(3) 5 (2,1) 9 (3,0) L(4) 8 (2,2) 16 (4,0) L(5) 13 (3,2) 25 (5,0) L(6) 18 (3,3) 36 (6,0) L(7) 25 (4,3) 49 (7,0) L(8) 32 (4,4) 64 (8,0) 

So, to start from 0, you only need to consider the elements in L (0), then this is exhausted, and you go to L (1). Then it is exhausted, etc. Then, working through L (3), you will find that you are looking at the last of L (3), which is larger than the lowest in L (4), so you are looking at both of these lists.

When you just put (5.0) and (4.3) over 25, you will consider things in L (6) and L (7). As you go higher, you will consider more lists as lists begin to contain more items in a larger range (for example, the number 10,000 is in the range for L (100) (approximately) and L (141) (which starts with 9941).

I should also note that you do not need to pre-compute the entire list, you can easily make it a lazy iterator to only calculate the number in front of the list, as this is the only one you ever wanted.